Putnam 1995, Problem A-3

The number \( d_1d_2\ldots d_9 \) has nine (not necessarily distinct) decimal digits. The number \( e_1e_2\ldots e_9 \) is such that each of the nine 9-digit numbers formed by replacing just one of the digits \( d_i \) is \( d_1d_2\ldots d_9 \) by the corresponding digit \( e_i \) (\( 1 \leq i \leq 9 \)) is divisible by 7. The number \( f_1f_2\ldots f_9 \) is related to \( e_1e_2\ldots e_9 \) in the same way: that is, each of the nine numbers formed by replacing one of the \( e_i \) by the corresponding \( f_i \) is divisible by 7. Show that, for each \( i \), \( d_i - f_i \) is divisible by 7. [For example, if \( d_1d_2\ldots d_9 = 199501996 \), then \( e_6 \) may be 2 or 9, since 199502996 and 199509996 are multiples of 7.]

Solution:
Let \( D \) and \( E \) be the numbers \( d_1 \dots d_9 \) and \( e_1 \dots e_9 \), respectively. We are given that \( (e_i - d_i) 10^{9-i} + D \equiv 0 \pmod{7} \) and \( (f_i - e_i) 10^{9-i} + E \equiv 0 \pmod{7} \) for \( i = 1, \dots, 9 \). Sum the first relation over \( i = 1, \dots, 9 \) and we get \( E - D + 9D \equiv 0 \pmod{7} \), or \( E + D \equiv 0 \pmod{7} \). Now add the first and second relations for any particular value of \( i \) and we get \( (f_i - d_i) 10^{9-i} + E + D \equiv 0 \pmod{7} \). But we know \( E + D \) is divisible by 7, and 10 is coprime to 7, so \( d_i - f_i \equiv 0 \pmod{7} \).