Cyclic groups and modular exponentiation
The group of invertibles of Z/pZ, the order of an element, generators, Fermat's little theorem, Euler's theorem, Euler's totient and fast exponentiation.
- 28 cards
- 4 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
A few cards from the deck
Cyclic group: what is it?
Show the answer
A group whose elements are all obtained as successive powers of a single one of them.
The invertibles of Z/7Z are cyclic: the powers of 3 give 3, 2, 6, 4, 5, 1, that is all six elements.
Under which conditions is a to the power p − 1 equal to 1 modulo p?
- p prime, and p does not divide a
- p prime, a arbitrary
- p odd, a arbitrary
- a coprime with p, p arbitrary
Show the answer
p prime, and p does not divide a
If p divides a, a is zero modulo p and its powers stay zero. And if p is not prime, the exponent must be φ(p), not p − 1: modulo 9, 2⁶ ≡ 1 but 2⁸ = 256 ≡ 4.
For a prime p, the totient is φ(p) = …; for a product pq of two distinct primes, φ(pq) = ….
Show the answer
For a prime p, the totient is φ(p) = p − 1; for a product pq of two distinct primes, φ(pq) = (p − 1)(q − 1).
The integers from 1 to p − 1 are all coprime with p. For pq, you remove the multiples of p and of q: φ(33) = 2 × 10 = 20.
Order of an element: what is it?
Show the answer
The smallest exponent k ≥ 1 for which the powers of the element come back to 1.
In the invertibles of Z/13Z, the powers of 3 are 3, 9, 1 (27 ≡ 1): the order of 3 is 3. This order always divides the number of elements of the group, here 12.