Verify that 2 is a primitive root of 61 Solution This deals with the ring of \"r

Question

Explanation / Answer

This deals with the ring of "residues modulo N" for positive integral N > 1. This is isomorphic to the set { 0, 1, 2, ..., N - 1 } under the operations of addition modulo N and multiplication modulo N. The multiplicative identity is 1 (modulo N). The group of units is the subset that divide into 1 (modulo N), equivalently, the subset of { 0, 1, 2, ..., N - 1 } of elements which are relatively prime to N. g is a primitive root of N in the group of units precisely when the group is cyclic and g is a generator for that group. If the group of units is not cyclic, then N has no primitive roots. The multiplicative order of an element "a" of the group of units is the least exponent "e" = 1, 2, 3, ... such that a^e = 1 modulo N. So for example, modulo 15 the powers of 7 are 7, 49 or 4 modulo 15, 28 or 13 modulo 15, 91 or 1 modulo 15, so 7 has multiplicative order 4 in the group of units modulo 15. There are 8 units modulo 15 so 7 is not a primitive root modulo 15. In fact, no unit of N = 15 has multiplicative order 8, so N = 15 has no primitive roots. You can solve this two ways: find the group of units of N, counts is size (call it k), and check each unit noting how many (if any) have multiplicative order k. Or: recall that the group of units modulo N is cyclic if and only if N is a prime or twice a prime. Either way, you will find that only the prime 61 and the twice a prime 62 have primitive roots. The size of the group of units of N is N times the product of (1 - 1/p) for each prime divisor p of N. N = 61 is prime k = 61 * (1 - 1/61) = 61 * 60/61 = 60 (k is always N - 1 when N is prime) If you enumerate them, the primitive roots are 2 6 7 10 17 18 26 30 31 35 43 44 51 54 55 59 and so there are 16 of them. But you need not enumerate them to know how many there are: if g is a generator, then the elements are g = g^1, g^2, g^3, ..., g^e, ..., g^k-1, g^k = 1 (modulo N). The generators occur precisely when e is relatively prime to k. Here k = 60 and we know from above that the number of residues relative prime to 60 is 16.

Related Questions

Navigate

• Browse (All)
• Browse V
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.