- #1

mattmns

- 1,128

- 6

-----------

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!