Number Theory - Primitive Roots

In summary, the conversation discussed finding a primitive root modulo 19 and using it to find all primitive roots. It was determined that the order of 2 modulo 19 is 18, making it a primitive root. The idea of finding other primitive roots was discussed by looking for values of g that satisfy g^18 = 1, but not g^9 = 1 or g^6 = 1. This was explained by understanding the unit group of Z/19Z as a cyclic group of order 18.
  • #1
mattmns
1,128
6
Here is the question from the book:
------------
Determine a primitive root modulo 19, and use it to find all the primitive roots.
------------

[tex]\varphi(19)= 18[/tex]

And 18 is the order of 2 modulo 19, so 2 is a primitive root modulo 19, but I am not sure of how to use that to find all primitive roots modulo 19. My only idea is that we need to find what values of g satisfy [itex]g^{18} \equiv 1 \ \text{mod 19}[/itex]. However, I am not sure how to solve that equation. Any ideas? Thanks!
 
Physics news on Phys.org
  • #2
Well, you know that the unit group of Z/19Z is simply a cyclic group of order 18, right?

If that doesn't help, don't forget that g is a power of 2. Now, you know that everything in Z/19Z satisfies g^18 = 1... the things you're interested in are the things that do not also satisfy g^9 = 1 or g^6 = 1. (Do you see why?)
 
  • #3
Unfortunately I don't know much algebra, and our number theory class has not focused on the algebra behind it, so I don't really understand what you are saying.
 
  • #4
Z/19Z is simply the residue classes modulo 19.
 
  • #5
Thanks, now I see the idea behind it, and I see how to find the others. Seems kind of obvious now :redface:
 
  • #6
why are we interested in the things that DO not satisfy g^9 = 1 or g^6 = 1?
 

FAQ: Number Theory - Primitive Roots

1. What is a primitive root in number theory?

A primitive root of a prime number p is an integer a that generates all other integers relatively prime to p when raised to successive powers modulo p. In other words, all numbers an mod p are distinct for n ranging from 0 to p - 2.

2. How do you find primitive roots?

There is no known formula for finding primitive roots of a prime number p. However, it has been proven that a primitive root exists for every prime number p. One way to find primitive roots is to test different candidate numbers a and see if they satisfy the definition of a primitive root.

3. Can non-prime numbers have primitive roots?

No, only prime numbers have primitive roots. This is because the property of being a primitive root is closely related to the properties of prime numbers, such as having a limited number of factors and being relatively prime to all smaller numbers.

4. What is the significance of primitive roots in number theory?

Primitive roots have many applications in number theory, including in cryptography, prime number generation, and factorization algorithms. They also have connections to other important concepts such as discrete logarithms and the distribution of prime numbers.

5. Can a number have more than one primitive root?

Yes, some prime numbers have multiple primitive roots. For example, the prime number 11 has two primitive roots: 2 and 6. However, there are also prime numbers that have only one primitive root, such as 3 and 5.

Similar threads

Proving Primitive Roots of Odd Numbers Modulo pm
Replies
3
Views
1K
Number Theory (2) Homework: Find Integer Orders Modulo 19 & 17
Replies
2
Views
1K
MHB Number of natural numbers that have primitive roots
Replies
5
Views
1K
Number Theory What books or materials are needed to understand primitive roots?
Replies
1
Views
1K
Does Zp Contain Primitive Fourth Roots of Unity?: Investigating p
Replies
1
Views
2K
Formal Derivative and Multiple Roots
Replies
1
Views
2K
Extending a field by a 16th primitive root of unity
Replies
1
Views
1K
Are there any resources for questions on primitive roots?
Replies
2
Views
1K
Number theory: primitive roots
Replies
1
Views
2K
Proving 2 as a Primitive Root of Z_83: A Step-by-Step Approach
Replies
4
Views
1K

Hot Threads

Recent Insights

Back
Top