# Primitive root question

• Nov 9th 2011, 08:40 PM
jzellt
Primitive root question
According to my book, 2 is a primitive root of 11 because:

phi(11) = 10. 2^2 = 4 mod 11. 2^5 = -1 mod 11. 2^10 = 1 mod 11
That's the whole explanation.

I used to same logic to find a primitive root of 17.

phi(17) = 16. 2^2 = 4 mod 17. 2^4 = -1 mod 17. 2^8 = 1 mod 17. 2^16 = 1 mod 16.
But 2 is NOT a primitive root of 17???

Whats going on here?
• Nov 9th 2011, 09:17 PM
Deveno
Re: Primitive root question
the order of an element, has to divide the order (size) of the entire group of units.

for 11, U(11) has 10 elements, so the possible orders of elements of U(11) (which are all the integers mod 11 save 0, because 11 is prime), are 1,2,5 and 10.

only 1 will have order 1. 2^2 = 4 ≠ 1, so 2 doesn't have order 2. 2^5 = -1 (or 10, doesn't matter), so 2^5 does not have order 5. that just leaves 10, and 2^10 = 1, as expected

(all these values are mod 11, of course).

now U(17) has 16 elements. possible orders are 1,2,4,8 or 16.

while it is true that 2^16 = 1, that does not mean 2 has order 16. why? because 2^8 = 1, and 8 < 16, so 2 has order 8.

not every element of U(17) will have order 16. for example 2^4 = 16 (mod 17). as you can easily see, 16 only has order 2.

the upshot of this, is that 2 does not generate the entire set of units via powers, the powers of 2 are:

{2,4,8,16,15,13,9,1}, which is only half of U(17) = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}.
• Nov 9th 2011, 11:44 PM
Opalg
Re: Primitive root question
How do you find a primitive root of 17? Well, you have already found that 2 has order 8. So if you can find an element x such that $x^2=2\pmod{17},$ then x will have order 2*8=16 in U(17) and will therefore be a primitive root.
• Nov 10th 2011, 12:18 AM
Deveno
Re: Primitive root question
and looking at integers of the form 17k+2, we have:

2, 19, 36...i think i see a winner....