# Primes, congruent, Fermat squares

I need some proof or procedure to solve the question:

For given n = 1 or > 1, We know by fermat, $p = x^2 + ny^2$ for an odd prime $p$. Now, can we proof the

(a) $(-n/p) = 1$ and $(p/q) = 1$ for every odd prime $q\mid n$?

(b) $p \equiv 1 \pmod{4}$ for $n \equiv 0, 1 \pmod{4}$?

(c) $p \equiv 1 \pmod{8}$ for $8\mid n$?

The proofs of the above problem will answer many questions easily, especially primes of the form $p = x^2 + ny^2$. So, kindly discuss the proofs.

-
This post is possibly related. – Old John Aug 22 '12 at 9:57

can you explain the notation $(-n/p)$?

By the way, is this homework?

Concerning $(b)$ and $(c)$, take a look at the groups $\mathbb{Z}/4\mathbb{Z}$ and $\mathbb{Z}/8\mathbb{Z}$, square each element, and see which values are possible. You'll see that if you also use the fact that $p$ is odd, the results $(b)$ and $(c)$ follow easily.

I leave it to you as an exercise on purpose, its really useful to find this out for yourself, but let me know if you need more hints!

Edit:

$(b)$: First of all, $\mathbb{Z}/4\mathbb{Z}$ has \begin{align*} 0^2=2^2 = 0\\ 1^2=3^2=1 \end{align*} So an even square is zero, an odd square is one.

Two cases. If $n \equiv 0$ (mod 4), then $ny^2 \equiv 0$ (mod 4) and in particular $ny^2$ is even. Since $p$ is odd, $x^2$ (and hence $x$ itself) must be odd. Then $x^2 \equiv 1$. Hence \begin{align*} p &= x^2 + ny^2\\ &\equiv 1 + 0\\ &\equiv 1 \end{align*}

If $n \equiv 1$ (mod 4), then $p \equiv x^2 + y^2$. The sum of two odd numbers or two even numbers is even, since $p$ is odd we know either $x$ is odd and $y$ is even or the other way around. In any case we find by the inspection of squares in $\mathbb{Z}/4\mathbb{Z}$ above that $p \equiv 1 + 0 \equiv 1$ as desired.

Notice that strictly speaking i was working modulo 2 most of the time in the last argument. Formally i could have argued that $n \equiv 1$ (mod 4) implies $n \equiv 1$ (mod 2) and hence $p \equiv x^2 + y^2$ (mod 2), from which the statement of the parity of $x$ and $y$ follows. Then, we return to working modulo 4 again: the value of a number modulo 2 is of course not enough to determine its value modulo 4, but as we saw above, we are able to find the value of the square of the number modulo 4, just by knowing its value modulo 2. Since we are only interested in the values of the squares, this suffices.

Now $(c)$. We determine the squares in $\mathbb{Z}/8\mathbb{Z}$. Noticing that $5 \equiv -3$ hence $5^2 \equiv 3^2$ and similarly $7^2 \equiv (-1)^2 \equiv 1^2$, we can quickly see that all odd numbers square to one (In fact this shows that $\mathbb{Z}/8\mathbb{Z}^*$ is the Klein four group). Now $8 | n$ is a reformulation of $n \equiv 0$ (mod 8), which certainly implies $ny^2$ is even, and again since $p$ is odd we know $x^2$ and hence $x$ must be odd. Putting this together we see \begin{align*} p &= x^2 + ny^2\\ &\equiv 1 + 0\\ &\equiv 1 \end{align*}

Modulo 8 of course, as desired. Whereever i left out the (mod ...) notation i assume it to be clear modulo which number we work.

Hope this clears it up.

-
JOACHIM! here (x, y) =1. Before that, if you can prove for (n, p) =1 and (x, y) =1, p divides $x^2$+n$y^2$ then (-n/p) = 1. Of course we are talking about quadratic reciprocity. Still, I need complete help in the above problem. – vidyaojal Aug 22 '12 at 10:39
JOACHIM! Still I need more explanation or hints or complete proof of the above post. Kindly explain. – vidyaojal Aug 22 '12 at 10:41
It's a bit odd to accept an answer you don't understand. – Gerry Myerson Aug 22 '12 at 13:17
I'll get back to it soon, its bedtime in my time zone.. In the meantime, could you confirm that its not a homework question? – Joachim Aug 23 '12 at 19:43
JOACHIM! It is not homework question. – vidyaojal Aug 24 '12 at 4:38

Assuming that your notation $(-n/p)$ means the Legendre symbol, you can use the following argument to prove the first of your result (a):

If $p = x^2+ny^2$ then $0 \equiv x^2+ny^2 \pmod{p}$, so that $-ny^2 \equiv x^2 \pmod{p}$, which shows that $-n$ must be a quadratic residue of $p$. (Note that we can multiply both sides by $y^{-2}$, since clearly $y$ is invertible $\pmod{p}$.)

To complete the proof of (a), suppose that $q$ is a prime dividing $n$, so that $n \equiv 0 \pmod{q}$. Then $p-x^2 \equiv ny^2 \equiv 0 \pmod{q}$, and so $p \equiv x^2 \pmod{q}$, which means that $p$ must be a quadratic residue of $q$, in other words $(p/q) = 1$.

The other parts can be completed using the hints provided above by Joachim.

-
OLD John! is not impressed. – vidyaojal Aug 24 '12 at 13:48
@vidyaojal I am not sure I understand what you mean by that cryptic comment. If there is something mathematically wrong with what I posted, perhaps you could explain? – Old John Aug 24 '12 at 14:13