## 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

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=10^{80}+10^{79}+...+10^{1}+1 and
the sum comprises 81 terms - 10^{80}, 10^{79}, ..., 1. Subtracting 1 from each
and then adding it back gives

N=(10^{80}-1+1)+(10^{79}-1+1)+...+(10^{1}-1+1)+(1-1+1).

Now regroup the terms to get N=(10^{80}-1)+(10^{79}-1)+...+(10^{1}-1)+81. Notice that
10^{80}-1 is the number written with 80 9's. 10^{79}-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=10^{160}+10^{158}+10^{156}+...+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 10^{n}=1 mod 9. This, in turn, is a straightforward
consequence of 10=1 mod 9.

## Exercise 1

Prove that a number _{n}10^{n}+a_{n-1}10^{n-1} + ... + a_{1}10^{1} + a_{0}_{0}+a_{1}+a_{2}+...+a_{n} is divisible by 9.

### Exercise 2

Prove that the number N is divisible by 11 iff _{0} - a_{1} + a_{2} - ... + (-1)^{n}a_{n} = 0.

### Remark

Both results admit a very useful though straightforward generalization.

### References

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

|Contact| |Front page| |Contents| |Generalizations| |Arithmetic|

Copyright © 1996-2018 Alexander Bogomolny