A Problem of Divisibility

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.

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at http://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

Buy this applet
What if applet does not run?

References

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

Proof

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

There are n horizontal numbers

A_i = 10^m-1a_i1 + 10^m-2a_i2 + ... + a_im

and m vertical numbers

B_j = 10^n-1a_1j + 10^n-2a_2j + ... + a_nj.

Form the number

C = 10^n-1A₁ + 10^n-2A₂ + ... + A_n.

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:

D = 10^m-1B₁ + 10^m-2B₂ + ... + B_m.

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

10A₁ + A₂ = 10²B₁ + 10·B₂ + B₃

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

10·B₂ = 10²B₁ + B₃ - 10A₁ - A₂

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.

40616156