Problem 1A number is written with 81 ones. Prove it's a multiple of 81. RemarkFor 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 1Let 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 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: 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 2Prove that the number 1010101...0101, 81 ones and 80 alternating zeros, is a multiple of 81. Solution to Problem 2As 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.
Let number N be such that it's written with 81 1's with k zeros (k
CounterexampleConsider, for example, N=88888888881.
Modulo Arithmetic, CongruenceWe 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
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 1Prove that a number Exercise 2Prove that the number N is divisible by 11 iff RemarkBoth results admit a very useful though straightforward generalization.
References
|Contact| |Front page| |Contents| |Generalizations| |Arithmetic| |Store| Copyright © 1996-2012 Alexander Bogomolny |
0) between every pair of ones.
Prove that N is divisible by 81.| 40585949 |
