Делимость на 3 и 9

Читатель нашего блога segagenesis предложил в качестве темы признаки делимости на 3 и 9. Если сумма цифр в числе кратна трём, то это число делится на три. тоже самое и для девятки.

Почему это работает?

Пусть у нас есть (n+1)-значное число a_na_n-1...a₅a₄a₃a₂a₁a₀. Его можно записать как a_n10ⁿ+a_n-110^n-1+...+a₅10⁵+a₄10⁴+a₃10³+a₂10²+a₁10+a₀=

=a_n(999...999+1)+a_n-1(999...99+1)+...+a₅(99999+1)+a₄(9999+1)+a₃(999+1)+a₂(99+1)+a₁(9+1)+a₀=

=999...999a_n+999...99a_n-1+...+99999a₅+9999a₄+999a₃+99a₂+9a₁+
+a_n+a_n-1+...+a₅+a₄+a₃+a₂+a₁+a₀

Поскольку все слагаемые, в которых есть множитель, состоящий из девяток, делятся на 9, то делится или не делится исходное число на 9 или на 3 зависит только от того, делится ли на 9 или на 3 сумма его цифр.