Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Help with a proof on divisibility

  1. Jul 11, 2011 #1
    1. The problem statement, all variables and given/known data

    Prove the following:
    If 5 divides [tex] a^2 + b^2 + c^2[/tex] then 5 divides a and 5 divides b and 5 divides c.

    2. Relevant equations

    [tex] 5 \mid a \implies a=5k , k \in Z [/tex]

    3. The attempt at a solution

    My idea is to assume 5 divides [tex] a^2 + b^2 +c^2[/tex]

    also assume that "5 does not divide a" or "5 does not divide b" or "5 does not divide c"

    then by the division algorithm, for some integers k,s,t

    [tex] a=5k+1 [/tex] or [tex] a=5k+2 [/tex] or [tex] a=5k+3 [/tex] or [tex] a=5k+4 [/tex]

    [tex] b=5s+1 [/tex] or [tex] b=5s+2 [/tex] or [tex] b=5s+3 [/tex] or [tex] b=5s+4 [/tex]

    [tex] c=5t+1 [/tex] or [tex] c=5t+2 [/tex] or [tex] c=5t+3 [/tex] or [tex] c=5t+4 [/tex]

    Now if we square each possibility for a, b, and c and add them together in each possible way, we would find that there is no possible combination that will give that 5 divides a^2 + b^2 + c^2. Then we would see that this is a contradiction so we must have that 5 divides a,b, and c. However, there must be an easier way than to have to manipulate 3^4 (i think) equations. Does anybody see a better way to go about this? or a quicker way to check all of the equations?
    Last edited: Jul 11, 2011
  2. jcsd
  3. Jul 11, 2011 #2
    Are you certain that your theorem is even correct?? Have you tried finding counterexample?
  4. Jul 11, 2011 #3
    You are absolutely right! I misread the problem. It says prove that 5 divides a or 5 divides b or 5 divides c. Thanks! This is much easier! Hah i feel stupid
  5. Jul 11, 2011 #4
    You probably want to try this on your own. But it may be worth to see what kind of remainders a2 can have when divided by 5...
  6. Jul 11, 2011 #5
    Yes that is exactly right. I have it figured out now. Thank you
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook