## Problem 1

A number is written with 81 ones. Prove it's a multiple of 81.

### Remark

For those who remember the rules that a number is divisible by 3 and 9 if and only if (iff) the sum of its digits is divisible by 3 or 9, respectively, it's tempting to assume that the same applies to 81. That is a number is divisible by 81 iff the sum of its digits is divisible by 81. However, such an assumption will be patently false. For example, for 162, the sum of digits is 1 + 6 + 2 = 9. Thus you realize that the number 81 is too big. There is a good deal of its multiples whose sum is nowhere near 81.

Still, on the other hand, there is plenty of numbers whose digits sum up to 81 or its multiple. Perhaps the assumption works at least in one direction: If, for a number, the sum of digits is divisible by 81 then the number itself is divisible by 81. However, a little investigation shows this also to be false. (Try finding a counterexample - a number not divisible by 81 whose digits sum up to 81).

### Solution to Problem 1

Let N=111...111 be written with 81 1's. We must prove it's divisible by 81.

N is a decimal number which means N=1080+1079+...+101+1 and the sum comprises 81 terms - 1080, 1079, ..., 1. Subtracting 1 from each and then adding it back gives

N=(1080-1+1)+(1079-1+1)+...+(101-1+1)+(1-1+1).

Now regroup the terms to get N=(1080-1)+(1079-1)+...+(101-1)+81. Notice that 1080-1 is the number written with 80 9's. 1079-1 is written with 79 9's and so on. Each of them is divisible by 9 which can be factored out:

N=9*(11...11 + 11..11 + ... + 111 + 11 + 1) + 81,

where the first number in parenthesis is written with 80 1's, the second with 79 1's and so on. Suffice it now to prove that the sum in parenthesis is divisible by 9. Let us apply what is known from the calculus by modulo 9. The sum of digits of the first number in parenthesis is 80, of the second - 79, then 78, and so on. Therefore, the number in parenthesis and 80+79+78+...+3+2+1 have the same remainder when divided by 9. But 80+79+78+...+3+2+1 = 81*80/2=81*40 is divided by 9 (actually, by 81). Therefore the number in parenthesis is divided by 9 and hence N is divisible by 81. ## Problem 2

Prove that the number 1010101...0101, 81 ones and 80 alternating zeros, is a multiple of 81.

### Solution to Problem 2

As before, let N denote the number at hand. Now we can write N=10160+10158+10156+...+100+1. Following in footsteps of Problem 1, N=9*(11...1 + 11...1 + 11) + 81 where the first number in parenthesis is written with 160 1's, the second with 158 ones, the third needs 156 ones and so on. Thus, when divided by 9, the number in parenthesis has the same remainder as (160+158+156+...+2)=2*(80+79+78+...+1) which is divisible by 9. The two problems above admit a natural generalization.

## Problem 3

Let number N be such that it's written with 81 1's with k zeros (k≠0) between every pair of ones. Prove that N is divisible by 81. ## Counterexample

Consider, for example, N=88888888881. ### Modulo Arithmetic, Congruence

We write a=b mod N iff (a-b) is divisible by N or, in other words, when a and b have the same remainder when divided by N. Such a and b are said to be congruent modulo N. From the definition one can easily derive several properties. For example

• If a = b mod N and c = d mod N then (a + c) = (b + d) mod N
• If a = b mod N and c = d mod N then ac = bd mod N

The criterion of divisibility by 9 follows from the fact that for every n 10n=1 mod 9. This, in turn, is a straightforward consequence of 10=1 mod 9.

## Exercise 1

Prove that a number N = an10n+an-110n-1 + ... + a1101 + a0 is divisible by 9 iff a0+a1+a2+...+an is divisible by 9.

### Exercise 2

Prove that the number N is divisible by 11 iff a0 - a1 + a2 - ... + (-1)nan = 0.

### Remark

Both results admit a very useful though straightforward generalization. ### References

1. R.Courant and H.Robbins, What is Mathematics?, Oxford University Press, 1996
2. H.Davenport, The Higher Arithmetic, Harper&Brothers, NY. • 