# 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 *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.

What if applet does not run? |

### References

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

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

Copyright © 1996-2017 Alexander Bogomolny

### 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-1}a_{i1} + 10^{m-2}a_{i2} + ... + a_{im}

and m vertical numbers

B_{j} = 10^{n-1}a_{1j} + 10^{n-2}a_{2j} + ... + a_{nj}.

Form the number

C = 10^{n-1}A_{1} + 10^{n-2}A_{2} + ... + 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-1}B_{1} + 10^{m-2}B_{2} + ... + B_{m}.

I claim that C = D. If true, it will solve our problem. In the way of example, let

10A_{1} + A_{2} = 10^{2}B_{1} + 10·B_{2} + B_{3}

If, for example, A_{1}, A_{2}, B_{1}, and B_{3} are divisible by p. Then

10·B_{2} = 10^{2}B_{1} + B_{3} - 10A_{1} - A_{2}

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_{2}.

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-j}a_{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.

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

Copyright © 1996-2017 Alexander Bogomolny

62067193 |