[Ashish Khandelwal]

Suppose that you have a four-digit number nn that is written abcdabcd. Then

n=103a+102b+10c+d=(999+1)a+(99+1)b+(9+1)c+d=(999a+99b+9c)+(a+b+c+d)=3(333a+33b+3c)+(a+b+c+d),n=103a+102b+10c+d=(999+1)a+(99+1)b+(9+1)c+d=(999a+99b+9c)+(a+b+c+d)=3(333a+33b+3c)+(a+b+c+d),
so when you divide nn by 33, you’ll get

333a+33b+3c+a+b+c+d3.333a+33b+3c+a+b+c+d3.
The remainder is clearly going to come from the division a+b+c+d3a+b+c+d3, since 333a+33b+3c333a+33b+3c is an integer.

Now generalize: make a similar argument for any number of digits, not just four. (If you know about congruences and modular arithmetic, you can do it very compactly.)

[Author]

Posts