I have no idea how to do this problem; please consider helping me:
If $3|(a^2 + b^2)$, show that $3|a$ and $3|b$.
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.Sign up to join this community
The key point is that if $3$ does not divide $x$, then $x^2$ leaves remainder $1$, because $x$ is of the form $3k\pm1$. Therefore:
If $3$ divides $a$ but not $b$ (or vice-versa), then $a^2+b^2$ leaves remainder $1$.
If $3$ divides neither $a$ nor $b$ then $a^2+b^2$ leaves remainder $2$.
So, the only way for $3$ to divide $a^2+b^2$ is for $3$ to divide both numbers.
From $3\mid a^2+b^2$ we get $a^2\equiv -b^2\pmod 3$. Now assume that $3\nmid a,b$, then because $3$ is prime we get $\gcd(3,a)=\gcd(3,b)=1$. Hence we may divide the first congruence by either $a$ or $b$ (let's do $b$) to get $(a/b)^2\equiv -1\pmod 3$. Hence $-1$ is a quadratic residue mod $3$, contradiction. Thus $3\mid a,b$.
Say $a = 3k_1 + i_1$ and $b = 3k_2 + i_2$, where $0\leq i_1, i_2< 3$. Then we have $$ a^2 = (3k_1^2 + i_1)^2 = 9k_1 + 6i_1k_1 + i_1^2 = 3(3k_1^2 + 2 k_1i_1) + i_1^2 $$ and similarily, we have $$ b^2 = 3(3k_2^2 + 2k_2i_2) + i_2^2 $$ Now, each of $i_1$ and $i_2$ are either $0, 1$ or $4$, and you can verify by checking each case that if one or both of them are not $0$, then $i_1^2 + i_2^2$ is not divisible by $3$.