Arrange n×m digits a_ij (i = 1, ..., n; j = 1, ..., m) in a rectangular array. If read left to right, every row then represents a decimal integer, and so does every column if read from top downwards. In all, there are n + m integers. Let p be relatively prime to 10. (Two integers are relatively or mutually prime if they have no common divisors except 1. They are also called coprime.) Being prime to 10 means that p is odd but is not divisible by 5. 3, 7, 9, 11, 21 are examples of such integers.

Here's a problem. Assume it's known that all n + m numbers in the matrix but one are divisible by p. Prove that the remaining number is bound to be divisible by p as well.

The applet below helps you verify that this is so. All digits are clickable so that you can modify the matrix to your liking.

References

1. Fred. Schuh, The Master Book of Mathematical Recreations, Dover, 1968, p 307

Copyright © 1996-2008 Alexander Bogomolny

The proof is an exercise in the basic laws (associativity, commutativity, and distributivity) of arithmetic operations.

There are n horizontal numbers

and m vertical numbers

Form the number

That is, multiply the first row by 10^n-1, the second row by 10^n-2, and so on, and sum up all the resulting numbers. We may also proceed differently. Multiply the columns starting from left by 10^m-1, 10^m-2, and so on. Sum up the products:

I claim that C = D. If true, it will solve our problem. In the way of example, let n = 2 and m = 3. C = D means that

If, for example, A₁, A₂, B₁, and B₃ are divisible by p. Then

where the right-hand side is divisible by p. The product on the left is thus also divisible by p. If p is relatively prime to 10, it is also prime to all powers of 10. It then follows that p divides B₂.

How do we prove the identity C = D? Take any digit a_ij and compare the powers of ten it is multiplied by in C and D. a_ij is included into C as a digit of A_i. Its place value in A_i is 10^m-ja_ij. To obtain C, A_i is multiplied by 10^n-i. Therefore, digit a_ij enters into the sum C with the coefficient 10^m+n-i-j. It's the very same coefficient that stands by a_ij in the sum D.

Copyright © 1996-2008 Alexander Bogomolny