How would one go about proving this rule using modular arithmetic and can it be done using Euclidean algorithm?
The question is this but I am unsure which route to take: The number $123$ in $\mathbb{Z}$ has the property that $123 = 6 \mod{9}$, and $1 + 2 + 3 = 6 \mod {9}$.
Prove that an integer is divisible by $9$ if and only if the sum of its digits is divisible by $9$.
Any help would be appreciated as my lecturer won't post any solutions.
Best Answer
Suppose, the digits $a_n,a_{n-1},\cdots ,a_1,a_0$ form the number $N$. Then, we have $$N=10^na_n+10^{n-1}a_{n-1}+\cdots+10a_1+a_0$$
Because of $$10^k\equiv 1\mod 9$$ for all non-negative integers $k$, we get
$$N\equiv a_n+a_{n-1}+\cdots+a_1+a_0\mod 9$$
So, the number has the same residue modulo $9$ as the sum of its digits.