# Need help in understanding the question. Elemntary number theory

I have this question in my home assignment. I contains two parts and I don't quite understand what is the difference between them.

The question is:

Let $n > 2$ be an integer such that $(\mathbb{Z}/n\mathbb{Z}) \smallsetminus \{0\}$ has a primitive root. Show that:

• The equation $x^2 \equiv a\ (\mod{n})$ is solvable if and only if $a^{\frac{\phi (n)}{2} }\equiv 1 (\mod n)$.

• For a prime $p \geq 3$ and $j \geq 1$ the equation $x^2 \equiv a (\mod p^j)$ is solvable if and only if $a^{\frac{p^{j−1}(p−1)}{2} }\equiv 1 (\mod p^j)$.

My attempt to prove the first:
Let $\lambda \in \mathbb{Z}/n\mathbb{Z}$ be a solution for the congruence $x^2 \equiv a\ (\mod{n})$, then $$a^{\frac{\phi (n)}{2}} \equiv ({\lambda^2})^{\frac{\phi (n)}{2}} (\mod n) = \lambda^{\phi (n)}(\mod n)$$ Since $\lambda$ and $n$ are coprimes: $$\lambda^{\phi (n)} \equiv 1 (\mod n)$$ So we got $$a^{\frac{\phi (n)}{2}} \equiv 1 \mod n$$

Now, if $a^{\frac{\phi (n)}{2}} \equiv 1 \mod n$ then $a$ and $n$ are coprimes. Let $r$ be a primitive root $\mod n$ , then there is an $i< \phi (n)$ so that $a \equiv r^i \mod n$ . So $$r^{i \frac{\phi (n) }{2}} \equiv a^{\frac{\phi (n}{2}} \equiv 1 \mod n$$ By Lagrange's theorem, the order of $r$ divides $\phi (n)$ hence $i$ is even, we can write then - $r^i = r^{2j}$ . And from $a \equiv r^i \mod n$ we get $a \equiv r^{2j} \mod n$ so the solution for the equation is $x = r^j$.

For the second part, if $p \geq 3$ is a prime number, then $p^e$ has a primitive root, moreover, $\phi (p^e) = p^{e-1} (p-1)$, so I'm asking how is it different from the first part?

• I suppose you want to take $n=p^e$ and apply the first part to the second part. But does this $n$ then satisfy the assumption on the existence of a primitive root ? In general, not ! – Dietrich Burde May 19 '15 at 8:01
• I thaught it does (if p is an odd prime and it's exponent is positive.) – Uria Mor May 19 '15 at 8:06
• Yes, it does. But then you are using a result which is much more difficult than the whole question. – Dietrich Burde May 19 '15 at 8:57