Thread: Can anyone think of a simpler way to do this or do I need to use brute force?

1. Can anyone think of a simpler way to do this or do I need to use brute force?

If 5 divides a^2+b^2+c^2, then 5 divides a or 5 divides b or 5 divides c.

I figured I would use the contrapositive. So I suppose 5 does not divide a nor b nor c. So each of a, b, and c are of the form 5k+1 or 5k+2 or 5k+3 or 5k+4. One method would involve taking all possibilities for each of a,b,c and showing that 5 does not divide the result. The problem is that I get something like 4^3 cases to compute, and so, this would take forever. Is there a simpler way?
Thanks.

2. Hello,

If you know it, you can work with congruencies. Let's do a proof by contradiction.


\begin{aligned}
x\equiv 0 \pmod 5& \Rightarrow &x^2 \equiv 0 \pmod 5 \\
x\equiv 1 \pmod 5& \Rightarrow &x^2 \equiv 1 \pmod 5 \\
x\equiv 2 \pmod 5& \Rightarrow &x^2 \equiv 4 \pmod 5 \\
x\equiv 3 \pmod 5& \Rightarrow &x^2 \equiv 4 \pmod 5 \\
x\equiv 4 \pmod 5& \Rightarrow &x^2 \equiv 1 \pmod 5 \end{aligned}

So is it possible, that by taking 3 numbers within {1,4} (since we don't want any of the number to be divisible by 5, i.e. $\equiv 0 \pmod 5$, to get a sum which is a multiple of 5 ?

3. Thanks, and while I do understand that, it is not covered in the book until the section or two after this problem appears, and so, our professor does not want us to use that yet. Is there another way?

4. You can sort of translate this argument to exclude explicit references to modular arithmetic.

Claim: the remainder of the square of any natural number divided by 5 is 0, 1, or 4.

Proof. It is enough to consider 0 through 9, because divisibility by 5 and the remainder is determined by the last digit, and the last digit of a square is determined by the last digit of the number. And so on.

5. ok...thanks