A Problem of Divisibility

Arrange n×m digits aij (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 https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.


What if applet does not run?

References

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

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

Proof

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

There are n horizontal numbers

Ai = 10m-1ai1 + 10m-2ai2 + ... + aim

and m vertical numbers

Bj = 10n-1a1j + 10n-2a2j + ... + anj.

Form the number

C = 10n-1A1 + 10n-2A2 + ... + An.

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

D = 10m-1B1 + 10m-2B2 + ... + Bm.

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

10A1 + A2 = 102B1 + 10·B2 + B3

If, for example, A1, A2, B1, and B3 are divisible by p. Then

10·B2 = 102B1 + B3 - 10A1 - A2

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 B2.

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

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

71471492