Imagine a rectangle divided into 3x4 squares, and put a digit in each square.

     +---+---+---+---+
     | a | b | c | d |  A
     +---+---+---+---+
     | e | f | g | h |  B
     +---+---+---+---+
     | i | j | k | l |  C
     +---+---+---+---+
       D   E   F   G

The number abcd is denoted by A, that is, A = 1000a + 100b + 10c + d, and the same for the other 2 horizontal numbers B and C.

The number aei is denoted by D, that is, D = 100a + 10e + i, and the same for the other 3 vertical numbers E, F and G.

Prove that if any 6 of these numbers (A, B, C, D, E, F, G) are divisible by 7, then the last number must also be divisible by 7.

The posted solution is wrong in two respects:

1)

10² * A + 10 * B + C = 10³ * D + 10² * E + 10 * F + G

does not imply that

A + B + C = D + E + F + G (mod 10).

Mod 10, 10² = 10 = 0,  so all you can say is that C = G (mod 10)
And that's why this isn't true mod 10.  However, that first equation can be used to prove it for mod 7, and for many other moduli also.

2) In fact, it is true for any modulus that leaves a non-zero remainder when dividing all powers of 10.  It is not true that it only works for numbers ending in 1,3,7,or 9.  For instance, it works for any multiple of 3, including 6, 12, 15, 18, 24 and 30, none of which end in 1,3,7, or 9.  More generally, it is true for any number of rows and columns, and for any modulus which has one or more prime factors that are neither 2 nor 5.  






Thus, if the seven numbers A, B, C, D, E, F, G contains six numbers, for instance, A, C, D, E, F, G, divisible by 7, say, then it follows B is divisible by 7, too.

So, if all but one of the numbers obtained by reading from left to right or downwards are known to be divisible by 7, then the last number must also be divisible by 7.

This property can be extended to larger rectangles, and to divisibility by 13, or by 17, or in general, by any number that is relatively prime to 10, which means that it must end in 1, 3, 7, or 9 (3, 7, 9, 11, 13, 17, 19, ...).

Posted by Steve Herman on 2008-11-12 23:00:21