Exercises 25 We have been told in arithmetic that the remin

Exercises 25 : We have been told in arithmetic that the reminder of an integer divided by 9 is the same as the reminder of division of the sum of its decimal digits by 9. In other words, the reminder of division 6371 by 9 is the same as dividing 17 by 9 because 6+3+7+1=17. Use the properties of the mod operator to prove this claim

This question is from Cryptography course

Solution

Ans :

As we can write 6371 = 6 * 10³ + 3 * 10² + 7 * 10¹ + 1 * 10⁰

which means a = a_n * 10ⁿ + ..........+ a₁ * 10¹ + a₀ * 10⁰   . .......................(1)

Also 10 mod 9 = 1

And 10ⁿ mod 9 = (10 mod 9)ⁿ = 1 ...........................(2)

Now by applying the mod operator of 9 to both sides of (1) we get

a mod 9 = (a_n * 10ⁿ + .......+a₀ *10⁰) mod 9

= (a_n * 10ⁿ) mod 9 + ..............+ (a₀ *10⁰) mod 9

= (a_n mod 9) * (10ⁿ mod 9) + ..................+ (a₀  mod 9 ) * (10⁰ mod 9)

= (a_n mod 9) + ..........+  (a₀  mod 9 ) ...............................( From (2) )

=(a_n + ......+ a₁ + a₀ ) mod 9

Hence Proved.