1. ## two-square problem

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

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

Suppose $\displaystyle A_1+A_2=0$ (mod $\displaystyle p$). Since $\displaystyle A_1,A_2$ are two quadratic residues of the $\displaystyle p=4k+3$, $\displaystyle x^2=A_1$ (mod $\displaystyle p$) and $\displaystyle y^2=A_2$ (mod $\displaystyle p$). So $\displaystyle x^2+y^2=0$ (mod $\displaystyle p$). So $\displaystyle x^2+y^2=mp$ for some $\displaystyle m \in \mathbb{N}$.
I also know that $\displaystyle 0<A_1<A_2<p$, so $\displaystyle 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 $\displaystyle A_1,A_2$ be two quadratic residues of the $\displaystyle (4k+3)-$prime $\displaystyle p$ that satisfy $\displaystyle 0<A_1<A_2<p$. Prove that $\displaystyle A_1+A_2=0$ (mod $\displaystyle p$) is impossible.

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

Suppose $\displaystyle A_1+A_2=0$ (mod $\displaystyle p$). Since $\displaystyle A_1,A_2$ are two quadratic residues of the $\displaystyle p=4k+3$, $\displaystyle x^2=A_1$ (mod $\displaystyle p$) and $\displaystyle y^2=A_2$ (mod $\displaystyle p$). So $\displaystyle x^2+y^2=0$ (mod $\displaystyle p$). So $\displaystyle x^2+y^2=mp$ for some $\displaystyle m \in \mathbb{N}$.
I also know that $\displaystyle 0<A_1<A_2<p$, so $\displaystyle 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 $\displaystyle A_1=x^2\!\!\!\!\pmod p\,,\,A^2=y^2\!\!\!\!\pmod p$, then $\displaystyle 0=A_1+A_2\!\!\!\!\pmod p\,\Longrightarrow\,x^2+y^2=0\!\!\!\!\pmod p$ , and thus you have expressed a multiple of $\displaystyle p$ less than $\displaystyle 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 $\displaystyle p$ less than $\displaystyle 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 $\displaystyle mp <p^2$?

4. Originally Posted by dori1123
This is where I'm stuck, how do I know $\displaystyle mp <p^2$?

Because we're given $\displaystyle A_1\,,\,A_2<p\,\Longrightarrow\,A_1+A_2<2p<p^2$

Tonio

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

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

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

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

Tonio