Primitive Roots: Multiple Possibilities?

In summary, a number can have more than 1 primitive root. Finding the primitive of a number is a long process of trial and error, and prime numbers always have at least one primitive root.
  • #1
pivoxa15
2,255
1
Can a number have more than 1 primitive root?

Thanks
 
Last edited:
Physics news on Phys.org
  • #2
This one's not too hard to work out for yourself: what's the defining property of a primitive root?
 
  • #3
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?
 
  • #4
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.
 
  • #5
What do you mean by relatively prime?

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

Thanks Hurkyl
 
  • #6
Also, prime numbers always have at least one primitive root but do they have infinitely many?

Are one primitive root usually preferred to another?
 
  • #7
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:
  • #8
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)
 

1. What are primitive roots?

Primitive roots are numbers that when raised to certain powers, called indices, result in all possible remainders when divided by a prime number. In other words, they are numbers that generate all the elements of a cyclic group.

2. How can I find primitive roots?

There are several methods for finding primitive roots, including brute force testing, the primitive root theorem, and the index calculus method. These methods involve checking powers of numbers and using modular arithmetic to determine if they are primitive roots.

3. How many primitive roots are there?

The number of primitive roots for a prime number p depends on the value of p. For example, if p is a prime number, there are always φ(p-1) primitive roots, where φ is the Euler totient function. This means that there are multiple possible primitive roots for a given prime number.

4. Are primitive roots important in cryptography?

Yes, primitive roots are essential in cryptography and are used in a variety of encryption algorithms. They are used to create large, random-looking numbers that are difficult to break, making them useful for generating secure keys and codes.

5. Can a non-prime number have primitive roots?

No, only prime numbers have primitive roots. This is because for a number to have primitive roots, it must be a cyclic group, and only prime numbers have this property. Non-prime numbers can have elements that act as generators, but they are not considered primitive roots.

Similar threads

  • Science and Math Textbooks
Replies
1
Views
557
Replies
5
Views
839
  • Atomic and Condensed Matter
Replies
4
Views
2K
  • Atomic and Condensed Matter
Replies
1
Views
859
  • Introductory Physics Homework Help
Replies
14
Views
505
Replies
4
Views
611
  • Science and Math Textbooks
Replies
2
Views
904
Replies
1
Views
1K
Replies
1
Views
952
  • Introductory Physics Homework Help
Replies
5
Views
1K
Back
Top