1. ## two-square problem

Let $A_1,A_2$ be two quadratic residues of the $(4k+3)-$prime $p$ that satisfy $0. Prove that $A_1+A_2=0$ (mod $p$) is impossible.

The hint says to use the theorem " $N=a^2+b^2$ if and only if no $(4k+3)-$prime in the factorization of $N$ occurs to an odd power.

Suppose $A_1+A_2=0$ (mod $p$). Since $A_1,A_2$ are two quadratic residues of the $p=4k+3$, $x^2=A_1$ (mod $p$) and $y^2=A_2$ (mod $p$). So $x^2+y^2=0$ (mod $p$). So $x^2+y^2=mp$ for some $m \in \mathbb{N}$.
I also know that $0, so $A_1+A_2<2p \implies A_1+A_2=p$.
I think I should end up contracting the theorem above, but I'm kinda stuck.. can I get some help please?

2. Originally Posted by dori1123
Let $A_1,A_2$ be two quadratic residues of the $(4k+3)-$prime $p$ that satisfy $0. Prove that $A_1+A_2=0$ (mod $p$) is impossible.

The hint says to use the theorem " $N=a^2+b^2$ if and only if no $(4k+3)-$prime in the factorization of $N$ occurs to an odd power.

Suppose $A_1+A_2=0$ (mod $p$). Since $A_1,A_2$ are two quadratic residues of the $p=4k+3$, $x^2=A_1$ (mod $p$) and $y^2=A_2$ (mod $p$). So $x^2+y^2=0$ (mod $p$). So $x^2+y^2=mp$ for some $m \in \mathbb{N}$.
I also know that $0, so $A_1+A_2<2p \implies A_1+A_2=p$.
I think I should end up contracting the theorem above, but I'm kinda stuck.. can I get some help please?

I think you already proved but you didn't noticed... :

Since $A_1=x^2\!\!\!\!\pmod p\,,\,A^2=y^2\!\!\!\!\pmod p$, then $0=A_1+A_2\!\!\!\!\pmod p\,\Longrightarrow\,x^2+y^2=0\!\!\!\!\pmod p$ , and thus you have expressed a multiple of $p$ less than $p^2$ (why?)

as a sum of squares, which is impossible by the theorem in the hint that you quote.

Tonio

3. Originally Posted by tonio
... multiple of $p$ less than $p^2$ (why?)

as a sum of squares, which is impossible by the theorem in the hint that you quote.

Tonio
This is where I'm stuck, how do I know $mp ?

4. Originally Posted by dori1123
This is where I'm stuck, how do I know $mp ?

Because we're given $A_1\,,\,A_2

Tonio

5. Can't we simply say that $p \mid x^2+y^2$ is a contradiction since $p$ is of the form $4n+3$?

6. Originally Posted by chiph588@
Can't we simply say that $p \mid x^2+y^2$ is a contradiction since $p$ is of the form $4n+3$?

Of course, and that's the point. Nevertheless, the OP had the problem to show that $x^2+y^2$ doesn't equal $p^2\,,\,2p^2$ or something that'd have a prime of the form $4n+3$ to an even power...

For example, $3\mid 3^2+6^2$...

Tonio