# Thread: Prove divisibility test for 3 using induction

1. ## 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.

2. ## Re: Prove divisibility test for 3 using induction

Originally Posted by alexmahone
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?

3. ## Re: Prove divisibility test for 3 using induction

Originally Posted by abhishekkgp
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?

4. ## Re: Prove divisibility test for 3 using induction

Originally Posted by alexmahone
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!