Results 1 to 4 of 4

Math Help - divisible by 11 proof

  1. #1
    Junior Member
    Joined
    Sep 2008
    Posts
    62

    divisible by 11 proof

    Prove that a positive integer n is divisible by 11 if and only if the integer obtained by alternately adding and subtracting its digits beginning with adding the units digit and working to the left is divisible by 11.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,408
    Let the digit representation of a number be: d_{k}d_{k-1}d_{k-2}...d_{2}d_{1}d_{0}

    Note that it can be represented as: d_{k}10^{k} + d_{k-1}10^{k-1} + d_{k-2}10^{k-2} + \hdots + d_{2}10^2 + d_{1}10 + d_{0}

    So all you have to show is that:
    d_{k}10^{k} + d_{k-1}10^{k-1} + d_{k-2}10^{k-2} + \hdots + d_{2}10^2 + d_{1}10 + d_{0}
    .................................................  \equiv d_{0} - d_{1} + d_{2} - d_{3} + \hdots + (-1)^{k}d_{k} \ (\text{mod } 11)

    Hint: 10^{k} \equiv (-1)^{k} \ (\text{mod 11})
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2008
    Posts
    62
    Quote Originally Posted by o_O View Post
    Let the digit representation of a number be: d_{k}d_{k-1}d_{k-2}...d_{2}d_{1}d_{0}

    Note that it can be represented as: d_{k}10^{k} + d_{k-1}10^{k-1} + d_{k-2}10^{k-2} + \hdots + d_{2}10^2 + d_{1}10 + d_{0}

    So all you have to show is that:
    d_{k}10^{k} + d_{k-1}10^{k-1} + d_{k-2}10^{k-2} + \hdots + d_{2}10^2 + d_{1}10 + d_{0}
    .................................................  \equiv d_{0} - d_{1} + d_{2} - d_{3} + \hdots + (-1)^{k}d_{k} \ (\text{mod } 11)

    Hint: 10^{k} \equiv (-1)^{k} \ (\text{mod 11})
    I have tired to do this for the past 1 hr and still cant mange to get the right answer!! Any more hints?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,408
    What are you having trouble with? Do you understand the idea behind the earlier post?

    Using the hint:
    d_{k}10^{k} + d_{k-1}10^{k-1} + d_{k-2}10^{k-2} + \hdots + d_{2}10^2 + d_{1}10 + d_{0} (1)

    ................................. \equiv d_{0} + d_{1}(-1) + d_{2}(-1)^2 + d_{3}(-1)^3 + \hdots + d_{j}(-1)^{j} + \hdots d_{k}(-1)^{k} \ (\text{mod } 11) (2) for some j : 0 \leq j \leq k

    You can see that every second term is negative, giving us the alternating sum you wanted. So every integer is congruent to the alternating sum of its digit (mod 11). So if a number was divisible by 11, then their alternating sum (2) must be congruent to 0 (mod 11) which would mean (1) is congruent to 0 mod 11 which by definition, means that it is divisible by 11.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. proof by induction 5^n-1 is divisible by 4
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 29th 2011, 10:54 AM
  2. Replies: 8
    Last Post: July 3rd 2011, 04:55 PM
  3. Proof by induction: 4^n + 6n + 8 is divisible by 9.
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: April 19th 2011, 05:24 PM
  4. Proof validation for number divisible by 25
    Posted in the Algebra Forum
    Replies: 4
    Last Post: March 16th 2006, 08:18 AM
  5. [SOLVED] [SOLVED] Proof divisible by 64
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: April 22nd 2005, 06:12 AM

Search Tags


/mathhelpforum @mathhelpforum