Shortlist 2018, N2¶

Domaine : Théorie des nombres · Difficulté : ★☆☆☆☆ · Proposé par : Indonesia

Concepts : Congruences, théorèmes de Fermat et d'Euler

Solution officielle : Shortlist officielle 2018 (avec solutions), p. 56 (page 58 du PDF)

Énoncé¶

Let \(n > 1\) be a positive integer. Each cell of an \(n \times n\) table contains an integer. Suppose that the following conditions are satisfied:

(i) Each number in the table is congruent to \(1\) modulo \(n\);

(ii) The sum of numbers in any row, as well as the sum of numbers in any column, is congruent to \(n\) modulo \(n^2\).

Let \(R_i\) be the product of the numbers in the \(i\)-th row, and \(C_j\) be the product of the numbers in the \(j\)-th column. Prove that the sums \(R_1 + \cdots + R_n\) and \(C_1 + \cdots + C_n\) are congruent modulo \(n^4\).

Indices : les idées clés

Une quantité symétrique : on montre que \(R_1 + \cdots + R_n \equiv (n-1) + P \pmod{n^4}\), où \(P\) est le produit de tous les nombres du tableau ; par symétrie, il en va de même pour les \(C_j\).
Congruences et développement d'un produit : si chaque \(a_j\) est divisible par \(n\), alors \(\prod (1 + a_j) \equiv 1 + \sum a_j \pmod{n^2}\), car tout produit d'au moins deux \(a_j\) est divisible par \(n^2\).
Appliquer deux fois la même idée (solution 1) : d'abord \(R_i \equiv 1 \pmod{n^2}\), puis \(P = \prod R_i \equiv 1 + \sum (R_i - 1) \pmod{n^4}\).
Développer jusqu'à l'ordre 3 (solution 2) : regrouper les termes selon les lignes et factoriser par des sommes de lignes, divisibles par \(n^2\).

Solutions

Les solutions ci-dessous suivent les solutions officielles de la Shortlist 2018 (deux solutions et une remarque).

Solution 1¶

Notons \(A_{i,j}\) le nombre situé à la \(i\)-ème ligne et la \(j\)-ème colonne, et \(P\) le produit des \(n^2\) nombres du tableau. Posons \(a_{i,j} = A_{i,j} - 1\) et \(r_i = R_i - 1\). Nous allons montrer que

\[\sum_{i=1}^{n} R_i \equiv (n - 1) + P \pmod{n^4}. \tag{1}\]

Les conditions de l'énoncé étant symétriques entre lignes et colonnes, on aura de même \(\sum_j C_j \equiv (n-1) + P \pmod{n^4}\), d'où la conclusion.

D'après la condition (i), \(n\) divise \(a_{i,j}\) pour tous \(i, j\). Tout produit d'au moins deux \(a_{i,j}\) est donc divisible par \(n^2\), et en développant,

\[R_i = \prod_{j=1}^{n} (1 + a_{i,j}) = 1 + \sum_{j=1}^{n} a_{i,j} + \sum_{1 \leq j_1 < j_2 \leq 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} \pmod{n^2}\]

pour tout \(i\). D'après la condition (ii), \(\sum_j A_{i,j} \equiv n \pmod{n^2}\), donc \(R_i \equiv 1 \pmod{n^2}\), c'est-à-dire \(n^2 \mid r_i\).

Par conséquent, tout produit d'au moins deux \(r_i\) est divisible par \(n^4\). Le même argument donne

\[P = \prod_{i=1}^{n} R_i = \prod_{i=1}^{n} (1 + r_i) \equiv 1 + \sum_{i=1}^{n} r_i \pmod{n^4},\]

d'où

\[\sum_{i=1}^{n} R_i = n + \sum_{i=1}^{n} r_i \equiv n + (P - 1) \pmod{n^4},\]

ce qui est (1). \(\blacksquare\)

Solution 2¶

Voici une façon plus directe (mais plus longue) d'établir (1), avec les mêmes notations \(a_{i,j} = A_{i,j} - 1\).

D'après (i), tous les \(a_{i,j}\) sont divisibles par \(n\), donc tout produit d'au moins quatre d'entre eux est divisible par \(n^4\). En développant,

\[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} \pmod{n^4},\]

où les deux dernières sommes portent sur les paires (resp. triplets) non ordonnées de couples \((i,j)\) deux à deux distincts ; on utilise cette convention dans toute la suite. De même,

\[\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} \pmod{n^4}.\]

Dans la différence ne restent que les termes faisant intervenir au moins deux lignes distinctes :

\[P + (n - 1) - \sum_i R_i \equiv \underbrace{\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}}_{\Sigma_1} + \underbrace{\sum_{\substack{(i_1,j_1),(i_2,j_2),(i_3,j_3) \\ i_1, i_2, i_3 \text{ distincts}}} a_{i_1,j_1} a_{i_2,j_2} a_{i_3,j_3}}_{\Sigma_2} + \underbrace{\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}}_{\Sigma_3} \pmod{n^4}.\]

Montrons que chacune de ces trois sommes est divisible par \(n^4\), ce qui donnera (1). D'après la condition (ii),

\[\sum_{j} a_{i,j} = \sum_j A_{i,j} - n \equiv 0 \pmod{n^2} \quad \text{pour tout } i.\]

Pour deux indices de lignes \(i_1 < i_2\),

\[\sum_{j_1} \sum_{j_2} a_{i_1,j_1} a_{i_2,j_2} = \Big(\sum_{j_1} a_{i_1,j_1}\Big) \cdot \Big(\sum_{j_2} a_{i_2,j_2}\Big) \equiv 0 \pmod{n^4},\]

car chaque facteur est divisible par \(n^2\). En sommant sur toutes les paires \((i_1, i_2)\), on obtient \(n^4 \mid \Sigma_1\).

De même, pour trois indices \(i_1 < i_2 < i_3\),

\[\sum_{j_1} \sum_{j_2} \sum_{j_3} a_{i_1,j_1} a_{i_2,j_2} a_{i_3,j_3} = \Big(\sum_{j_1} a_{i_1,j_1}\Big) \cdot \Big(\sum_{j_2} a_{i_2,j_2}\Big) \cdot \Big(\sum_{j_3} a_{i_3,j_3}\Big),\]

qui est même divisible par \(n^6\). Donc \(n^4 \mid \Sigma_2\).

Enfin, pour des indices \(i_1 \neq i_2 = i_3\) et \(j_2 < j_3\),

\[\sum_{j_1} a_{i_2,j_2} \cdot a_{i_2,j_3} \cdot a_{i_1,j_1} = a_{i_2,j_2} \cdot a_{i_2,j_3} \cdot \Big(\sum_{j_1} a_{i_1,j_1}\Big) \equiv 0 \pmod{n^4},\]

car les trois facteurs sont divisibles respectivement par \(n\), \(n\) et \(n^2\). En sommant sur tous les quadruplets \((i_1, i_2, j_2, j_3)\), on obtient \(n^4 \mid \Sigma_3\). Cela établit (1), et on conclut comme dans la solution 1. \(\blacksquare\)

Remarques¶

Remarque 1. La version originale de l'énoncé contenait aussi la condition (iii) : le produit de tous les nombres du tableau est congru à \(1\) modulo \(n^4\). Cette condition s'est révélée superflue et a été supprimée.