• Support PF! Buy your school textbooks, materials and every day products Here!

Primitive roots?

  • Thread starter pivoxa15
  • Start date
2,234
1
Can a number have more than 1 primitive root?

Thanks
 
Last edited:

Answers and Replies

Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,843
17
This one's not too hard to work out for yourself: what's the defining property of a primitive root?
 
2,234
1
From the name, I get the impression that there should be only one primitive root for each number but there are more due to the definition that a primitive root exists when the primitive root to the power of phi(n) has a remainder of 1 when divided by n.

Finding the primitive of a number, n (if it exists) is quiet a long process of trial and error is it not?
 
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,843
17
The "primitive" part of saying that a is a primitive root modulo n means that that every number m relatively prime to n can be written as m = a^k (mod n) for some integer k.

As I recall, there are quite a lot of them, so you just try things randomly, and you'll find one fairly quickly.
 
2,234
1
What do you mean by relatively prime?

How many numbers do have to try to ensure this number has no primitive roots?

Thanks Hurkyl
 
2,234
1
Also, prime numbers always have at least one primitive root but do they have infinitely many?

Are one primitive root usually prefered to another?
 
2,234
1
One excercise was find the primitive root of 12.

I did it by trying to find a number 'a' where the ord of the number 'a' to the base 12 equal phi(12)

phi(12) = 2

and so I found 5^2 is congruent to 1 (mod 12). The power of 5, that is 2 is also the smallest power for which 5^i is congruent to 1 (mod 12).

the gcd(5,12)=1

Hence i=phi(12)=ord5(mod12) which matches the definition of primitive root. 'a' or the primitive root therefore is 5.



But the back of the book said that 12 has no primitive root.

Is the book wrong or am I wrong?

Thanks
 
Last edited:
matt grime
Science Advisor
Homework Helper
9,394
3
the elements relatively prime to 12 are, 1,5,7,11, so pih(12)=4, not 2. square any element in there and you get 1 mod 12, hence there is no primitive root (something of order 4).

in general p^n where p is any prime and 2p^n 4 are the only numbers that have primitive roots i think. (hard to prove)

if a is any primitive root mod n then so is a^k where k is relatively prime with n. (easy to prove)
 

Related Threads for: Primitive roots?

  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
24
Views
3K
Replies
3
Views
2K
  • Last Post
Replies
13
Views
7K
Replies
14
Views
23K
  • Last Post
Replies
7
Views
3K
Top