Solution to January 2005 Problem
As a warm-up exercise you can prove
Every way you line up the numbers 0, 1, 2, ..., 9, the resulting 10-digit number is a multiple of 3.
It does not matter whether or not we allow the leading digit to be zero – technically the resulting number would only have 9 digits, but it would still be a multiple of 3, which is the important point. There is no need for you to send us the proof – we already have similar results on the Math Central web page; see, for example,
http://mathcentral.uregina.ca/QQ/database/QQ.09.00/kelera1.html.
Our problem this month is the version that would be natural for a citizen of the planet Kuku, where the inhabitants have five hand of two million digits each.
Let us build a 70-million digit number N by stringing together, in any order, all 107 possible arrangements of 7 digits (using the numbers from 0 to 9 as our digits). In other words, each consecutive 7-digit block of N is one of the arrangements from the list 0000000, 0000001, 0000002, ..., 9999999. (There are 10-million factorial such numbers N, if we allow them to begin with initial zeros.)
The problem for January:
Prove that every one of these very many very big numbers Nis divisible by 239.
Solution to MP47
We found our January problem in a review of the latest book by Ross Honsberger — Mathematical Delights. We received correct solutions from
| Mehdi Abdeh-Kolahchi (Halifax, Nova Scotia) | Xavier Hecquet (France) |
| Pierre Bornsztein (France) | Wolfgang Kais (Germany) |
| John Campbell (Edmonton, Alberta) | Nguyen Ngoc Khoi |
| Seymur Cahangirov | Marc Lichtenberg (France) |
| Pablo de la Viuda (Spain) | Patrick LoPresti (USA) |
| Cédric Favry (France) | Dat Phan (Regina) |
| Gilles Feyrit (France) | Anonymous |
The solutions came in two forms.
Variation 1 (the method used by most solvers — we combine all their ideas here). First, almost everybody factored 107 – 1 = 9999999 = 3·3·239·4649. This means that
(107)k 
1
(mod 239). (*)
(In words, (*) means that if you divide any power of 107 by 239, you always get a remainder of 1. Abdeh-Kolahchi came to this conclusion without a calculator by noticing that
107 = (103)2 ·10
= (956 + 44)2 ·10 (44)2 ·10
= (1912 + 24)·10 24·10 1
(mod 239).)
If we let B1, B2, B3, ..., B107 be the complete list of all 7-digit blocks, listed in any order, then our large number N can be written
N = B2 + B2107 +B3(107)2 + ... + B10000000(107)999999.
By our observation (*), N B1
+ B2 + B3 + ... + B107 (mod
239). We recognize that this sum is just the sum of the integers
from 0 to 107 – 1, so that
N 1
+ 2 + 3 + ... + (107 -1) = (107(107-1)/2)(mod
239)
Since 107 is divisible by 2, we see that N is congruent modulo 239 to an integer multiple of 107-1, which by (*) is divisible by 239; we therefore conclude that N itself is divisible by 239.
In fact, our argument shows that N is divisible by 9999999 as well as by all of its divisors. Several correspondents noted, furthermore, that the property of the month will hold with 107 replaced by any positive number b; specifically,
When the "digits" 0, 1, 2, ..., b – 1, are strung together to form a number written in base b, that number is divisible by b – 1 (and all divisors of b – 1) when b is even, and it is divisible by the divisors of (b – 1)/2 when b is odd.
Variation 2 (The method of Phan and de la Viuda). To discover the divisibility criteria, we first examine the residues modulo 239 for the powers of 10:
|
|
and the cycle of length 7 starts again. In our large number N, a typical block of 7 consecutive digits looks like
a·107k + b·107k+1 + c·107k+2 + d·107k+3 + e·107k+4 + f·107k+5 + g·107k+6
a·1
+ b·10 + c·100 + d·44 + e·201 + f·98
+ g·24 (mod 239).
With 107 ways to replace the letters a through g by the digits 0 through 9, each of these letters will take on each value 0 through 9 exactly 106 times each. Therefore, letting k = (0 + 1 + 2 + ... + 9)·106 = 45·106, we see that
N º k(1 + 10 + 100 + 44 + 201 + 98 + 24) = k·478
0
(mod 239),
which says that N is divisible by 239 as claimed