Maths Olympiad Prep

Library / /123 of 397

Number theory Difficulty 5.4 AIME, harder Prove it Taiwan

Let n1n \ge 1 be an integer. In an n×nn \times n table, each cell is filled with an integer. Suppose the following two conditions hold:
(i) The integers on the squares all leave remainder 11 when divided by nn.
(ii) The sum of each row, as well as the sum of each column, leaves remainder nn when divided by n2n^2.
Let RiR_i be the product of all the numbers in the ii-th row, and CjC_j be the product of all the numbers in the jj-th column.
Prove that n4n^4 divides i=1nRij=1nCj\sum_{i=1}^n R_i - \sum_{j=1}^n C_j.

Solution

Let Ai,jA_{i,j} be the entry on row ii and column jj. Let PP be the product of all n2n^2 entries. Denote ai,j=Ai,j1a_{i,j} = A_{i,j} - 1 and ri=Ri1r_i = R_i - 1.
By condition (i), the number nn divides ai,ja_{i,j}. So every product of two or more ai,ja_{i,j} is divisible by n2n^2, hence
Ri=j=1n(1+ai,j)1+j=1nai,j1n+j=1nAi,j(modn2) R_i = \prod_{j=1}^n (1 + a_{i,j}) \equiv 1 + \sum_{j=1}^n a_{i,j} \equiv 1 - n + \sum_{j=1}^n A_{i,j} \pmod{n^2}
for every ii.
By condition (ii), we have Ri1(modn2)R_i \equiv 1 \pmod{n^2}, and so n2rin^2|r_i. Therefore, every product of at least two of the rir_i is divisible by n4n^4. Thus
P=i=1n(1+ri)1+i=1nri(modn4) P = \prod_{i=1}^n (1 + r_i) \equiv 1 + \sum_{i=1}^n r_i \pmod{n^4}
whence
i=1nRi=n+i=1nrin1+P(modn4) \sum_{i=1}^n R_i = n + \sum_{i=1}^n r_i \equiv n - 1 + P \pmod{n^4}

Due to symmetry of the problem conditions, we also have
j=1nCjn1+P(modn4), \sum_{j=1}^n C_{j} \equiv n-1+P \pmod{n^{4}},
thus i=1nRij=1nCj\sum_{i=1}^n R_i - \sum_{j=1}^n C_j is divisible by n4n^4.

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 translated into English from zh; metadata (topic, difficulty) added by this project.