Results 1 to 4 of 4

Math Help - Prove divisibility test for 3 using induction

  1. #1
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Prove divisibility test for 3 using induction

    The sum of the digits of 3 is 3, which is divisible by 3.

    Let the statement be true for a certain number n, which is divisible by 3.
    So, the sum of its digits is divisible by 3.

    Consider the number n + 3, which is the next number divisible by 3.
    The sum of its digits is divisible by 3. -- I'm looking for a rigorous proof of this step.
    This completes the proof.
    Last edited by alexmahone; August 12th 2011 at 03:23 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member abhishekkgp's Avatar
    Joined
    Jan 2011
    From
    India
    Posts
    495
    Thanks
    1

    Re: Prove divisibility test for 3 using induction

    Quote Originally Posted by alexmahone View Post
    The sum of the digits of 3 is 3, which is divisible by 3.

    Let the statement be true for a certain number n, which is divisible by 3.
    So, the sum of its digits is divisible by 3.

    Consider the number n + 3.
    The sum of its digits is divisible by 3. -- I'm looking for a rigorous proof of this step.
    So, n + 3 is divisible by 3. This completes the proof.
    well you can make 10 cases:
    CASE 1: the last digit of n is 0. in this case sum_of_digits_of (n+3)= 3 + sum_of_digits_of n. So the inductive statement holds.

    CASE 2: the last digit of n is 1. same argument holds.

    ...
    CASE 8: the last digit of n is 7. here the argument extends to the second last digit if the second last digit is less than 9 and to the third last digit if the third last digit is 9 and so on. But still the argument is easy. Can you finish?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Re: Prove divisibility test for 3 using induction

    Quote Originally Posted by abhishekkgp View Post
    well you can make 10 cases:
    CASE 1: the last digit of n is 0. in this case sum_of_digits_of (n+3)= 3 + sum_of_digits_of n. So the inductive statement holds.

    CASE 2: the last digit of n is 1. same argument holds.

    ...
    CASE 8: the last digit of n is 7. here the argument extends to the second last digit if the second last digit is less than 9 and to the third last digit if the third last digit is 9 and so on. But still the argument is easy. Can you finish?
    Case 8: If the last digit of n is 7, the last digit of n + 3 is 0. If i digits preceding the last digit are 9, they will all become 0. The digit before the i digits (equal to 9) will increase by 1, and so the sum of digits of n + 3 will be (sum of digits of n) - 9i - 7 + 1 = (sum of digits of n) - 9i - 6, which is also divisible by 3.

    Case 9: If the last digit of n is 8, the last digit of n + 3 is 1. If i digits preceding the last digit are 9, they will all become 0. The digit before the i digits (equal to 9) will increase by 1, and so the sum of digits of n + 3 will be (sum of digits of n) - 9i - 7 + 1 = (sum of digits of n) - 9i - 6, which is also divisible by 3.

    Case 10: If the last digit of n is 9, the last digit of n + 3 is 2. If i digits preceding the last digit are 9, they will all become 0. The digit before the i digits (equal to 9) will increase by 1, and so the sum of digits of n + 3 will be (sum of digits of n) - 9i - 7 + 1 = (sum of digits of n) - 9i - 6, which is also divisible by 3.

    Is this what you had in mind?
    Last edited by alexmahone; August 12th 2011 at 12:07 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member abhishekkgp's Avatar
    Joined
    Jan 2011
    From
    India
    Posts
    495
    Thanks
    1

    Re: Prove divisibility test for 3 using induction

    Quote Originally Posted by alexmahone View Post
    Case 8: If the last digit of n is 7, the last digit of n + 3 is 0. If i digits preceding the last digit are 9, they will all become 0. The digit before the i digits (equal to 9) will increase by 1, and so the sum of digits of n + 3 will be the (sum of digits of n) - 9i 7 + 1 = (sum of digits of n) -9i - 6, which is also divisible by 3.

    Case 9: If the last digit of n is 8, the last digit of n + 3 is 1. If i digits preceding the last digit are 9, they will all become 0 and not change the sum_of_digits % 3. The digit before the i digits (equal to 9) will increase by 1, and so the sum of digits of n + 3 will be the (sum of digits of n) - 9i - 7 + 1 = (sum of digits of n) 9i - 6, which is also divisible by 3.

    Case 10: If the last digit of n is 9, the last digit of n + 3 is 2. If i digits preceding the last digit are 9, they will all become 0 and not change the sum_of_digits % 3. The digit before the i digits (equal to 9) will increase by 1, and so the sum of digits of n + 3 will be the (sum of digits of n) - 9i - 7 + 1 = (sum of digits of n) - 9i - 6, which is also divisible by 3.

    Is this what you had in mind?
    yup!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove divisibility test for 11 using induction
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: August 13th 2011, 04:48 AM
  2. Induction divisibility P1
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 6th 2010, 11:20 AM
  3. Prove divisibility by induction
    Posted in the Algebra Forum
    Replies: 9
    Last Post: June 2nd 2009, 01:14 PM
  4. Prove divisibility by 7 (using induction)
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 29th 2008, 12:12 PM
  5. Prove divisibility by induction
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: July 30th 2008, 01:58 PM

Search Tags


/mathhelpforum @mathhelpforum