Maths Olympiad Prep

Library / /450 of 520

Number theory Difficulty 7.2 National olympiad, round 2 Prove it

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 1 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 ith i^{\text {th }} row, and CjC_{j} be the product of the numbers in the jth j^{\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}. (Indonesia)

Solution

Let Ai,jA_{i, j} be the entry in the ith i^{\text {th }} row and the jth j^{\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(modn4) \sum_{i=1}^{n} R_{i} \equiv(n-1)+P \quad\left(\bmod n^{4}\right)
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(modn2) R_{i}=\prod_{j=1}^{n}\left(1+a_{i, j}\right)=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} \quad\left(\bmod n^{2}\right)
for every index ii. Using condition (ii), we obtain Ri1(modn2)R_{i} \equiv 1\left(\bmod n^{2}\right), 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(modn4) P=\prod_{i=1}^{n} R_{i}=\prod_{i=1}^{n}\left(1+r_{i}\right) \equiv 1+\sum_{i=1}^{n} r_{i} \quad\left(\bmod n^{4}\right)
whence
i=1nRi=n+i=1nrin+(P1)(modn4) \sum_{i=1}^{n} R_{i}=n+\sum_{i=1}^{n} r_{i} \equiv n+(P-1) \quad\left(\bmod n^{4}\right)
as desired.
Comment. The original version of the problem statement contained also the condition
(iii) The product of all the numbers in the table is congruent to 1 modulo n4n^{4}.
This condition appears to be superfluous, so it was omitted.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.