Number Theory - Primitive Roots

  • Thread starter mattmns
  • Start date
  • #1
1,085
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!
 

Answers and Replies

  • #2
morphism
Science Advisor
Homework Helper
2,015
4
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
1,085
6
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:

Related Threads on Number Theory - Primitive Roots

  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
5
Views
7K
Replies
6
Views
667
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
9
Views
5K
  • Last Post
Replies
3
Views
688
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
4
Views
488
  • Last Post
Replies
2
Views
833
Top