Divisibilité, PGCD et congruences
Ce qui se cache derrière les astuces d'une feuille de terminale

Résumé

En terminale, on calcule \((2n+1)\pgcd(n+3)\) en écrivant \(2n+1=2(n+3)-5\), et l'on conclut que ce PGCD divise \(5\). Le geste est familier, mais il soulève une question : quelles transformations du couple \((a,b)\) a-t-on le droit de faire sans changer le PGCD ? On reprend une feuille de révision de terminale (divisibilité, PGCD, congruences) en cherchant, derrière chaque astuce, l'énoncé général qui la rend évidente. La réponse à la question de départ est l'action du groupe \(\GL_2(\Z)\). Viennent ensuite le coût de l'algorithme d'Euclide (théorème de Lamé), le développement de Pierce, l'exposant du groupe \((\Z/n\Z)^\times\), l'obstruction modulo \(16\) dans le problème de Waring pour les puissances quatrièmes et le paramétrage des triplets pythagoriciens. Deux énoncés de la feuille d'origine étaient faux ; on explique pourquoi et on les corrige (remarques 2.3 et 5.3).

Théorème 2.1. Soit \(M=\begin{pmatrix}\alpha&\beta\\\gamma&\delta\end{pmatrix}\in M_2(\Z)\), et pour \((a,b)\in\Z^2\) posons \(\begin{pmatrix}a'\\b'\end{pmatrix}=M\begin{pmatrix}a\\b\end{pmatrix}\), \(d=a\pgcd b\), \(d'=a'\pgcd b'\).

1. On a \(d\mid d'\) et \(d'\mid (\det M)\,d\).
2. En particulier, si \(M\in\GL_2(\Z)\), c'est-à-dire \(\det M=\pm1\), alors \(d'=d\).
3. Réciproquement, si \(d'=d\) pour tout \((a,b)\in\Z^2\), alors \(\det M=\pm1\).

Démonstration. 1. Tout diviseur commun de \(a\) et \(b\) divise \(a'=\alpha a+\beta b\) et \(b'=\gamma a+\delta b\), donc \(d\mid d'\). Pour l'autre sens, on utilise la comatrice : \({}^t\!\com(M)\,M=(\det M)\,I_2\). Les entiers \((\det M)\,a\) et \((\det M)\,b\) sont donc des combinaisons entières de \(a'\) et \(b'\). Ainsi \(d'\) les divise, donc divise leur PGCD, qui est \(|\det M|\,d\).

2. Si \(\det M=\pm1\), on a \(d\mid d'\) et \(d'\mid d\), d'où \(d=d'\) puisque les deux sont positifs.

3. Supposons \(\det M\neq\pm1\) et construisons \((a,b)\) avec \(a\pgcd b=1<d'\).

Si \(\det M=0\), les colonnes de \(M\) sont liées. Il existe donc \((a,b)\neq(0,0)\), qu'on peut prendre premiers entre eux en divisant par leur PGCD, avec \(M\binom{a}{b}=0\). Alors \(d'=0\neq 1\).

Sinon, soit \(p\) premier divisant \(\det M\). La réduction \(\overline M\in M_2(\F_p)\) a un déterminant nul, donc n'est pas inversible. Il existe donc \((u,v)\in\F_p^2\) non nul avec \(\overline M\binom{u}{v}=0\). Quitte à échanger les rôles des deux coordonnées, \(u\neq0\). On choisit \(a\in\{1,\dots,p-1\}\) représentant \(u\). Il reste à choisir \(b\) dans la classe \(v\) modulo \(p\), premier avec \(a\). Comme \(a\pgcd p=1\), les entiers \(v+kp\), \(0\leq k<a\), parcourent toutes les classes modulo \(a\). L'un d'eux, noté \(b\), vérifie \(b\equiv 1\pmod a\), donc \(a\pgcd b=1\). Par construction, \(a'\equiv b'\equiv0\pmod p\), donc \(p\mid d'\) et \(d'\neq d\). ∎

Remarque 2.2. Pourquoi le déterminant, et pas autre chose ? Parce que la question « peut-on revenir en arrière avec des coefficients entiers ? » est exactement la question « \(M^{-1}\) est-elle à coefficients entiers ? ». Comme \(\det M\cdot\det M^{-1}=1\) dans \(\Z\), cela force \(\det M=\pm1\). Le théorème dit que cette condition algébrique est aussi la bonne condition arithmétique.

Remarque 2.3. La feuille d'origine demandait de montrer que \(a\pgcd b=(\alpha a+\beta b)\pgcd(\gamma a+\delta b)\) pour tous entiers \(\alpha,\beta,\gamma,\delta\). C'est faux. Prenons \(M=\begin{pmatrix}1&1\\1&-1\end{pmatrix}\), de déterminant \(-2\), et \((a,b)=(1,1)\). On obtient \((a',b')=(2,0)\), de PGCD \(2\), alors que \(1\pgcd1=1\). Ce contre-exemple n'est pas un hasard : c'est celui que fabrique la preuve du point 3. Avec \(p=2\), le noyau de \(\overline M\) est engendré par \((1,1)\), et l'on prend \(a=b=1\). Le théorème 2.1 dit exactement quand l'énoncé est vrai : quand \(\det M=\pm1\).

Exemple 2.4. Soit \(n\geq5\), \(a=n^3-n^2-12n\) et \(b=2n^2-7n-4\). On cherche \(a\pgcd b\).

Première étape : factoriser. On trouve \[ a=n(n-4)(n+3), \qquad b=(n-4)(2n+1). \] Le facteur \(n-4>0\) est commun. Il reste à comparer \(n(n+3)\) et \(2n+1\).

Deuxième étape : deux PGCD élémentaires, par le théorème.

• On a \(\binom{2n+1}{n+3}=\begin{pmatrix}2&1\\1&3\end{pmatrix}\binom{n}{1}\), de déterminant \(5\). Donc \((2n+1)\pgcd(n+3)\) divise \(5\,(n\pgcd 1)=5\). Il vaut \(5\) si et seulement si \(n\equiv2\pmod5\), puisque \(2n+1\equiv0\) et \(n+3\equiv0\pmod 5\) équivalent tous deux à \(n\equiv2\pmod5\).
• On a \(\binom{n}{2n+1}=\begin{pmatrix}1&0\\2&1\end{pmatrix}\binom{n}{1}\), de déterminant \(1\). Donc \(n\pgcd(2n+1)=n\pgcd1=1\).

Troisième étape : recoller. Par le lemme de Gauss, si \(c\pgcd n=1\), alors \((nm)\pgcd c=m\pgcd c\) : un facteur premier avec \(c\) ne change pas le PGCD. Comme \(n\pgcd(2n+1)=1\), on peut enlever le facteur \(n\) : \[ a\pgcd b=(n-4)\cdot\big(n(n+3)\pgcd(2n+1)\big)=(n-4)\cdot\big((n+3)\pgcd(2n+1)\big) =\begin{cases} 5(n-4) & \text{si } n\equiv 2 \pmod 5,\\ n-4 & \text{sinon.}\end{cases} \]

Vérification. Pour \(n=7\), on a \(7\equiv2\pmod5\). On calcule \(a=343-49-84=210\) et \(b=98-49-4=45\). Et en effet \(210\pgcd45=15=5\cdot(7-4)\).

Remarque 2.5. Le théorème dit que l'orbite de \((a,b)\) sous \(\GL_2(\Z)\) est contenue dans \(\{(a',b') : a'\pgcd b'=d\}\). En fait elle lui est égale. Une étape de l'algorithme d'Euclide s'écrit \[ \begin{pmatrix}b\\a-qb\end{pmatrix}=\begin{pmatrix}0&1\\1&-q\end{pmatrix}\begin{pmatrix}a\\b\end{pmatrix}, \qquad \det\begin{pmatrix}0&1\\1&-q\end{pmatrix}=-1 . \] L'algorithme est donc une suite de multiplications par des matrices de \(\GL_2(\Z)\), qui ramène \((a,b)\) à \((d,0)\). Tout couple de PGCD \(d\) est ainsi dans l'orbite de \((d,0)\). En particulier, les vecteurs primitifs de \(\Z^2\) (ceux de PGCD \(1\)) forment une seule orbite, celle de \((1,0)\).

Exemple 2.6. Pour \((210,45)\) : \(210=4\cdot45+30\), puis \(45=1\cdot30+15\), puis \(30=2\cdot15+0\). On passe successivement par \[ (210,45)\longmapsto(45,30)\longmapsto(30,15)\longmapsto(15,0), \] avec les quotients \(q=4\), \(1\), \(2\). Le produit des trois matrices correspondantes envoie \((210,45)\) sur \((15,0)\).

Théorème 2.7 (Lamé, 1844). Soit \(a>b\geq1\). Si l'algorithme d'Euclide appliqué à \((a,b)\) effectue \(k\) divisions, alors \(b\geq F_{k+1}\) et \(a\geq F_{k+2}\). Par conséquent \(k\leq 1+\log_\varphi b\).

Démonstration. On pose \(r_0=a\), \(r_1=b\) et \(r_{i-1}=q_ir_i+r_{i+1}\) avec \(0\leq r_{i+1}<r_i\), pour \(1\leq i\leq k\), où \(r_k\neq0\) et \(r_{k+1}=0\).

• On a \(r_k\geq1=F_2\).
• Ensuite \(r_{k-1}=q_kr_k>r_k\) impose \(q_k\geq2\), donc \(r_{k-1}\geq2=F_3\).
• Pour \(i<k\), on a \(q_i\geq1\), donc \(r_{i-1}\geq r_i+r_{i+1}\).

Une récurrence descendante donne alors \(r_{k-j}\geq F_{j+2}\) pour \(0\leq j\leq k\) : pour \(j\geq2\), on a \(r_{k-j}\geq r_{k-j+1}+r_{k-j+2}\geq F_{j+1}+F_{j}=F_{j+2}\). Avec \(j=k-1\) et \(j=k\), on obtient \(b\geq F_{k+1}\) et \(a\geq F_{k+2}\).

Enfin \(F_{k+1}\geq\varphi^{k-1}\), par récurrence : c'est vrai pour \(k=0\) et \(k=1\), et l'hérédité vient de \(\varphi^{k-2}+\varphi^{k-3}=\varphi^{k-3}(\varphi+1)=\varphi^{k-1}\), car \(\varphi^2=\varphi+1\). Donc \(b\geq\varphi^{k-1}\), c'est-à-dire \(k\leq1+\log_\varphi b\). ∎

Remarque 2.8. La borne est atteinte pour deux termes consécutifs de la suite de Fibonacci : tous les quotients valent \(1\), sauf le dernier, qui vaut \(2\). Par exemple, pour \((13,8)=(F_7,F_6)\), \[ 13=1\cdot8+5,\quad 8=1\cdot5+3,\quad 5=1\cdot3+2,\quad 3=1\cdot2+1,\quad 2=2\cdot1+0 . \] On fait \(k=5\) divisions, et l'on a bien \(b=8=F_6=F_{k+1}\) et \(a=13=F_7=F_{k+2}\). La figure 1 montre ce trajet dans le plan : chaque étape est une matrice de \(\GL_2(\mathbb{Z})\), et les couples successifs restent collés à la droite de pente \(1/\varphi\), puisque \(F_{k}/F_{k+1}\to1/\varphi\). Les restes décroissent donc d'un facteur \(\varphi\) à chaque étape, et pas plus vite : c'est exactement le pire cas. Le coût est donc \(O(\log b)\) divisions. Comme la taille de \(b\) (son nombre de chiffres) est de l'ordre de \(\log b\), l'algorithme est linéaire en la taille des entrées.

Figure 1. L'algorithme d'Euclide sur \((13,8)\). Chaque flèche est la multiplication par une matrice \(\begin{pmatrix}0&1\\1&-q\end{pmatrix}\) de déterminant \(-1\), ici toujours avec \(q=1\) sauf à la dernière étape. Le trajet aboutit à \((1,0)\) : tous ces couples sont dans l'orbite de \((1,0)\), et ils longent la droite de pente \(1/\varphi\).

Proposition 3.1. Soit \(0<x<y\) deux entiers. On pose \(r_0=x\), puis, tant que \(r_{i-1}\neq0\), on effectue la division euclidienne \(y=q_ir_{i-1}+r_i\) avec \(0\leq r_i<r_{i-1}\). L'algorithme s'arrête après un nombre fini \(n\) d'étapes, avec \(r_n = 0\), et \[ \frac{x}{y}=\frac1{q_1}-\frac1{q_1q_2}+\frac1{q_1q_2q_3}-\cdots+\frac{(-1)^{n+1}}{q_1q_2\cdots q_n}, \qquad 1\leq q_1<q_2<\cdots<q_n . \]

Démonstration. Les restes \(r_0>r_1>\cdots\) sont des entiers positifs, donc l'algorithme s'arrête.

Comme \(y-r_i=q_ir_{i-1}\), on a, pour \(i\geq1\), \[ \frac{r_{i-1}}{y}=\frac{1}{q_i}-\frac{1}{q_i}\cdot\frac{r_i}{y}. \] On part de \(r_0/y=x/y\), on remplace \(r_1/y\) par son expression en fonction de \(r_2/y\), et ainsi de suite jusqu'à \(r_n=0\). On obtient la formule annoncée.

Pour la croissance, on a d'abord \(q_{i+1}=\lfloor y/r_i\rfloor\geq\lfloor y/r_{i-1}\rfloor=q_i\) puisque \(r_i<r_{i-1}\). Supposons maintenant \(q_{i+1}=q_i=q\). Alors \(y=qr_{i-1}+r_i=qr_i+r_{i+1}\), d'où \(q(r_{i-1}-r_i)=r_{i+1}-r_i\). Le membre de gauche est \(>0\) et celui de droite \(<0\), ce qui est absurde. La croissance est donc stricte. ∎

Exemple 3.2. Développons \(17/45\). On divise \(45\) par les restes successifs : \[ 45=2\cdot17+11,\qquad 45=4\cdot11+1,\qquad 45=45\cdot1+0 . \] Les quotients sont \(2<4<45\), donc \[ \frac{17}{45}=\frac12-\frac1{2\cdot4}+\frac1{2\cdot4\cdot45} =\frac{180-45+1}{360}=\frac{136}{360}. \] On vérifie que \(136/360=17/45\) en simplifiant par \(8\).

Pour \(2/(2k+1)\) avec \(k\geq1\) : \(2k+1=k\cdot2+1\), puis \(2k+1=(2k+1)\cdot1+0\). Donc \(\dfrac{2}{2k+1}=\dfrac1k-\dfrac1{k(2k+1)}\).

Remarque 3.3. Le même algorithme, appliqué à un réel \(t\in\,]0,1[\) (avec \(q_i=\lfloor 1/t_{i-1}\rfloor\), \(t_0=t\), \(t_i=1-q_it_{i-1}\)), s'arrête si et seulement si \(t\) est rationnel. Par exemple \(\frac1e=\sum_{k\geq0}\frac{(-1)^k}{k!}=\frac12-\frac1{2\cdot3}+\frac1{2\cdot3\cdot4}-\cdots\) a pour chiffres \(q_i=i+1\). La condition de croissance stricte est indispensable : sans elle, le développement n'est pas unique, puisque \(\frac1q-\frac1{q(q+1)}=\frac1{q+1}\).

Exemple 4.1 (Exercices 9 et 12 de la feuille).

1. On cherche le chiffre des unités de \(\sum_{i=0}^{400}7^i\). On travaille modulo \(10\). On a \(\lambda(10)=\operatorname{ppcm}(1,4)=4\), et en effet les puissances de \(7\) modulo \(10\) forment le cycle \(1,7,9,3\), de somme \(20\equiv0\). Comme la somme a \(401=4\cdot100+1\) termes, elle contient \(100\) cycles complets, de contribution nulle, plus le dernier terme \(7^{400}\equiv1\). On obtient \(\sum_{i=0}^{400}7^i\equiv1\pmod{10}\) : le chiffre des unités est \(1\).

   On peut aussi passer par la formule \(\frac{7^{401}-1}{6}\). Mais attention : diviser par \(6\) n'est pas permis modulo \(10\), car \(6\) n'y est pas inversible. Il faut connaître \(7^{401}-1\) modulo \(60\) pour connaître le quotient modulo \(10\). Comme \(\lambda(60)=4\), on a \(7^{401}\equiv7\pmod{60}\), donc \(7^{401}-1\equiv6\pmod{60}\) et le quotient est \(\equiv1\pmod{10}\).

2. On veut montrer que \(\dfrac{(7^{2004})^{2014}-(3^{2004})^{2014}}{2014-2004}\) est un entier. Soit \(N=2004\cdot2014\), multiple de \(4\). Comme \(\lambda(10)=4\), on a \(7^N\equiv3^N\equiv1\pmod{10}\), donc \(10\) divise \(7^N-3^N\). Le quotient est bien entier. Comme \(\lambda(40)=\operatorname{ppcm}(2,4)=4\), on a même \(40\mid 7^N-3^N\).

Proposition 4.2 (Exercice 5 de la feuille). On note \(R_k=\frac{10^k-1}{9}=\underbrace{1\cdots1}_{k}\).

1. Tout entier \(n\geq1\) possède un multiple dont l'écriture décimale ne comporte que des \(0\) et des \(1\).
2. Si \(n\pgcd 10=1\), alors \(n\mid R_k\) si et seulement si \(\ord_{9n}(10)\mid k\). En particulier \(n\) divise un nombre formé uniquement de \(1\).

Démonstration. 1. Parmi \(R_1,\dots,R_{n+1}\), deux ont le même reste modulo \(n\) (principe des tiroirs), disons \(R_p\) et \(R_{p'}\) avec \(p<p'\). Alors \(n\) divise \(R_{p'}-R_p=10^p R_{p'-p}\), qui s'écrit avec \(p'-p\) chiffres \(1\) suivis de \(p\) chiffres \(0\).

2. On a \(n\mid R_k\iff 9n\mid 10^k-1\iff 10^k\equiv1\pmod{9n}\), et \(10\) est inversible modulo \(9n\) car \(n\pgcd10=1\). Les \(k\) qui conviennent sont donc les multiples de l'ordre de \(10\) modulo \(9n\). ∎

Exemple 4.3. Pour \(n=6\) (non premier à \(10\)), on applique le point 1. Modulo \(6\), on a \(R_1=1\), \(R_2=11\equiv5\), \(R_3=111\equiv3\), \(R_4=1111\equiv1\). Les restes de \(R_1\) et \(R_4\) coïncident, donc \(6\) divise \(R_4-R_1=1110=6\cdot185\).

Pour \(n=7\), on applique le point 2. On a \(\ord_7(10)=6\) et \(\ord_9(10)=1\), donc \(\ord_{63}(10)=\operatorname{ppcm}(6,1)=6\). Ainsi \(R_6=111111=7\cdot15873\), et aucun \(R_k\) plus court n'est multiple de \(7\).

Proposition 4.4 (Exercice 13 de la feuille). Tout entier \(n\geq1\) possède un multiple dont l'écriture décimale contient les dix chiffres.

Démonstration. Soit \(A=1234567890\) et \(k\) tel que \(10^k\geq n\). Les \(n\) entiers consécutifs \(A\cdot10^k+j\), \(0\leq j<n\), commencent tous par les chiffres de \(A\), puisque \(j<10^k\) ne touche que les \(k\) derniers chiffres. L'un d'eux est multiple de \(n\). ∎

Exemple 4.5. Pour \(n=7\), on prend \(k=1\). On a \(1234567890\equiv3\pmod7\), donc \(12345678900\equiv30\equiv2\pmod 7\). Avec \(j=5\), on trouve \(12345678905=7\cdot1763668415\).

Lemme 5.1. Pour \(x\in\Z\), \(x^4\equiv0\pmod{16}\) si \(x\) est pair et \(x^4\equiv1\pmod{16}\) si \(x\) est impair.

Démonstration. Si \(x=2t\) est pair, \(x^4=16t^4\). Si \(x=2t+1\) est impair, \(x^2=4t(t+1)+1\), et \(t(t+1)\) est pair, donc \(x^2=1+8m\). Alors \(x^4=1+16m+64m^2\equiv1\pmod{16}\). ∎

Proposition 5.2. Un entier \(N\equiv15\pmod{16}\) n'est pas somme de moins de \(15\) puissances quatrièmes. En particulier \(79=4\cdot2^4+15\cdot1^4\) n'est pas somme de moins de \(19\) puissances quatrièmes.

Démonstration. La première assertion découle du lemme 5.1, comme on vient de l'expliquer. Pour \(79\), on peut faire mieux, car \(79\) est petit. Les seules puissances quatrièmes utilisables sont \(1\) et \(16\), puisque \(3^4=81>79\). Une écriture \(79=16a+b\) avec \(a\) seizes et \(b\) uns utilise \(a+b=79-15a\) termes, avec \(a\leq4\). Ce nombre est minimal pour \(a=4\) et vaut alors \(19\). ∎

Remarque 5.3. La feuille d'origine affirmait que \(2005\) n'est pas somme de six puissances quatrièmes non nulles. Elle donnait pourtant l'égalité \(2005=1^4+1^4+1^4+3^4+5^4+6^4=1+1+1+81+625+1296\), qui la contredit. L'énoncé correct porte sur \(2015\). Comme \(2015=16\cdot125+15\), la proposition 5.2 montre que \(2015\) n'est pas somme de six puissances quatrièmes, ni même de quatorze. Pour \(2005=16\cdot125+5\), la congruence n'interdit rien à partir de cinq termes, et l'on voit qu'il en suffit de six.

Proposition 5.4. Pour tout \(k\geq0\), l'entier \(31\cdot16^k\) n'est pas somme de \(15\) puissances quatrièmes (positives ou nulles). Il y a donc une infinité d'entiers qui ne sont pas somme de \(15\) puissances quatrièmes.

Démonstration. Par récurrence sur \(k\).

Pour \(k=0\) : dans une écriture \(31=\sum_{i=1}^{15}x_i^4\), le nombre de \(x_i\) impairs est \(\equiv31\equiv15\pmod{16}\) et \(\leq15\), donc tous les \(x_i\) sont impairs. Comme \(3^4=81>31\), ils valent tous \(\pm1\), et la somme vaut \(15\neq31\).

Pour \(k\geq1\) : si \(31\cdot16^k=\sum_{i=1}^{15}x_i^4\), le nombre de \(x_i\) impairs est \(\equiv0\pmod{16}\) et \(\leq15\), donc nul. Tous les \(x_i\) sont pairs. En divisant par \(16=2^4\), on obtient \(31\cdot16^{k-1}=\sum(x_i/2)^4\), ce qui contredit l'hypothèse de récurrence. ∎

Remarque 5.5. Notons \(g(4)\) le plus petit \(s\) tel que tout entier soit somme de \(s\) puissances quatrièmes, et \(G(4)\) le plus petit \(s\) tel que tout entier assez grand le soit. Les propositions précédentes donnent \(g(4)\geq19\) (à cause de \(79\)) et \(G(4)\geq16\) (à cause des \(31\cdot16^k\)). Ces bornes sont exactes : \(G(4)=16\) (Davenport, 1939) et \(g(4)=19\) (Balasubramanian, Deshouillers et Dress, 1986). Les minorations sont élémentaires, comme on vient de le voir ; toute la difficulté est dans les majorations. Le chapitre 21 de Hardy et Wright [3] raconte cette histoire et démontre une partie des majorations.

Théorème 6.1. Les solutions de \(x^2+y^2=z^2\) en entiers \(x,y,z\geq1\) avec \(x\pgcd y=1\) et \(y\) pair sont exactement \[ x=u^2-v^2,\qquad y=2uv,\qquad z=u^2+v^2, \] avec \(u>v\geq1\), \(u\pgcd v=1\) et \(u\not\equiv v\pmod 2\).

Démonstration. Ces triplets conviennent. L'identité \((u^2-v^2)^2+(2uv)^2=(u^2+v^2)^2\) se vérifie en développant. Si un premier \(p\) divisait \(x\) et \(y\), il diviserait \(z\), donc \(z+x=2u^2\) et \(z-x=2v^2\). Comme \(x\) est impair (car \(u\not\equiv v\pmod2\)), \(p\) est impair, donc \(p\) diviserait \(u^2\) et \(v^2\), ce qui est exclu par \(u\pgcd v=1\).

Ce sont les seuls. Si \(x\pgcd y=1\), alors \(x\) et \(y\) ne sont pas tous deux pairs. Ils ne sont pas non plus tous deux impairs, sinon \(z^2\equiv1+1=2\pmod4\), alors qu'un carré est \(\equiv0\) ou \(1\pmod4\). Avec \(y\) pair, \(x\) et \(z\) sont impairs, et \[ \frac{z+x}{2}\cdot\frac{z-x}{2}=\Big(\frac y2\Big)^2 . \] Un diviseur commun des deux facteurs divise leur somme \(z\) et leur différence \(x\). Or \(x\pgcd z=1\), car un nombre premier qui divise \(x\) et \(z\) divise \(z^2-x^2=y^2\), donc \(y\), ce qui contredit \(x\pgcd y=1\). Les deux facteurs sont donc premiers entre eux, positifs, et leur produit est un carré. Par factorialité de \(\Z\), ce sont des carrés \(u^2\) et \(v^2\), ce qui donne \(z=u^2+v^2\), \(x=u^2-v^2\) et \(y=2uv\). Les conditions sur \(u\) et \(v\) viennent de \(x\pgcd y=1\) et de la parité de \(x\). ∎

Exemple 6.2. Avec \((u,v)=(2,1)\), on trouve \((3,4,5)\). Avec \((u,v)=(3,2)\), on trouve \((5,12,13)\). Avec \((u,v)=(4,1)\), on trouve \((15,8,17)\). En revanche \((u,v)=(3,1)\) est exclu, car \(u\equiv v\pmod 2\) : il donnerait \((8,6,10)\), qui n'est pas primitif.

Corollaire 6.3 (Exercice 3 de la feuille). Si \(x^2+y^2=z^2\) avec \(x,y,z\geq1\), alors \(3\mid xy\), l'un de \(x,y\) est multiple de \(4\), et \(5\mid xyz\). En particulier \(60\mid xyz\), et \(60\) est optimal puisque \((3,4,5)\) donne \(60\).

Démonstration. On écrit \((x,y,z)=e\,(x_0,y_0,z_0)\) avec \((x_0,y_0,z_0)\) primitif et, quitte à échanger \(x\) et \(y\), \(y_0=2uv\) comme dans le théorème. Il suffit de traiter le triplet primitif, car multiplier par \(e\) conserve les divisibilités.

• L'un de \(u,v\) est pair, donc \(4\mid 2uv=y_0\).
• On a \(x_0y_0=2uv(u^2-v^2)\). Si \(3\nmid uv\), alors \(u^2\equiv v^2\equiv1\pmod3\), donc \(3\mid u^2-v^2\).
• On a \(x_0y_0z_0=2uv(u^4-v^4)\). Si \(5\nmid uv\), le petit théorème de Fermat donne \(u^4\equiv v^4\equiv1\pmod5\), donc \(5\mid u^4-v^4\).

Comme \(3\), \(4\) et \(5\) sont premiers entre eux deux à deux, \(60\mid xyz\). ∎

Exemple 6.4. Pour \((5,12,13)\) : \(3\) divise \(xy=60\), \(4\) divise \(12\), \(5\) divise \(5\), et \(xyz=780=60\cdot13\).

Remarque 6.5. On peut aussi raisonner directement sur les carrés modulo \(3\), \(8\) et \(5\), comme le suggérait la feuille. Le paramétrage a deux autres interprétations, qui expliquent pourquoi il existe. La première est la factorisation \(z^2=(x+iy)(x-iy)\) dans l'anneau factoriel \(\Z[i]\) : c'est le même argument « produit de deux facteurs premiers entre eux qui est un carré ». La seconde est géométrique : c'est le paramétrage rationnel du cercle unité par la droite de pente \(t=v/u\) passant par \((-1,0)\) (figure 2). En effet, un triplet \(x^2+y^2=z^2\) donne le point rationnel \((x/z,\,y/z)\) du cercle \(X^2+Y^2=1\). La droite \(Y=t(X+1)\) recoupe le cercle en un second point, qu'on trouve en résolvant une équation du second degré dont on connaît déjà la racine \(X=-1\) : \[ X=\frac{1-t^2}{1+t^2},\qquad Y=\frac{2t}{1+t^2}. \] Avec \(t=v/u\), on obtient \(X=\dfrac{u^2-v^2}{u^2+v^2}\) et \(Y=\dfrac{2uv}{u^2+v^2}\) : c'est le paramétrage du théorème 6.1. Les points rationnels du cercle correspondent ainsi aux pentes rationnelles.

Figure 2. La droite de pente \(t\) passant par \((-1,0)\) recoupe le cercle unité au point \(\big(\frac{1-t^2}{1+t^2},\frac{2t}{1+t^2}\big)\). Pour \(t=\frac12\), c'est-à-dire \((u,v)=(2,1)\), on obtient \(\big(\frac35,\frac45\big)\) et le triplet \((3,4,5)\).

Exercice 1. Déterminer les \(n\in\N\) tels que \(n+1\mid 3n^2+15n+19\).

Exercice 2. Soit \(n\geq1\), \(M=9n-1\) et \(N=9n+1\). Calculer \(M\pgcd N\) selon la parité de \(n\), et montrer que \(4\mid 81n^2-1\) si et seulement si \(n\) est impair.

Exercice 3. Un rectangle \(a\times b\) (\(a,b\geq1\) entiers) est découpé en \(ab\) carrés unités. Combien de carrés la diagonale traverse-t-elle (en passant par leur intérieur) ?

Exercice 4. Trouver tous les entiers \(0<a<b<c\) avec \(abc<2003\) tels que la somme de deux quelconques d'entre eux soit divisible par le troisième.

Exercice 5. On a \(1089\times9=9801\). Trouver un entier à quatre chiffres \(N\) tel que \(4N\) s'écrive avec les chiffres de \(N\) dans l'ordre inverse.

Exercice 6. Soit \(s\geq1\). Montrer que les sommes de \(s\) puissances quatrièmes ne recouvrent pas toutes les classes modulo \(16\) si \(s\leq14\), et les recouvrent toutes si \(s\geq15\).

Figure 3. Dans un rectangle \(6\times4\), la diagonale traverse les \(8=6+4-2\) carrés grisés. Elle passe par les points entiers \((0,0)\), \((3,2)\) et \((6,4)\) : il y en a \(6\wedge4+1=3\).