Maths Olympiad Prep

Library / /237 of 383

Number theory Difficulty 8.7 Shortlist Prove it IMO

Let n>1n > 1 be a positive integer. Each cell of an n×nn \times n table contains an integer. Suppose that the following conditions are satisfied:
(i) Each number in the table is congruent to 11 modulo nn;
(ii) The sum of numbers in any row, as well as the sum of numbers in any column, is congruent to nn modulo n2n^{2}.
Let RiR_{i} be the product of the numbers in the ithi^{\text{th}} row, and CjC_{j} be the product of the numbers in the jthj^{\text{th}} column. Prove that the sums R1++RnR_{1} + \cdots + R_{n} and C1++CnC_{1} + \cdots + C_{n} are congruent modulo n4n^{4}.

Solutions — 2

Solution 1

Let Ai,jA_{i, j} be the entry in the ithi^{\text{th}} row and the jthj^{\text{th}} column; let PP be the product of all n2n^{2} entries. For convenience, denote ai,j=Ai,j1a_{i, j} = A_{i, j} - 1 and ri=Ri1r_{i} = R_{i} - 1. We show that
i=1nRi(n1)+P(mod n4)(1) \sum_{i=1}^{n} R_{i} \equiv (n-1) + P \quad (\bmod\ n^{4}) \tag{1}
Due to symmetry of the problem conditions, the sum of all the CjC_{j} is also congruent to (n1)+P(n-1) + P modulo n4n^{4}, whence the conclusion.
By condition (i)(i), the number nn divides ai,ja_{i, j} for all ii and jj. So, every product of at least two of the ai,ja_{i, j} is divisible by n2n^{2}, hence
Ri=j=1n(1+ai,j)=1+j=1nai,j+1j1<j2nai,j1ai,j2+1+j=1nai,j1n+j=1nAi,j (mod n2)R_{i} = \prod_{j=1}^{n} (1 + a_{i, j}) = 1 + \sum_{j=1}^{n} a_{i, j} + \sum_{1 \leqslant j_{1} < j_{2} \leqslant n} a_{i, j_{1}} a_{i, j_{2}} + \cdots \equiv 1 + \sum_{j=1}^{n} a_{i, j} \equiv 1 - n + \sum_{j=1}^{n} A_{i, j} \ (\bmod\ n^{2})
for every index ii. Using condition (ii), we obtain Ri1 (mod n2)R_{i} \equiv 1\ (\bmod\ n^{2}), and so n2rin^{2} \mid r_{i}.
Therefore, every product of at least two of the rir_{i} is divisible by n4n^{4}. Repeating the same argument, we obtain
P=i=1nRi=i=1n(1+ri)1+i=1nri(mod n4), P = \prod_{i=1}^{n} R_{i} = \prod_{i=1}^{n} (1 + r_{i}) \equiv 1 + \sum_{i=1}^{n} r_{i} \quad (\bmod\ n^{4}),
whence
i=1nRi=n+i=1nrin+(P1)(mod n4) \sum_{i=1}^{n} R_{i} = n + \sum_{i=1}^{n} r_{i} \equiv n + (P - 1) \quad (\bmod\ n^{4})
as desired.

Solution 2

We present a more straightforward (though lengthier) way to establish (1). We also use the notation of ai,ja_{i, j}.
By condition (i), all the ai,ja_{i, j} are divisible by nn. Therefore, we have
P=i=1nj=1n(1+ai,j)1+(i,j)ai,j+(i1,j1),(i2,j2)ai1,j1ai2,j2+(i1,j1),(i2,j2),(i3,j3)ai1,j1ai2,j2ai3,j3(mod n4) \begin{aligned} P = \prod_{i=1}^{n} \prod_{j=1}^{n} (1 + a_{i, j}) &\equiv 1 + \sum_{(i, j)} a_{i, j} + \sum_{(i_{1}, j_{1}), (i_{2}, j_{2})} a_{i_{1}, j_{1}} a_{i_{2}, j_{2}} \\ &+ \sum_{(i_{1}, j_{1}), (i_{2}, j_{2}), (i_{3}, j_{3})} a_{i_{1}, j_{1}} a_{i_{2}, j_{2}} a_{i_{3}, j_{3}} \quad (\bmod\ n^{4}) \end{aligned}
where the last two sums are taken over all unordered pairs/triples of pairwise different pairs (i,j)(i, j); such conventions are applied throughout the solution.
Similarly,
i=1nRi=i=1nj=1n(1+ai,j)n+ijai,j+ij1,j2ai,j1ai,j2+ij1,j2,j3ai,j1ai,j2ai,j3(mod n4). \sum_{i=1}^{n} R_{i} = \sum_{i=1}^{n} \prod_{j=1}^{n} (1 + a_{i, j}) \equiv n + \sum_{i} \sum_{j} a_{i, j} + \sum_{i} \sum_{j_{1}, j_{2}} a_{i, j_{1}} a_{i, j_{2}} + \sum_{i} \sum_{j_{1}, j_{2}, j_{3}} a_{i, j_{1}} a_{i, j_{2}} a_{i, j_{3}} \quad (\bmod\ n^{4}) .
Therefore,
P+(n1)iRi(i1,j1),(i2,j2)i1i2ai1,j1ai2,j2+(i1,j1),(i2,j2),(i3,j3)i1i2i3i1ai1,j1ai2,j2ai3,j3+(i1,j1),(i2,j2),(i3,j3)i1i2=i3ai1,j1ai2,j2ai3,j3(mod n4). \begin{aligned} P + (n-1) - \sum_{i} R_{i} &\equiv \sum_{\substack{(i_{1}, j_{1}), (i_{2}, j_{2}) \\ i_{1} \neq i_{2}}} a_{i_{1}, j_{1}} a_{i_{2}, j_{2}} \\ &+ \sum_{\substack{(i_{1}, j_{1}), (i_{2}, j_{2}), (i_{3}, j_{3}) \\ i_{1} \neq i_{2} \neq i_{3} \neq i_{1}}} a_{i_{1}, j_{1}} a_{i_{2}, j_{2}} a_{i_{3}, j_{3}} \\ &+ \sum_{\substack{(i_{1}, j_{1}), (i_{2}, j_{2}), (i_{3}, j_{3}) \\ i_{1} \neq i_{2} = i_{3}}} a_{i_{1}, j_{1}} a_{i_{2}, j_{2}} a_{i_{3}, j_{3}} \quad (\bmod\ n^{4}) . \end{aligned}
We show that in fact each of the three sums appearing in the right-hand part of this congruence is divisible by n4n^{4}; this yields (1). Denote those three sums by Σ1,Σ2\Sigma_{1}, \Sigma_{2}, and Σ3\Sigma_{3} in order of appearance. Recall that by condition (ii) we have
jai,j0(mod n2)for all indices i \sum_{j} a_{i, j} \equiv 0 \quad (\bmod\ n^{2}) \quad \text{for all indices } i
For every two indices i1<i2i_{1} < i_{2} we have
j1j2ai1,j1ai2,j2=(j1ai1,j1)(j2ai2,j2)0(mod n4) \sum_{j_{1}} \sum_{j_{2}} a_{i_{1}, j_{1}} a_{i_{2}, j_{2}} = \left(\sum_{j_{1}} a_{i_{1}, j_{1}}\right) \cdot \left(\sum_{j_{2}} a_{i_{2}, j_{2}}\right) \equiv 0 \quad (\bmod\ n^{4})
since each of the two factors is divisible by n2n^{2}. Summing over all pairs (i1,i2)(i_{1}, i_{2}) we obtain n4Σ1n^{4} \mid \Sigma_{1}.
Similarly, for every three indices i1<i2<i3i_{1} < i_{2} < i_{3} we have
j1j2j3ai1,j1ai2,j2ai3,j3=(j1ai1,j1)(j2ai2,j2)(j3ai3,j3) \sum_{j_{1}} \sum_{j_{2}} \sum_{j_{3}} a_{i_{1}, j_{1}} a_{i_{2}, j_{2}} a_{i_{3}, j_{3}} = \left(\sum_{j_{1}} a_{i_{1}, j_{1}}\right) \cdot \left(\sum_{j_{2}} a_{i_{2}, j_{2}}\right) \cdot \left(\sum_{j_{3}} a_{i_{3}, j_{3}}\right)
which is divisible even by n6n^{6}. Hence n4Σ2n^{4} \mid \Sigma_{2}.
Finally, for every indices i1i2=i3i_{1} \neq i_{2} = i_{3} and j2<j3j_{2} < j_{3} we have
ai2,j2ai2,j3j1ai1,j10(mod n4) a_{i_{2}, j_{2}} \cdot a_{i_{2}, j_{3}} \cdot \sum_{j_{1}} a_{i_{1}, j_{1}} \equiv 0 \quad (\bmod\ n^{4})
since the three factors are divisible by n,nn, n, and n2n^{2}, respectively. Summing over all 4-tuples of indices (i1,i2,j2,j3)(i_{1}, i_{2}, j_{2}, j_{3}) we get n4Σ3n^{4} \mid \Sigma_{3}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.