1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Number Theory - Primitive Roots

  1. Mar 29, 2007 #1
    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!
  2. jcsd
  3. Mar 30, 2007 #2


    User Avatar
    Science Advisor
    Homework Helper

    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.)
  4. Mar 31, 2007 #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: Mar 31, 2007
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook