Congruences

Donner le reste, c’est-à-dire l’entier compris entre $0$ et $n-1$ congru au nombre proposé modulo $n$.

1. Reste de $83$ modulo $6$ :
   $83=6\times 13+5$ avec $0⩽5<6$, donc $83\equiv 5[6]$.
2. Reste de $-83$ modulo $6$ :
   $-83=6\times (-13)-5$, et $-5$ n’est pas un reste. On descend d’un multiple de $6$ : $-83=6\times (-14)+1$ avec $0⩽1<6$. Donc $-83\equiv 1[6]$ (et $1=6-5$).
3. Reste de $1000$ modulo $7$ :
   $7\times 142=994$ et $1000-994=6$ : $1000\equiv 6[7]$, c’est-à-dire $1000\equiv -1[7]$.
4. Reste de $-1$ modulo $13$ :
   $-1=13\times (-1)+12$ avec $0⩽12<13$ : $-1\equiv 12[13]$.

Dans cet exercice, les modules $n$ sont des entiers naturels supérieurs ou égaux à $2$.

1. Nombre de modules $n$ tels que $29\equiv 5[n]$ :
   $29\equiv 5[n]$ signifie que $n$ divise $29-5=24$. Les diviseurs de $24$ supérieurs ou égaux à $2$ sont $2$, $3$, $4$, $6$, $8$, $12$ et $24$ : il y a $7$ modules.
2. Le plus grand de ces modules :
   C’est $24$ lui-même : $29=24+5$.
3. Entier $x$ tel que $100⩽x⩽110$ et $x\equiv 3[8]$ :
   $100=8\times 12+4$. Les entiers congrus à $3$ modulo $8$ sont …, $99$, $107$, $115$… : seul $107=8\times 13+3$ est compris entre $100$ et $110$.
4. Plus grand entier strictement négatif $x$ tel que $x\equiv 17[6]$ :
   $17=6\times 2+5$, donc $x\equiv 5[6]$ : $x$ est l’un des entiers …, $-7$, $-1$, $5$, $11$… Le plus grand strictement négatif est $-1$ ; on a bien $17-(-1)=18=6\times 3$.

Soit $a$ un entier dont le reste dans la division euclidienne par $12$ vaut $5$.

1. Justifier que $a\equiv 5[4]$, puis donner le reste de $a$ modulo $4$ :
   Rédaction attendue. Le reste de $a$ par $12$ vaut $5$, donc $a\equiv 5[12]$ : $12$ divise $a-5$. Comme $4$ divise $12$, $4$ divise aussi $a-5$, donc $a\equiv 5[4]$. Or $5=4+1$, donc $a\equiv 1[4]$ : le reste de $a$ par $4$ vaut $1$. Exemple : $17=12+5$ et $17=4\times 4+1$.
2. Reste de $a$ modulo $6$ :
   $6$ divise $12$, donc $a\equiv 5[6]$, et $0⩽5<6$ : le reste vaut $5$.
3. Reste de $a$ modulo $3$ :
   $3$ divise $12$, donc $a\equiv 5[3]$, et $5=3+2$ : le reste vaut $2$.

On cherche les entiers naturels $n⩾2$ tels que $100\equiv 37[n]$ et $50\equiv 8[n]$.

1. Démontrer qu’un module $n$ convient si et seulement si $n$ divise $63$ et $42$. Nombre de modules $n$ qui conviennent :
   Rédaction attendue. $100\equiv 37[n]$ équivaut à « $n$ divise $100-37=63$ », et $50\equiv 8[n]$ à « $n$ divise $50-8=42$ ». Les modules cherchés sont donc les diviseurs communs de $63$ et $42$ supérieurs ou égaux à $2$. Les diviseurs communs de deux entiers sont les diviseurs de leur PGCD : $63=1\times 42+21$ et $42=2\times 21+0$, donc $\text{pgcd}(63;42)=21$. Les diviseurs de $21$ supérieurs ou égaux à $2$ sont $3$, $7$ et $21$ : il y a $3$ modules.
2. Le plus grand module qui convient :
   C’est $21$ : $100-37=63=21\times 3$ et $50-8=42=21\times 2$.
3. Pour ce plus grand module, reste commun de $100$ et de $37$ :
   $100=21\times 4+16$ et $37=21\times 1+16$ : les deux restes valent $16$, comme le veut la caractérisation par les restes.

Soit $a$ et $b$ deux entiers tels que $a\equiv 4[15]$ et $b\equiv 13[15]$. Donner chaque reste entre $0$ et $14$.

1. Reste de $a+b$ modulo $15$ :
   Par compatibilité avec l’addition, $a+b\equiv 4+13=17[15]$, et $17=15+2$ : $a+b\equiv 2[15]$.
2. Reste de $ab$ modulo $15$ :
   $ab\equiv 4\times 13=52[15]$ et $52=3\times 15+7$. Plus court avec $13\equiv -2[15]$ : $ab\equiv 4\times (-2)=-8\equiv 7[15]$.
3. Reste de $a-b$ modulo $15$ :
   $a-b\equiv 4-13=-9[15]$, et $-9+15=6$ : $a-b\equiv 6[15]$.
4. Démontrer que $a^3-b^2$ est divisible par $15$. Reste de $a^3$ modulo $15$ :
   Rédaction attendue. Par compatibilité avec les puissances, $a^3\equiv 4^3=64[15]$, et $64=4\times 15+4$, donc $a^3\equiv 4[15]$. De même $b\equiv -2[15]$ donne $b^2\equiv (-2{)}^2=4[15]$. Par différence, $a^3-b^2\equiv 4-4=0[15]$ : $15$ divise $a^3-b^2$.

On donne $2023=7\times 289$. Donner chaque reste entre $0$ et $6$, sans effectuer les produits.

1. Reste de $2024\times 2025\times 2026$ modulo $7$ :
   $2023\equiv 0[7]$, donc $2024\equiv 1$, $2025\equiv 2$ et $2026\equiv 3[7]$. Par compatibilité avec le produit : $2024\times 2025\times 2026\equiv 1\times 2\times 3=6[7]$.
2. Reste de $2{024}^2+2{026}^2$ modulo $7$ :
   $2{024}^2+2{026}^2\equiv 1^2+3^2[7]$, soit $1+9=10\equiv 3[7]$.
3. Reste de $2020\times 2027$ modulo $7$ :
   $2020=2023-3$, donc $2020\equiv -3[7]$ ; et $2027\equiv 4\equiv -3[7]$. Donc $2020\times 2027\equiv (-3)\times (-3)=9\equiv 2[7]$.

Soit $n$ un entier naturel. On veut démontrer que $3^{2n+1}+2^{n+2}$ est divisible par $7$.

1. $3^{2n+1}=3\times 9^n$ et $9\equiv 2[7]$. On en déduit $3^{2n+1}\equiv k\times 2^n[7]$, où $k$ est un entier compris entre $0$ et $6$ : $k$ =
   $3^{2n+1}=3\times (3^2{)}^n=3\times 9^n$. Comme $9\equiv 2[7]$, la compatibilité avec les puissances donne $9^n\equiv 2^n[7]$, puis celle avec le produit $3^{2n+1}\equiv 3\times 2^n[7]$ : $k=3$.
2. Démontrer que $3^{2n+1}+2^{n+2}$ est divisible par $7$ pour tout entier naturel $n$. Contrôle pour $n=1$ : $3^3+2^3=7\times$
   Rédaction attendue. D’après la question précédente, $3^{2n+1}\equiv 3\times 2^n[7]$. D’autre part $2^{n+2}=4\times 2^n$. Par compatibilité avec l’addition : $3^{2n+1}+2^{n+2}$ $\equiv 3\times 2^n+4\times 2^n$ $=7\times 2^n$ $\equiv 0[7]$. Donc $7$ divise $3^{2n+1}+2^{n+2}$ pour tout entier naturel $n$. Pour $n=1$ : $27+8=35=7\times 5$.
3. Reste de $3^{2n+1}$ modulo $7$ lorsque $n\equiv 2[3]$ :
   Si $n=3q+2$, alors $2^n=(2^3{)}^q\times 2^2=8^q\times 4$. Comme $8\equiv 1[7]$, la compatibilité avec les puissances donne $8^q\equiv 1[7]$, donc $2^n\equiv 4[7]$. D’après la première question, $3^{2n+1}\equiv 3\times 4=12\equiv 5[7]$. De même, le reste vaut $3$ si $n\equiv 0[3]$ et $6$ si $n\equiv 1[3]$.

Simplifier une congruence. Les lettres $a$ et $b$ désignent des entiers.

1. « Si $3a\equiv 3[12]$, alors $a\equiv 1[12]$ » est faux. Plus petit entier naturel $a$ tel que $3a\equiv 3[12]$ et $a\not\equiv 1[12]$ :
   On cherche $a⩾2$ tel que $12$ divise $3a-3$ : $a=2$, $3$, $4$ donnent $3$, $6$, $9$, qui ne sont pas des multiples de $12$, mais $a=5$ donne $3\times 5-3=12$. Ainsi $3\times 5\equiv 3\times 1[12]$ alors que $5\not\equiv 1[12]$ : on ne « divise » pas par $3$.
2. Démontrer que si $3a\equiv 3b[12]$, alors $a-b$ est toujours multiple d’un même entier $m$. Plus grand entier $m$ qui convient pour tous $a$ et $b$ :
   Rédaction attendue. Si $3a\equiv 3b[12]$, il existe un entier $k$ tel que $3a-3b=12k$ ; en divisant cette égalité par $3$, $a-b=4k$ : $a\equiv b[4]$. On ne peut pas faire mieux : avec $a=4$ et $b=0$, on a $3a\equiv 3b[12]$ et $a-b=4$, qui n’est multiple d’aucun entier plus grand que $4$. Donc $m=4$ : on a divisé par $3$ le coefficient et le module.
3. « Si $a^2\equiv 1[8]$, alors $a\equiv 1[8]$ » est faux. Plus petit entier naturel $a$ tel que $a^2\equiv 1[8]$ et $a\not\equiv 1[8]$ :
   $0^2=0$ et $2^2=4$ ne conviennent pas, mais $3^2=9=8+1$, donc $3^2\equiv 1[8]$ alors que $3\not\equiv 1[8]$ : on ne prend pas la racine d’une congruence.

Donner chaque reste, ou le chiffre demandé, en cherchant le cycle des puissances.

1. Reste de $4^{2026}$ modulo $9$ :
   $4^2=16\equiv 7[9]$ et $4^3\equiv 7\times 4=28\equiv 1[9]$ : le cycle a pour longueur $3$. Or $2026=3\times 675+1$, donc $4^{2026}=(4^3{)}^{675}\times 4\equiv 4[9]$.
2. Chiffre des unités de $7^{1001}$ :
   $7^2=49\equiv 9$, $7^3\equiv 63\equiv 3$, $7^4\equiv 21\equiv 1[10]$ : cycle de longueur $4$. $1001=4\times 250+1$, donc $7^{1001}\equiv 7[10]$ : le chiffre des unités est $7$.
3. Reste de $2^{555}$ modulo $7$ :
   $2^3=8\equiv 1[7]$ et $555=3\times 185$, donc $2^{555}=(2^3{)}^{185}\equiv 1[7]$.

Bases congrues à $-1$, puis une base pour laquelle le reste $1$ n’apparaît jamais.

1. Reste de ${14}^{77}$ modulo $15$ :
   $14\equiv -1[15]$ et $77$ est impair : ${14}^{77}\equiv (-1{)}^{77}=-1\equiv 14[15]$.
2. Reste de ${29}^{2026}$ modulo $10$ :
   $29\equiv 9\equiv -1[10]$ et $2026$ est pair : ${29}^{2026}\equiv (-1{)}^{2026}=1[10]$.
3. Démontrer que $2^{m+4}\equiv 2^m[10]$ pour tout entier $m⩾1$, puis donner le chiffre des unités de $2^{2026}$ :
   Rédaction attendue. $2^5=32\equiv 2[10]$. Pour $m⩾1$, $2^{m+4}=2^5\times 2^{m-1}$ $\equiv 2\times 2^{m-1}=2^m[10]$ par compatibilité avec le produit. Les restes se répètent donc tous les $4$ exposants à partir de $m=1$ : $2$, $4$, $8$, $6$. Comme $2026=4\times 506+2$, en appliquant $506$ fois cette relation, $2^{2026}\equiv 2^2=4[10]$ : $2^{2026}$ se termine par $4$. Ici le reste $1$ n’apparaît jamais, car $2$ et $10$ sont tous deux pairs.

Puissances de $3$ modulo $11$. Dans la dernière question, $n$ désigne un entier naturel.

1. Plus petit entier $k⩾1$ tel que $3^k\equiv 1[11]$ :
   $3^2=9$, $3^3=27\equiv 5$, $3^4\equiv 15\equiv 4$, $3^5\equiv 12\equiv 1[11]$ : $k=5$.
2. Reste de $3^{2026}$ modulo $11$ :
   $2026=5\times 405+1$, donc $3^{2026}=(3^5{)}^{405}\times 3\equiv 3[11]$.
3. Démontrer que le reste de $3^{5n+2}$ modulo $11$ ne dépend pas de $n$. Ce reste vaut
   Rédaction attendue. Soit $n\in \mathbb{N}$. $3^{5n+2}=(3^5{)}^n\times 3^2$. Comme $3^5\equiv 1[11]$, la compatibilité avec les puissances donne $(3^5{)}^n\equiv 1[11]$, donc $3^{5n+2}\equiv 3^2=9[11]$ : le reste vaut $9$ pour tout $n$. Par conséquent, $3^{5n+2}+2$ est toujours divisible par $11$.

Soit $n$ un entier naturel. On étudie les puissances de $2$ modulo $31$ ; on rappelle que $2^5=32$.

1. Démontrer que le reste de $2^n$ modulo $31$ ne dépend que du reste de $n$ modulo $5$. Reste de $2^n$ modulo $31$ lorsque $n\equiv 4[5]$ :
   Rédaction attendue. $2^5=32=31+1$, donc $2^5\equiv 1[31]$ : le cycle des puissances de $2$ modulo $31$ a pour longueur $5$. Si $n=5q+r$ avec $0⩽r<5$, alors $2^n=(2^5{)}^q\times 2^r\equiv 2^r[31]$. Les restes possibles sont $1$, $2$, $4$, $8$ et $16$ selon que $r=0$, $1$, $2$, $3$ ou $4$. Pour $n\equiv 4[5]$ : $2^n\equiv 2^4=16[31]$.
2. Démontrer qu’aucun entier naturel $n$ ne rend $2^n+3$ divisible par $31$. Reste que devrait avoir $2^n$ modulo $31$ :
   Rédaction attendue. $31$ divise $2^n+3$ si et seulement si $2^n\equiv -3\equiv 28[31]$. Or, d’après la question précédente, les seuls restes de $2^n$ modulo $31$ sont $1$, $2$, $4$, $8$ et $16$ : $28$ n’en fait pas partie. Aucun entier naturel $n$ ne convient.
3. Reste de $2^{1234}+5$ modulo $31$ :
   $1234=5\times 246+4$, donc $2^{1234}\equiv 2^4[31]$, et $2^{1234}+5\equiv 16+5=21[31]$, avec $0⩽21<31$.
4. Plus petit entier $n⩾10$ tel que $31$ divise $2^n-8$ :
   $2^n\equiv 8=2^3[31]$ équivaut à $n\equiv 3[5]$ ; les entiers concernés sont $3$, $8$, $13$, $18$… Le plus petit supérieur ou égal à $10$ est $13$.

On considère l’entier $2471$. Donner chaque reste sans poser de division.

1. Reste de $2471$ modulo $9$ :
   $10\equiv 1[9]$ : $2471$ est congru à la somme de ses chiffres, $2+4+7+1=14$, et $14\equiv 5[9]$. Contrôle : $9\times 274=2466$ et $2471-2466=5$.
2. Reste de $2471$ modulo $11$ :
   $10\equiv -1[11]$ : somme alternée à partir des unités, $1-7+4-2=-4$, et $-4\equiv 7[11]$. Contrôle : $11\times 224=2464$ et $2471-2464=7$.
3. Reste de $-2471$ modulo $9$ :
   $2471\equiv 5[9]$ donne $-2471\equiv -5\equiv 4[9]$ ; en effet $-2471=9\times (-275)+4$.
4. Reste de $2471$ modulo $3$ :
   $10\equiv 1[3]$ aussi : $2471\equiv 14\equiv 2[3]$.

Un entier $N$ s’écrit avec quatre chiffres : $4$ (milliers), $c$ (centaines), $7$ (dizaines) et $2$ (unités), où $c$ est un chiffre inconnu.

1. Valeur du chiffre $c$ qui fait de $N$ un multiple de $9$ :
   $N\equiv 4+c+7+2=13+c[9]$, avec $13⩽13+c⩽22$ : seul $18$ est un multiple de $9$ dans cet intervalle, d’où $c=5$ ($4572=9\times 508$).
2. Plus grand chiffre $c$ pour lequel $N$ est divisible par $8$ :
   $1000\equiv 0[8]$ : $N$ a le même reste que $100c+72$. Or $72=8\times 9$ et $100=8\times 12+4$, donc $N\equiv 4c[8]$, qui est un multiple de $8$ si et seulement si $c$ est pair. Le plus grand chiffre pair est $8$ : $4872=8\times 609$.
3. Chiffre $c$ pour lequel $N$ est divisible par $11$ :
   Somme alternée depuis les unités : $2-7+c-4=c-9$. Elle doit être un multiple de $11$, avec $-9⩽c-9⩽0$ : $c=9$, et $4972=11\times 452$.

Le critère par $11$.

1. Démontrer qu’un entier naturel est congru modulo $11$ à la somme alternée de ses chiffres, en partant des unités. Reste de $908172$ modulo $11$ :
   Rédaction attendue. $10=11-1$, donc $10\equiv -1[11]$, et par compatibilité avec les puissances ${10}^k\equiv (-1{)}^k[11]$ pour tout entier naturel $k$. Si $N=a_p\times {10}^p+\dots +a_1\times 10+a_0$, la compatibilité avec le produit et la somme donne $N\equiv a_0-a_1+a_2-\dots +(-1{)}^p{a}_p[11]$. Pour $908172$ : $2-7+1-8+0-9=-21$, et $-21+22=1$, donc $908172\equiv 1[11]$.
2. Reste de ${10}^{2025}$ modulo $11$ :
   $2025$ est impair : ${10}^{2025}\equiv (-1{)}^{2025}=-1\equiv 10[11]$.
3. L’entier de cinq chiffres $3$, $x$, $5$, $0$, $8$ (dans cet ordre) est divisible par $11$ pour le chiffre $x$ =
   Somme alternée depuis les unités : $8-0+5-x+3=16-x$. Comme $7⩽16-x⩽16$, le seul multiple de $11$ possible est $11$ : $x=5$, et $35508=11\times 3228$.

Soit $N$ un entier naturel inférieur à un milliard. On écrit $N=c_0+c_1\times {10}^3+c_2\times {10}^6$, où $c_0$, $c_1$, $c_2$ sont ses tranches de trois chiffres lues à partir de la droite (entiers compris entre $0$ et $999$). On donne $1001=7\times 11\times 13$.

1. Démontrer que $N\equiv c_0-c_1+c_2$ modulo $7$ et modulo $13$. Pour $N=1234567$, valeur de $c_0-c_1+c_2$ :
   Rédaction attendue. $1001$ est un multiple de $7$ et de $13$, et ${10}^3=1001-1$, donc ${10}^3\equiv -1$ modulo $7$ et modulo $13$. Par compatibilité avec les puissances, ${10}^6=({10}^3{)}^2\equiv (-1{)}^2=1$. Donc, modulo $7$ comme modulo $13$ : $N=c_0+c_1\times {10}^3+c_2\times {10}^6$ $\equiv c_0-c_1+c_2$. Pour $N=1234567$ : $c_0=567$, $c_1=234$, $c_2=1$, et $567-234+1=334$.
2. Reste de $1234567$ modulo $7$ :
   $334=7\times 47+5$, donc $1234567\equiv 334\equiv 5[7]$ : il n’est pas divisible par $7$.
3. Reste de $1234567$ modulo $13$ :
   $334=13\times 25+9$, donc $1234567\equiv 9[13]$.
4. Le même calcul vaut modulo $11$. Reste de $1234567$ modulo $11$ :
   $11$ divise aussi $1001$, donc $1234567\equiv 334[11]$, et $334=11\times 30+4$. Contrôle par la somme alternée des chiffres : $7-6+5-4+3-2+1=4$.

Soit $n$ un entier. On étudie les carrés modulo $8$.

1. Nombre de restes différents possibles pour $n^2$ modulo $8$ :
   Tableau de congruences modulo $8$ (par exemple $5^2=25=3\times 8+1$ et $6^2=36=4\times 8+4$) :

   $n$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$
   $n^2$	$0$	$1$	$4$	$1$	$0$	$1$	$4$	$1$

   Les restes possibles sont $0$, $1$ et $4$ : il y en a $3$.
2. Reste modulo $8$ du carré de tout entier impair :
   Dans le tableau, les colonnes impaires $1$, $3$, $5$ et $7$ donnent toutes $1$ : le carré d’un entier impair est congru à $1$ modulo $8$.
3. Justifier que $3517$ n’est pas le carré d’un entier. Reste de $3517$ modulo $8$ :
   Rédaction attendue. $1000\equiv 0[8]$, donc $3517\equiv 517[8]$, et $517=8\times 64+5$ : $3517\equiv 5[8]$. Or un carré est congru à $0$, $1$ ou $4$ modulo $8$, jamais à $5$ : $3517$ n’est pas le carré d’un entier.

Soit $n$ un entier. On veut démontrer que $n^3-n$ est divisible par $6$.

1. Reste de $n^3$ modulo $6$ lorsque $n\equiv 5[6]$ :
   $5\equiv -1[6]$, donc $n^3\equiv (-1{)}^3=-1\equiv 5[6]$.
2. Reste de $n^3$ modulo $6$ lorsque $n\equiv 2[6]$ :
   $n^3\equiv 2^3=8\equiv 2[6]$.
3. Démontrer que $n^3-n$ est divisible par $6$ pour tout entier $n$. Contrôle : ${11}^3-11=6\times$
   Rédaction attendue. Tableau de congruences modulo $6$ (par exemple $3^3=27=4\times 6+3$ et $4^3=64=10\times 6+4$) :

   $n$	$0$	$1$	$2$	$3$	$4$	$5$
   $n^3$	$0$	$1$	$2$	$3$	$4$	$5$

   Dans chaque colonne, $n^3\equiv n[6]$, donc $n^3-n\equiv 0[6]$ : $6$ divise $n^3-n$ pour tout entier $n$. Pour $n=11$ : $1331-11=1320=6\times 220$.

Soit $x$ et $y$ des entiers relatifs. On étudie les carrés modulo $7$.

1. Nombre de restes différents possibles pour $x^2$ modulo $7$ :
   Avec les représentants $-3$ à $3$ : $0^2=0$, $(\pm 1{)}^2=1$, $(\pm 2{)}^2=4$ et $(\pm 3{)}^2=9\equiv 2[7]$. Un carré est congru à $0$, $1$, $2$ ou $4$ modulo $7$ : $4$ restes.
2. Plus grand reste modulo $7$ qui n’est jamais celui d’un carré :
   Les restes $3$, $5$ et $6$ ne sont jamais atteints ; le plus grand est $6$.
3. Démontrer que l’équation $x^2-7y=5$ n’a aucune solution entière. Si l’on remplace $5$ par $2$, une solution est $x=3$ et $y$ =
   Rédaction attendue. Si $(x;y)$ était solution, on aurait $x^2=7y+5\equiv 5[7]$. Or un carré n’est jamais congru à $5$ modulo $7$ : l’équation n’a aucune solution. Avec $2$ au lieu de $5$, l’argument tombe ($2$ est le reste d’un carré) : $3^2-7y=2$ donne $7y=7$, soit $y=1$.

On s’intéresse à l’équation $x^3+y^3+z^3=1148$, d’inconnues $x$, $y$ et $z$ entières relatives.

1. Nombre de restes différents possibles pour $x^3$ modulo $9$ :
   Tableau de congruences modulo $9$ (par exemple $4^3=64=7\times 9+1$ et $5^3=125=13\times 9+8$) :

   $x$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$
   $x^3$	$0$	$1$	$8$	$0$	$1$	$8$	$0$	$1$	$8$

   Un cube est congru à $0$, $1$ ou $8$ modulo $9$, c’est-à-dire à $0$, $1$ ou $-1$.
2. Reste de $1148$ modulo $9$ :
   Somme des chiffres : $1+1+4+8=14$, et $14\equiv 5[9]$.
3. Démontrer que l’équation n’a aucune solution. Nombre de restes modulo $9$ (entre $0$ et $8$) qui ne sont jamais celui d’une somme de trois cubes :
   Rédaction attendue. Chaque cube est congru à $-1$, $0$ ou $1$ modulo $9$, donc une somme de trois cubes est congrue à un entier compris entre $-3$ et $3$, c’est-à-dire à l’un des restes $0$, $1$, $2$, $3$, $6$, $7$ ou $8$. Les restes $4$ et $5$ ne sont jamais atteints : il y en a $2$. Or $1148\equiv 5[9]$ : si l’équation avait une solution, on aurait $x^3+y^3+z^3\equiv 5[9]$, ce qui est impossible. L’équation n’a pas de solution entière.

Donner l’inverse demandé, compris entre $1$ et $n-1$.

1. Inverse de $3$ modulo $11$ :
   $3\times 4=12=11+1$, donc $3\times 4\equiv 1[11]$.
2. Inverse de $8$ modulo $15$ :
   $8\times 2=16=15+1$, donc $8\times 2\equiv 1[15]$.
3. Inverse de $5$ modulo $18$ :
   Parmi $19$, $37$, $55$, le premier multiple de $5$ est $55=5\times 11$, et $55=3\times 18+1$ : l’inverse est $11$.
4. Inverse de $10$ modulo $21$ :
   $10\times (-2)=-20=-21+1$, donc $10\times (-2)\equiv 1[21]$, et $-2\equiv 19[21]$. Contrôle : $10\times 19=190=9\times 21+1$.

Résoudre dans $\mathbb{Z}$. On donne la classe des solutions sous la forme $x\equiv c[n]$ avec $0⩽c<n$.

1. $7x\equiv 5[12]$ : $c$ =
   $7\times 7=49=4\times 12+1$ : $7$ est son propre inverse modulo $12$. En multipliant par $7$ : $x\equiv 35\equiv 11[12]$. Vérification : $7\times 11=77=6\times 12+5$.
2. $5x\equiv 7[18]$ : $c$ =
   L’inverse de $5$ modulo $18$ est $11$. Donc $x\equiv 11\times 7=77[18]$, et $77=4\times 18+5$ : $x\equiv 5[18]$. Vérification : $5\times 5=25=18+7$.
3. Les entiers $n$ tels que $4n+1$ soit divisible par $13$ vérifient $n\equiv c[13]$ : $c$ =
   $4n+1\equiv 0[13]$ équivaut à $4n\equiv -1\equiv 12[13]$. L’inverse de $4$ modulo $13$ est $10$ ($40=3\times 13+1$), donc $n\equiv 10\times 12=120[13]$, et $120=9\times 13+3$ : $n\equiv 3[13]$. Vérification : $4\times 3+1=13$.

Résoudre dans $\mathbb{Z}$ les équations suivantes.

1. $6x\equiv 9[15]$ : nombre de classes de solutions modulo $15$ :
   $3$ divise $6$, $9$ et $15$ : l’équation équivaut à $2x\equiv 3[5]$. L’inverse de $2$ modulo $5$ est $3$, d’où $x\equiv 9\equiv 4[5]$. Modulo $15$, cela fait trois classes : $x\equiv 4$, $9$ ou $14[15]$.
2. Plus petite solution strictement positive de $6x\equiv 9[15]$ :
   C’est $4$ : $6\times 4=24=15+9$.
3. Démontrer que $8x\equiv 5[20]$ n’a aucune solution. Nombre d’entiers $x$ compris entre $0$ et $19$ qui la vérifient :
   Rédaction attendue. Si $x$ était solution, il existerait un entier $k$ tel que $8x-5=20k$, soit $5=8x-20k=4(2x-5k)$ : $4$ diviserait $5$, ce qui est faux. L’équation n’a aucune solution : aucun entier entre $0$ et $19$ ne la vérifie.

On cherche les entiers $n$ tels que $n\equiv 2[5]$ et $n\equiv 3[7]$.

1. On écrit $n=5k+2$ avec $k$ entier. Démontrer que $n\equiv 3[7]$ équivaut à $5k\equiv 1[7]$, puis que $k\equiv c[7]$ avec $0⩽c<7$ : $c$ =
   Rédaction attendue. $n\equiv 3[7]$ s’écrit $5k+2\equiv 3[7]$, soit $5k\equiv 1[7]$ (on ajoute $-2$ aux deux membres). L’inverse de $5$ modulo $7$ est $3$, car $5\times 3=15=2\times 7+1$ ; en multipliant par $3$, $k\equiv 3[7]$. Réciproquement, si $k\equiv 3[7]$, alors $5k+2\equiv 17\equiv 3[7]$.
2. En déduire que $n\equiv c[35]$ avec $0⩽c<35$ : $c$ =
   $k=3+7j$ avec $j\in \mathbb{Z}$, donc $n=5(3+7j)+2=17+35j$ : $n\equiv 17[35]$. Contrôle : $17=3\times 5+2=2\times 7+3$.
3. Plus petit entier $n>100$ qui convient :
   Les solutions sont $17$, $52$, $87$, $122$… : $17+35\times 3=122$, et $122=24\times 5+2=17\times 7+3$.