# show if $n=4k+3$ is a prime and ${a^2+b^2} \equiv 0 \pmod n$ , then $a \equiv b \equiv 0 \pmod n$

$n = 4k + 3$

We start by letting $a \not\equiv 0\pmod n$ $\Rightarrow$ $a \equiv k\pmod n$ .

$\Rightarrow$ $a^{4k+2} \equiv 1\pmod n$

Now, I know that the contradiction will arrive from the fact that if we can show $a^2 \equiv 1 \pmod n$ then we can say $b^2 \equiv -1 \pmod n$ then it is not possible since solution exists only for $n=4k_2+1$ so $a \equiv b\equiv 0 \pmod n$

So from the fact that $a^{2^{2k+1}} \equiv 1 \pmod n$ I have to conclude something.

-

Hint: If $p \equiv 3 \pmod{4}$, then $x$ is a quadratic residue $\bmod{p}$ if and only if $-x$ is a quadratic nonresidue $\bmod{p}$.

Edit, to be more direct:

Lemma: Suppose that $p$ is an odd prime, and assume that $x$ is a nonzero quadratic residue $\bmod{p}$. Then, $-x$ is a quadratic residue $\bmod{p}$ if and only if $p \equiv 1 \pmod{4}$.

Proof:

First suppose that $p \equiv 1 \pmod{4}$. By assumption, as $x$ is a nonzero quadratic residue, there exists an integer $a \neq 0$ such that $a^2 = x$. Since $-1$ is also a quadratic residue, there also exists an integer $b$ such that $b^2 = -1$. Thus, $$-x = -1 x = b^2 a^2 = (ba)^2,$$ and hence $-x$ is a quadratic residue.

On the other hand, suppose that $p \equiv 3 \pmod{4}$ and $x = a^2$ is a quadratic residue. Since $x \neq 0$, it follows that $-x \neq 0$ as well. Then, suppose for a contradiction that $-x$ is also a nonzero quadratic residue, and hence $-x = c^2$ for some $c$. If this were the case, it would follow that $$-1 = -x/x = c^2/a^2 = (c/a)^2$$ which would imply that $-1$ is a square $\bmod{p}$. This gives a contradiction, and we conclude that if $p \equiv 3\pmod{4}$ and $x$ is a nonzero quadratic residue, then $-x$ must be a quadratic nonresidue.

-
This makes sense but we're not supposed to use a quadratic residue result yet. Maybe I should read the proof of this statement and try deriving it. – Rohan Feb 2 '12 at 18:16
Are you aware of the result that if $p \equiv 3\pmod{4}$, then $-1$ is not a square $\bmod{p}$? – JavaMan Feb 2 '12 at 18:18
Yes. the equation has a solution iff $p=4k+1$ – Rohan Feb 2 '12 at 18:24
If $x$ is a square and $-x$ is square, then (assuming $x \neq 0$), it must be that $-x/x = -1$ is also a square (this follows since $m^2/n^2 = (m/n)^2$). However, $-1$ cannot be a square since $p \equiv 4k + 3$. Thus, $-x$ also cannot be a square. – JavaMan Feb 2 '12 at 18:27
I get this but $a^2 \equiv k \pmod n$ and not necessarily $a^2 \equiv 1 \pmod n$ . – Rohan Feb 2 '12 at 19:20

Assume that $a$ and $b$ are coprime. If $a$ and $b$ are odd, replace $a$ and $b$ by $(a-b)/2$ and $(a+b)/2$. Then $a^2 + b^2 = pm$, and by reducing $a$ and $b$ modulo $p$ you can make sure that $m < p$. Since $p = 4n+3$ and $a^2 + b^2 = 4k+1$, we must have $m = 4j+3$. But then $m$ is divisible by a prime number $q = 4r+3$ strictly smaller than $p$. Repeat until you find that $3$ is a sum of two squares.

-

You are on the right track, the problem is that you don't know what $a^2$ is to relate it to $b^2$.

Hint Can you relate somehow $a^{4k+2} \equiv 1\pmod n$ to $b$?

Edit: Since you figured it, here is the complete solution.

First note that if we prove $a \equiv 0\pmod p$ it follows imediately that $b$ is also $0 \pmod p$.

Thus it is enough to prove that $a \equiv 0 \pmod p$. Assume by contradiction that is not true. Then, since $p$ is prime, by Fermat Little Theorem,

$$1=a^{p-1}=a^{4k+2}=(a^2)^{2k+1}=(-b^2)^{2k+1} =(-1)^{2k+1}b^{4k+2}=-b^{4k+2} (*)$$

But $b^2= -a^2$ is invertible, thus $b \neq 0 \pmod p$. Hence

$$b^{4k+2}=b^{p-1} = 1 \pmod p$$

Thus $(*)$ implies $1=-1 \pmod p$, contradiction.

-
${{(-b^2)}^{2k+1}} \equiv 1 \pmod n \Rightarrow {b}^{2^{2k+1}} \equiv {-1} \pmod n$ which implies $1 \equiv {-1} \pmod n$ hence contradiction . It sounds fine to me. Is it good? – Rohan Feb 2 '12 at 18:21
Yep, that's it. I added the details. – N. S. Feb 3 '12 at 2:23

p is prime / p=4k+3 if: p=xˆ2 +2*yˆ2 if: p = 3 (mod 8) and p = xˆ2 -2*yˆ2 if: p = 7 (mod 8) / p=xˆ2-c*yˆ2 / c=-2 if p=3 mod 8 and c=2 if p=7 mod 8

and exist a in (1,p-1) / (+-a)ˆ2=c (mod p) and: if p=3 mod 8 then not exist x´ and y´ / p (not= ) x´ˆ2+2*yˆ2 if p=7 mod 8 then not exist b in (1,p-1) / (+-b)ˆ2 not congruent with c mod p

examples: 1) p=11= [3]ˆ2 +2*[1]ˆ2 c=-2 and mcd[3,1]=+-1 exist a/aˆ2=-2 mod p / a=3 (and p-3) 2) p=27= [3]ˆ2 + 2*[3]ˆ2=[5]ˆ2+2*[1] then p not prime because exist x´... 3) p=23 c=2 only exist a=23 / (+-a)ˆ2=2 mod p if exist b not a / (+-b)ˆ2 mod p then p not prime if you want send me a email: miguelangelreybonet@yahoo.es

-
@miguel rey, Welcome to SE. Please write your posts using LaTeX, the answer is illegible. – Sepideh Bakhoda Jan 22 '14 at 11:27
Also, I strongly advise you not to make your email adress public. Anyone can read this, so this makes your email easily accessible for spam bots. – barto Jan 22 '14 at 21:20

This is solution from Prasolov V.V. Zadachi po algebre, arifmetike i analizu (В. В. Прасолов. Задачи по алгебре, арифметике и анализу.) This book (in Russian) is freely available at http://www.mccme.ru/free-books/

The problem appears there as Problem 31.2.

We want to show that if $p=4k+3$ is a prime number and $p\mid a^2+b^2$, then $p\mid a$ and $p\mid b$.

My translation of the solution given there:

Suppose that one of the numbers $a$, $b$ is not divisible by $p$. Then the other one is not divisible by $p$, either. Thus from Fermat's little theorem we get $a^{p-1} \equiv 1 \pmod p$ and $b^{p-1} \equiv 1 \pmod p$. This implies $a^{p-1}+b^{p-1} \equiv 2 \pmod p$.

On the other hand, the number $a^{p-1}+b^{p-1}=a^{4k+2}+b^{4k+2}=(a^2)^{2k+1}+(b^2)^{2k+1}$ is divisible by $a^2+b^2$, and thus it is divisible by $p$.

-