If $(a,b)=1$ and $p \mid a^{2}+b^{2}$ why can one assume that $|a| < \frac{p}{2}$

Question

There is a part of Euler's infinite descent proof I can't seam to get; If $(a,b)=1$ and $p \mid a^2+b^2$ why can one assume that $|a| < \frac{p}{2}$ and $|b| < \frac{p}{2}$ ?

Answer 1

Suppose $p$ is odd, then since $(a-kp)^2\equiv a^2 \mod p$ you can replace $a$ with its least non-negative residue modulo $p$, say $a'$.

If $a'\gt \frac p2$ then you can likewise replace $a'$ with $(p-a')\lt \frac p2$. Since $p$ is odd and $a'$ is an integer, the case $a'=\frac p2$ cannot occur.

In this way, if you can solve the equation at all, you can always find a solution where the value of $a$ satisfies $|a|\lt \frac p2$

Answer 2

The other answer is correct, but let me shed light on something that seems to be missing in a bigger picture here.

The argument here is a part of the "descent step" step in Fermat's proof of: an odd prime $p$ can be written as $p=a^2+b^2$ iff $p \equiv 1\pmod 4$. The descend step itself says:

If a prime $p$ divides a number $N$ of the form $N=a^2+b^2$, where $(a,b)=1$, then $p$ itself can be written as $p=x^2+y^2$ for some $(x,y)=1$.

The argument does not really care which $a,b$ are choosen as long as any $a,b$ exist. And since it can be shown (see the other answer) that replacing $a$ or $b$ by a multiples of $p$ the conditions still holds, we can change and relabel $a$ and/or $b$ without loss of generality to get ones that satisfy the desired bound. Then the subsequent argument uses this pair of $a,b$.

Answer 3

We must assume $p$ odd (otherwise, we should have to allow $|a|=p/2$). Then, there exist integers $a',b'\in[0,p/2)$ such that $a\equiv\pm a'\bmod p$ and $b\equiv\pm b'\bmod p$, which implies $p\mid a'^2+b'^2.$

However (and this detail was missing in the previous answers) $d:=\gcd(a',b')$ is not necessarily equal to $1.$ But we shall remedy this easily.

Write $a'=da'',b'=db''.$ Then, $$a'',b''\in[0,p/2),\quad\gcd(a'',b'')=1,$$ and $p\mid d^2(a''^2+b''^2).$ Now, since $\gcd(a,b)=1,$ $p$ has no common factor with $d,$ so $$p\mid a''^2+b''^2.$$