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

Elementary Proof

  1. Sep 1, 2006 #1


    User Avatar

    Remove the last digit from a number and subtract twice this digit from the new (shorter) number. Show that the original number is divisible by 7 iff this difference is divisible by 7.

    I have only the division algorithm and the fact that the integers are closed under addition/multiplication/subtraction to work with plus elementary arithmetic. By the way, all numbers are in base 10

    Heres what I've got:
    let n be an integer. By the division algorithm I can find an integers c,d s.t. n = 10c + d where 0<= d < 10

    The number 10c is n with the last digit removed. We need to show 10c + d is divisble by 7 iff 10c - 2d is divisible by 7

    Suppose 10c + d is divisble by 7. Then 10c + d = 7m for some integer m.

    using the division algorithm we can find integers e,f st. d = 7e + f where
    0<= f < 7

    given the restrictions that 0<=d<10 we must have e = 0 or 1.

    Here's where I'm stuck. Any suggestions?
  2. jcsd
  3. Sep 1, 2006 #2
    No, 10c is n with the last digit replaced with a zero. You want to consider c - 2d.

    This proof can be done like so (using various elementary divisibility properties):

    c - 2d is divisible by 7
    10c - 20d is divisibly by 7
    10c - 20d + 21d is divisibly by 7
    10c + d is divisible by 7
    n is divisible by 7.

    If you had modular arithmetic in your inventory, this type of problem would be routine.
  4. Sep 1, 2006 #3


    User Avatar

    Thank you muzza! I really need to get rid of this extra chromosome!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook