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 [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!

 

[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.