Number Theory - Primitive Roots

In summary, the question is asking for which values of a (in terms of the primitive root g) does the equation x^2 ≡ a (mod n) have solutions, given that n has a primitive root g. The conversation discusses potential strategies for solving the problem, including looking at even powers of g and concrete examples. A potential solution is mentioned, but it is not proven and does not fully solve the problem.
  • #1
mattmns
1,128
6
Here is the question:
-----------
Suppose n has a primitive root g. For which values of a (in terms of the primitive root g) does the equations [itex]x^2 \equiv a \ \text{(mod n)}[/itex] have solutions?
-----------

I really don't have much of an idea of how to even begin this one. Let g be a primitive root mod n, so [itex]g^{\phi(n)} \equiv 1 \ \text{(mod n)}[/itex] and if [itex]g^N \equiv 1 \ \text{mod n}[/itex] then [itex]\phi(n) \mid N[/itex]. I am not sure how this fits in. Perhaps if (a,n)=1 we can do something (like using that [itex]g^i \equiv a \ \text{mod n}[/itex] for some i)? If a is a perfect square then we can do something. I guess I can see many options for breaking into cases (with a, or with n), but none seem all that nice. Should I maybe be looking at [itex](x-a)(x+a) \equiv 0 \ \text{mod n}[\itex]? I think I will try a concrete example and see if anything stands out. Any ideas would be appreciated, thanks!
 
Physics news on Phys.org
  • #2
What do the even powers of g look like? (You may want to look at the case n>2 so that [itex]\phi(n)[/itex] is even.)
 
  • #3
I am not sure I understand what you mean; how I am supposed to look at the even powers of g? I am not sure if I am missing something obvious, but I think of g^2 as g^2, and g^4 as g^4, I can't really see anything special (though I am sure I am missing something).

I started looking at some concrete examples, and found something interesting (to me at least). It seems as though if a is a primitive root mod m, then the congruence does not have a solution. (that is, [itex]x^2 \equiv a \ \text{mod n}[/itex] does not have a solution when [itex]a = g^i \ \text{where} \ (i,\phi(n))=1[/itex]). Though I can't seem to prove this, and this does not complete the problem anyway, but seemed an interesting coincidence.edit... Hmm, I just might see what you are getting at. Since [itex]\phi(n)[/itex] is even, we know that g to an even power is never a primitive root. Perhaps a = g^b where b is even always has a solution.
 
Last edited:

1. What is a primitive root in number theory?

A primitive root in number theory is a number that, when raised to different powers, generates all the possible values in a given modular arithmetic system. It is also known as a primitive element or primitive generator.

2. How do you find a primitive root?

To find a primitive root, you need to first determine the totient function of the modulo. Then, you need to find the prime factors of the totient function and test each number less than the modulo that is relatively prime to the totient function. If none of the numbers satisfy the criteria for a primitive root, then a primitive root does not exist for that modulo.

3. What is the relationship between primitive roots and prime numbers?

There is a direct relationship between primitive roots and prime numbers. Every prime number has at least one primitive root, and a primitive root exists for a composite number only if all of its prime factors also have primitive roots.

4. Can a primitive root be a non-prime number?

Yes, a primitive root can be a non-prime number. For example, 10 is a primitive root modulo 23, even though it is not a prime number. However, not all non-prime numbers are primitive roots for a given modulo.

5. What is the significance of primitive roots in cryptography?

Primitive roots play a crucial role in cryptography, particularly in the Diffie-Hellman Key Exchange algorithm. This algorithm relies on the difficulty of calculating discrete logarithms in a finite field, which is made possible by the existence of primitive roots. Additionally, primitive roots are used in other cryptographic systems for generating random numbers and ensuring secure communication.

Similar threads

  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
786
  • Calculus and Beyond Homework Help
Replies
11
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
16
Views
1K
Replies
5
Views
892
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Science and Math Textbooks
Replies
1
Views
672
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
Back
Top