Number Theory - Primitive Roots

[mattmns]

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 x^2 \equiv a \ \text{(mod n)} 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 g^{\phi(n)} \equiv 1 \ \text{(mod n)} and if g^N \equiv 1 \ \text{mod n} then \phi(n) \mid N. I am not sure how this fits in. Perhaps if (a,n)=1 we can do something (like using that g^i \equiv a \ \text{mod n} 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 (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!

 

[morphism]

What do the even powers of g look like? (You may want to look at the case n>2 so that \phi(n) is even.)

 

[mattmns]

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, x^2 \equiv a \ \text{mod n} does not have a solution when a = g^i \ \text{where} \ (i,\phi(n))=1). 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 \phi(n) 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.