1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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?
    Thanks!
     
    Last edited: Jul 11, 2011
  2. jcsd
  3. Jul 11, 2011 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Help with a proof on divisibility
  1. Division Proof (Replies: 1)

Loading...