Track / Stage 5 / 107 of 400 #707 of 2000

Problem 707

AIME late

Number theory Difficulty 5.3 Prove it

31.2. Let $p=4k+3$ be a prime number. Prove that if $a^{2}+b^{2}$ is divisible by $p$ , then both numbers $a$ and $b$ are divisible by $p$ .

This one wants a proof. Work it on paper, read the official solution, then mark yourself honestly — the ladder only means something if the record is true.

Official solution

31.2. Suppose that one of the numbers $a$ and $b$ is not divisible by $p$ . Then the other number is also not divisible by $p$ . Therefore, according to Fermat's Little Theorem, $a^{p-1} \equiv 1(\bmod p)$ and $b^{p-1} \equiv 1(\bmod p)$ . Hence, $a^{p-1}+b^{p-1} \equiv 2(\bmod p)$ . On the other hand, the number $a^{p-1}+b^{p-1}=a^{4 k+2}+$ $+b^{4 k+2}=\left(a^{2}\right)^{2 k+1}+\left(b^{2}\right)^{2 k+1}$ is divisible by $a^{2}+b^{2}$ , so it is divisible by $p$ .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.