Congruences et théorème de Fermat-Euler

Calculer $17 \bmod 5$.

$17=5\times3+2$. Donc $17\equiv2\pmod5$.

Vrai ou faux : $\mathbb{Z}/7\mathbb{Z}$ est un corps.

Vrai. $7$ est premier, donc $\mathbb{Z}/7\mathbb{Z}$ est un corps (tout élément non nul est inversible).

Calculer $\varphi(12)$.

$12=4\times3=2^2\times3$. $\varphi(12)=\varphi(4)\varphi(3)=2\times2=4$. Les entiers $\leq12$ premiers à $12$ : $\{1,5,7,11\}$.

Vrai ou faux : $2^{100}\equiv1\pmod5$ (petit théorème de Fermat).

$p=5$, $5\nmid2$. Par Fermat : $2^4\equiv1\pmod5$. Comme $100=4\times25$, $2^{100}=(2^4)^{25}\equiv1^{25}=1\pmod5$ ✓.

Calculer $3^{\varphi(10)}\pmod{10}$ ($\varphi(10)=4$).

$\text{pgcd}(3,10)=1$ et $\varphi(10)=4$. Par le théorème d'Euler : $3^4\equiv1\pmod{10}$. Vérif : $3^4=81=80+1\equiv1$ ✓.

Résoudre $x\equiv3\pmod5$ et $x\equiv2\pmod7$ (CRT).

CRT : $N=5\times7=35$.
$M_1=35/5=7$, $M_2=35/7=5$.

$7y_1\equiv1\pmod5$ : $2y_1\equiv1\pmod5$, $y_1=3$ ($2\times3=6\equiv1$).
$5y_2\equiv1\pmod7$ : $5y_2\equiv1\pmod7$, $y_2=3$ ($5\times3=15\equiv1$).

$x_0=3\times7\times3+2\times5\times3=63+30=93\equiv93-2\times35=23\pmod{35}$.

Vérif : $23=4\times5+3\equiv3\pmod5$ ✓, $23=3\times7+2\equiv2\pmod7$ ✓.

Calculer $2^{1000}\pmod{13}$ (Fermat, $p=13$).

$p=13$, $13\nmid2$. Fermat : $2^{12}\equiv1\pmod{13}$.

$1000=12\times83+4$.

$2^{1000}=2^{12\times83+4}=(2^{12})^{83}\times2^4\equiv1^{83}\times16\equiv16\pmod{13}$.

$16=13+3\equiv3\pmod{13}$.

Vrai ou faux : $\varphi$ est multiplicatif, i.e., $\varphi(mn)=\varphi(m)\varphi(n)$ si $\text{pgcd}(m,n)=1$.

Vrai. La multiplicativité de $\varphi$ découle du CRT : $(\mathbb{Z}/mn)^\times\cong(\mathbb{Z}/m)^\times\times(\mathbb{Z}/n)^\times$ si $\text{pgcd}(m,n)=1$.

Démontrer le petit théorème de Fermat en utilisant le binôme.

Preuve par récurrence sur $a\geq0$ :

Base : $0^p=0\equiv0\pmod p$ ✓.

Hérédité : Supposons $a^p\equiv a\pmod p$. Alors :
$(a+1)^p=\sum_{k=0}^p\binom{p}{k}a^k$.

Pour $0<k<p$ : $p\mid\binom{p}{k}$ (car $p$ premier divise $p!$ mais pas $k!(p-k)!$ pour $0<k<p$).

Donc $(a+1)^p\equiv a^p+1\equiv a+1\pmod p$. $\square$

Vrai ou faux : Si $n$ est composé, alors $a^{n-1}\equiv1\pmod n$ pour tout $a$ avec $\text{pgcd}(a,n)=1$.

Faux en général (mais vrai pour les nombres de Carmichael, exception rare). En général pour $n$ composé il existe des $a$ premiers à $n$ avec $a^{n-1}\not\equiv1\pmod n$, ce qui est la base du test de primalité de Fermat.

Calculer $\varphi(p^k)$ pour $p$ premier et $k\geq1$.

Les entiers entre $1$ et $p^k$ non premiers à $p^k$ sont exactement les multiples de $p$ : $p, 2p, \ldots, p^{k-1}\cdot p$. Il y en a $p^{k-1}$.

$\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)$. $\square$

Vrai ou faux : L'ordre de $a$ dans $(\mathbb{Z}/p\mathbb{Z})^\times$ divise $p-1$.

Vrai. $(\mathbb{Z}/p\mathbb{Z})^\times$ est un groupe d'ordre $p-1$. Par le théorème de Lagrange, l'ordre de tout élément divise l'ordre du groupe.

Montrer que $n\mid\varphi(a^n-1)$ pour $\text{pgcd}(a,p)=1$.

Posons $N=a^n-1$. Alors $a^n\equiv1\pmod N$.

L'ordre de $a$ dans $(\mathbb{Z}/N\mathbb{Z})^\times$ divise $n$. D'autre part $a^k\equiv1\pmod N$ implique $N\mid a^k-1$. Pour $k<n$, $a^k-1<a^n-1=N$, donc $a^k\not\equiv1\pmod N$. L'ordre est exactement $n$.

Par Lagrange : $n\mid|(\mathbb{Z}/N\mathbb{Z})^\times|=\varphi(N)=\varphi(a^n-1)$. $\square$

Trouver toutes les solutions de $x^2\equiv1\pmod{15}$.

CRT : $\mathbb{Z}/15\cong\mathbb{Z}/3\times\mathbb{Z}/5$.

$x^2\equiv1\pmod3$ : $x\equiv\pm1\pmod3$, i.e., $x\equiv1$ ou $x\equiv2$.
$x^2\equiv1\pmod5$ : $x\equiv\pm1\pmod5$, i.e., $x\equiv1$ ou $x\equiv4$.

4 solutions mod 15 :
- $(1,1)\to x\equiv1\pmod{15}$
- $(1,4)\to x\equiv4$ (vérif: $4^2=16\equiv1$ ✓)
- $(2,1)\to x\equiv11$ ($11^2=121=8\times15+1\equiv1$ ✓)
- $(2,4)\to x\equiv14\equiv-1$ ($14^2=196=13\times15+1\equiv1$ ✓)

Vrai ou faux : Le groupe $(\mathbb{Z}/p\mathbb{Z})^\times$ est cyclique (il existe un générateur).

Vrai. $(\mathbb{Z}/p\mathbb{Z})^\times$ est un groupe abélien d'ordre $p-1$. Tout groupe abélien fini est produit de groupes cycliques. De plus, pour $p$ premier, ce groupe est cyclique (il admet une racine primitive modulo $p$). C'est un résultat classique non trivial.