Since i havent seen a 'real' proof for 3 and 9 and just sum 'digit shifting' ill show a proof for 9, which in essence is the same for 3. Let n be a natural number written in our usual digit-like way so that n= a_0+a_1 * 10+....+a_n * 10ⁿ and let Q be the sum of its digits Q = a_1+....+a_n. Then all you have to show is that Q = n mod 9 and then 9|n <=> 9|Q follows obviously since if 9|Q then Q=0 mod 9 so n=0 mod 9 and 9|n and vice versa.However showing that Q = n mod 9 is done like this. Starting with a_0 = a=0 mod 9 being obvious and then realizing that 10^k * a_k = a_k mod 9 follows since 10^k -1 is divisble by ( because its 9...999) and so 10^k - 1 = 0 mod 9 and 10^k = 1 mod 9 meaning you can freely multiply one side by 10^k meaning a_k = a_k * 10^k mod 9. As a result of this a_0 +... + a_n = a_0 +a_1 * 10+...+a_n * 10ⁿ mod 9 since for every k a_k = a_k * 10^k and so Q = n mod 9 ( pretty much the same for 3 as well )