Examen blanc — Arithmétique

1. Comme $7\times 8=56=55+1=5\times 11+1$, on a $7\times 8\equiv 1[11]$ : l'inverse de $7$ modulo $11$ est $8$.

En multipliant $7x\equiv 5[11]$ par $8$ : $8\times 7x\equiv 8\times 5[11]$, soit $x\equiv 40[11]$. Or $40=3\times 11+7$, donc $x\equiv 7[11]$.

L'ensemble des solutions est $\{7+11k;k\in \mathbb{Z}\}$.

2. Petit théorème de Fermat : si $p$ est premier et si $a$ n'est pas divisible par $p$, alors $a^{p-1}\equiv 1[p]$. Ici $p=11$ est premier et $11\nmid 7$, donc $7^{10}\equiv 1[11]$.

3. On écrit $2024=10\times 202+4$. Ainsi $7^{2024}=(7^{10}{)}^{202}\times 7^4\equiv 1^{202}\times 7^4\equiv 7^4[11]$.

Or $7^2=49\equiv 5[11]$ (car $49=44+5$), donc $7^4=(7^2{)}^2\equiv 5^2=25\equiv 3[11]$. Le reste cherché est $3$.

4. $N=7^{2024}+8\equiv 3+8=11\equiv 0[11]$, donc $11\mid N$.

5. $p$ est premier et $p\ne 7$, donc $p\nmid 7$ ($7$ étant premier, ses seuls diviseurs sont $1$ et $7$). Le petit théorème de Fermat donne directement $7^{p-1}\equiv 1[p]$, c'est-à-dire $p\mid 7^{p-1}-1$.

1. Algorithme d'Euclide : $18=1\times 13+5$, puis $13=2\times 5+3$, puis $5=1\times 3+2$, puis $3=1\times 2+1$, enfin $2=2\times 1+0$. Le dernier reste non nul est $1$, donc $\mathrm{pgcd}(13,18)=1$ : $13$ et $18$ sont premiers entre eux.

2. En remontant les égalités : $1=3-1\times 2=3-(5-3)=2\times 3-5=2\times (13-2\times 5)-5=2\times 13-5\times 5$. Or $5=18-13$, donc $1=2\times 13-5\times (18-13)=7\times 13-5\times 18$.

Ainsi $13\times 7+18\times (-5)=1$ : on peut prendre $(u,v)=(7,-5)$. (Vérification : $91-90=1$.)

3. De $13\times 7\equiv 1[18]$, l'inverse de $13$ modulo $18$ est $7$. En multipliant $13x\equiv 5[18]$ par $7$ : $x\equiv 35[18]$. Or $35=18+17$, donc $x\equiv 17[18]$.

L'ensemble des solutions est $\{17+18k;k\in \mathbb{Z}\}$. (Vérification : $13\times 17=221=12\times 18+5$.)

4. De $x\equiv 2[5]$, il existe $k\in \mathbb{Z}$ tel que $x=2+5k$. En reportant dans $x\equiv 3[7]$ : $2+5k\equiv 3[7]$, soit $5k\equiv 1[7]$. Comme $5\times 3=15\equiv 1[7]$, l'inverse de $5$ modulo $7$ est $3$, d'où $k\equiv 3[7]$, c'est-à-dire $k=3+7m$.

Alors $x=2+5(3+7m)=17+35m$, donc $x\equiv 17[35]$.

Rôle de Gauss : $5$ et $7$ sont premiers entre eux ; puisque $5\mid (x-17)$ et $7\mid (x-17)$, le théorème de Gauss assure que $5\times 7=35$ divise $x-17$. Le système équivaut donc à l'unique congruence $x\equiv 17[35]$. (Vérification : $17=3\times 5+2$ et $17=2\times 7+3$.)