5 ms·
No one taught me this in school, but if you add up the digits (5+7=12) and the result is divisible by 3, then so is the original number. It works recursively.
by alanh 6y ago
No one taught me this in school, but if you add up the digits (5+7=12) and the result is divisible by 3, then so is the original number. It works recursively.
- Arnt 6y agoMy maths teacher made me prove that, my first proof by induction. Try it. You know you want to procrastinate with a nice proof by induction now.
- dmurray 6y agoInduction seems like an odd way to prove this. Do you need to preform induction over all the numbers that are not multiples of three? The converse claim (every multiple of 3 has a digit sum that is a multiple of 3) is a more natural one for induction, though that's not the most standard proof there either.
- dan-robertson 6y agoIf induction is the only tool you have then it’s ok. What you really want is modular arithmetic. If you don’t have modular arithmetic then pricing it directly is hard: n = Sum(d_k 10^k) Let S = sum of digits = Sum(d_k) n - S = Sum(d_k (10^k - 1)) But (10^k - 1) = ((9 + 1)^k - 1) = ((1 + k*9 + (2 choose k)*9^2 + ... + 9^k) - 1) by binomial expansion so is divisible by 9. Therefore n - S is divisible by 9, so n is divisible by 9 iff S is. The same is true when you replace divisibility by 9 with divisibility by 3. I remember being asked this in an interview for a place at university and I solved it by induction (which was all I had) and was then shown this direct proof.
- Arnt 6y agoOdd if you're looking for the simplest way to prove that. Less odd, perhaps, if you're looking for something that can be proved simply using induction, in order to make students do their first proof by induction. I don't remember precisely what it was we were asked to prove. It may have been the converse.
- TimonKnigge 6y agoWorks for 9 as well (or any b such that 10 mod b = 1 .. so 3 and 9).
- DmitryOlshansky 6y agoYes, a simple consequence of e.g. 3-digit number being: 100x + 10y + z modulo 3 Removing 9y and 99x gives equivalence: x + y + z modulo 3 Now what’s left is induction with proper base (1-digit).
- red_admiral 6y agoAs dan-robertson mentioned in another branch, you don't even need induction - you can sidestep it by writing X = sum_i x_i 10^i and noticing that all the 10^i are 1 modulo 9 (and therefore modulo 3).
- wolfi1 6y ago"What is Mathematics" by Courant and Robbins teaches some more divisibility tricks, might be useful sometimes. btw, we learned divisibility by 3 in 5th or 6th grade (not the proof, of course)
- deleted 6y ago[deleted]