Exercice 1 — Potentiel carré — Olympiades 2015 Guyane

Sujet

Dans tout le problème, on dira qu'un entier \(n\) est un carré, lorsque c'est le carré d'un entier, autrement dit, lorsqu'il existe un entier \(k\) tel que \(k^{2}=n\). Par exemple 4 et 9 sont des carrés, mais pas 5 et 6 .
On appelle potentiel carré d'un entier \(n\) strictement supérieur à 1, et on note \(p c(n)\), le nombre de décompositions de \(n\) en somme de deux entiers non nuls dont le produit est un carré.

Par exemple :

\(p c(3)=0\) car la seule décomposition de 3 en somme de deux entiers non nuls est \(3=1+2\) (on ne considère pas que la décomposition \(3=2+1\) est différente), et \(2 \times 1=2\) n'est pas un carré.
\(p c(4)=1\) car pour la décomposition \(4=2+2\), le nombre \(2 \times 2=4\) est un carré, tandis que pour la décomposition \(4=1+3\), le nombre \(1 \times 3=3\) n'est pas un carré.
\(p c(10)=3\) car en listant les 5 décompositions possibles, exactement 3 donnent un produit qui est un carré, à savoir \(1+9,2+8\) et \(5+5\).

Pour traiter la question 7., on aura besoin des deux définitions suivantes :

Pour deux entier \(n\) et \(d\) non nuls, on dira que \(d\) est un diviseur de \(n\) lorsque \(n\) est un multiple de \(d\), autrement dit, s'il existe un entier \(k\) tel que \(n=k \times d\). Par exemple, 3 est un diviseur de 15 .
On dit qu'un nombre entier \(p\) est premier si \(p \geqslant 2\) et si \(p\) n'admet aucun diviseur autre que 1 et \(p\). Par exemple 15 n'est pas premier, mais 13 est premier.

On aura également besoin du résultat suivant :
Tout nombre entier \(n \geqslant 2\) se décompose de façon unique (à l'ordre des facteurs près) comme produit de nombres premiers (exemple : \(12=2 \times 2 \times 3\) ).

Calculer le potentiel carré de tous les entiers de 2 a 10 .
Exprimer, en fonction de \(n\), le nombre de décompositions à tester pour un entier \(n\) donné. On distinguera les cas \(n\) pair et \(n\) impair.
Montrer que pour tout entier non nul \(n\) pair, on a \(p c(n) \geqslant 1\).
Montrer que si \(n\) peut s'écrire comme la somme de deux entiers carrés non nuls (par exemple, \(13=4+9=2^{2}+3^{2}\) ), alors \(p c(n) \geqslant 1\).
Montrer que si \(n\) et \(k\) sont deux entiers non nuls, alors \(p c(k n) \geqslant p c(n)\).
En utilisant les propriétes des questions 4. et 5 ., démontrer que si \(n\) admet un diviseur pouvant s'écrire comme la somme de deux entiers carrés non nuls (par exemple \(15=3 \times 5\) avec \(5=4+1\) ), alors \(p c(n) \geqslant 1\).
Dans cette question, on va démontrer la réciproque de la propriété précédente. On considère un entier non nul \(n\) tel que \(p c(n) \geqslant 1\). Il existe donc \(a, b\) non nuls tels que \(a+b=n\) et tels que \(a \times b\) soit un carré, qu'on notera \(r^{2}\). Si \(a\) et \(b\) sont eux-mêmes des carrés, la démonstration est terminée. Dans la suite, on suppose que \(a\) et \(b\) ne sont pas tous les deux des carrés.
a) On écrit \(r=p_{1} \times p_{2} \times \cdots \times p_{s}\), avec \(s \geqslant 1\), où \(p_{1}, p_{2}, \ldots, p_{s}\) sont des nombres premiers. Montrer que l'un de ces diviseurs premiers de \(r\), qu'on notera simplement \(p\), est un diviseur à la fois de \(a\) et de \(b\).
b) On note \(a^{\prime}=\frac{a}{p}\) et \(b^{\prime}=\frac{b}{p}\) et \(n^{\prime}=a^{\prime}+b^{\prime}\). Montrer que \(p c\left(n^{\prime}\right) \geqslant 1\).
c) En envisageant le fait de recommencer avec \(n^{\prime}=a^{\prime}+b^{\prime}\) ce qui a été fait précédemment avec \(n=a+b\), établir un raisonnement prouvant que \(n\) admet forcément un diviseur somme de deux carrés.

\(n=1\) n'admet aucune décomposition en somme de deux entiers non nuls : \(p c(1)=0\).

Pour \(n=2\), la seule décomposition est \(2=1+1\) et \(1 \times 1\) est un carré : \(p c(2)=1\).
Pour \(n=5\), il y a deux décompositions : \(5=1+4\) et \(5=2+3\). Seule la première donne un produit carré : \(1 \times 4=4\). On a donc \(p c(5)=1\).
Avec le même raisonnement, on trouve successivement \(p c(6)=1, p c(7)=0, p c(8)=1\) et \(p c(9)=0\).
Les potentiels carrés de 3 , 4 et 10 étaient déjà donnés dans l'énoncé : \(p c(3)=0, p c(4)=1\) et \(p c(10)=3\).

Les décompositions à tester sont \((1, n-1),(2, n-2 q), \ldots\). Si \(n\) est pair, cela s'arrête à \(\left(\frac{n}{2}, \frac{n}{2}\right)\) ce qui donne \(\left(\frac{n}{2}\right)\) décompositions. Si \(n\) est impair, cela s'arrête à \(\left(\frac{n-1}{2}, \frac{n+1}{2}\right)\), ce qui donne \(\frac{n-1}{2}\).
Soit \(n\) un entier pair non nul, et \(k=\frac{n}{2}\). On a donc \(n=2 k=k+k\), avec \(k \neq 0\) et \(k \times k=k^{2}\) est un carré.
On a donc bien \(p c(n) \geqslant 1\).
Soit un entier \(n\) pouvant s'écrire comme la somme de deux entiers carrés non nuls \(n=a^{2}+b^{2}\). \(a^{2} \times b^{2}=(a b)^{2}\) étant un carré, on a \(p c(n) \geqslant 1\).
Soient \(n\) et \(k\) deux entiers non nuls. Si \(p c(n)=0\), on a bien sûr \(p c(k n) \geqslant p c(n)\). Supposons \(s=p c(n) \geqslant 1\), et notons \(\left(a_{1}, b_{1}\right),\left(a_{2}, b_{2}\right), \ldots,\left(a_{s}, b_{s}\right)\) tous les couples d'entiers dont la somme donne \(n\) et dont le produit est un carré. Pour tout \(i \in\{1,2, \ldots, s\}\), on peut écrire \(a_{i} b_{i}=r_{i}^{2}\), pour un certain entier \(r_{i}\), et on a alors:

\[ k a_{i}+k b_{i}=k\left(a_{i}+b_{i}\right)=k n \text { et }\left(k a_{i}\right) \times\left(k b_{i}\right)=k^{2} a_{i} b_{i}=\left(k r_{i}\right)^{2} . \]

L'entier \(k n\) admet donc au moins \(s\) décompositions en somme de deux entiers non nuls dont le produit est un carré. Autrement dit, \(p c(k n) \geqslant s=p c(n)\).
6. Soit \(n\) un entier non nul admettant un diviseur \(d\) pouvant s'écrire comme la somme de deux carrés non nuls, ce qu'on note \(d=a^{2}+b^{2}\). D'après la question 4., on a donc \(p c(d) \geqslant 1\). En notant \(k=\frac{n}{d}\), on a alors, d'après la question \(5 ., p c(n)=p c(k d) \geqslant p c(d) \geqslant 1\).
7. a) Rappelons les hypothèses. On a \(n=a+b\), et \(a b=r^{2}\). On a écrit \(r=p_{1} \times p_{2} \times \cdots \times p_{s}\), avec \(s \geqslant 1\), et \(p_{1}, p_{2}, \ldots, p_{s}\) premiers.
D'autre part, on a supposé que \(a\) et \(b\) ne sont pas tous les deux des carrés.
Commençons par noter qu'on peut écrire :

\[ a b=r^{2}=p_{1}^{2} \times p_{2}^{2} \times \cdot \times p_{s}^{2} . \]

Or \(a\) et \(b\) peuvent également chacun se décomposer comme produit de nombres premiers :

\[ a=a_{1} \times \cdots \times a_{k} \text { et } b=b_{1} \times \cdots \times b_{\ell} . \]

On peut donc également écrire :

\[ a b=a_{1} \times \cdots \times a_{k} \times b_{1} \times \cdots \times b_{\ell} \]