Primitive roots

cobijones

Can anyone explain to me the concept of primitive roots?
I tired here http://www.brynmawr.edu/math/people/stromquist/numbers/primitive.html and on wikipedia but I cant understand whats going on.

Son Goku

cobijones wrote:

Can anyone explain to me the concept of primitive roots?
I tired here http://www.brynmawr.edu/math/people/stromquist/numbers/primitive.html and on wikipedia but I cant understand whats going on.

Take prime and take another number, let's call it x.
Then collect all the powers of x into a list.
Then take the modulus of the list. If every number lower than the prime except 0 appears in the list, then x is a primitive root of that prime.

To use the example in the link. If the prime is 7 and the number is 3:

The powers of 3 are:
1,3,9,27,81,243,................

The modulus 7 of this list is
1,3,2,6,4,5,...............

Every number less than 7 except 0 appears in this list so 3 is a primitive root of 7.

cobijones

Thanks Son Goku

cobijones

I dont really understand the modulo part, I cant see where they come from?

If for instance the prime was 11 and the number was 3 could you tell me what the outcome would be?

Michael Collins

Modulo Arithmetic means the remainer left after division by an integer. Like for example in the case of Modulo 7 we have:

1 mod 7 = 1: 7 divides into 1 no times with a remainder of 1
3 mod 7 = 3: 7 divides into 3 no times with a remainder of 3
9 mod 7 = 2: 7 divides into 9 once with a remainder of 2
27 mod 7 = 6: 7 divides into 27 thrice with a remainder of 6
...and so on

You can check it out for 11 yourself...

dr.bollocko

I have a great great great great great great uncle who swore he was born half gorilla.
Primitive roots there...

Michael Collins

dr.bollocko wrote:

I have a great great great great great great uncle who swore he was born half gorilla.
Primitive roots there...

I see why you got your name

cobijones

Would I be correct in saying that 3 is NOT a primitive root of 11 because the powers of 3 are:
1,3,9,27, 81, 243 , 729 , 2187 , 6561, 19683, 59049.........

and the modulus of 11 are

1 mod 11 = 1
3 mod 11 = 3
9 mod 11 = 9
27 mod 11 = 5
81 mod 11 = 4
243 mod 11 = 1
729 mod 11 = 3
2187 mod 11 = 9
.........

Michael Collins

Yep, looks right to me. Not a primitive root because 7, 8 & 10 are not there. I think you'll find that 2 is though.

cobijones

Thanks Michael Collins.