Théorèmes fondamentaux de l'arithmétique

Théorème de Bézout et applications

Proposition Identité de Bézout

Soient $a$ et $b$ deux entiers relatifs non tous deux nuls et $d=PGCD(a,b)$.
Alors, il existe un couple d'entiers relatifs $(u,v)$ tel que$$au+bv=d.$$

Preuve

Considérons l'ensemble $S$ des combinaisons linéaires strictement positives de $a$ et $b$ :$$S=\{am+bn \mid m,n\in\mathbb{Z}\ \text{et}\ am+bn>0\}.$$

$S$ est non vide : comme $a$ et $b$ ne sont pas tous deux nuls, l'un au moins des entiers $a,-a,b,-b$ est strictement positif et appartient à $S$.
$S$ étant une partie non vide de $\mathbb{N}^*$, elle admet un plus petit élément $d_0$. Il existe donc des entiers relatifs $u$ et $v$ tels que $d_0=au+bv$.
Montrons que $d_0$ divise $a$. Effectuons la division euclidienne de $a$ par $d_0$ : $$ a=d_0q+r \quad \text{avec } 0\le r0\), alors $r\in S$, mais \(r
Enfin, $d_0$ est bien le PGCD : si $d'$ est un diviseur commun de $a$ et $b$, alors $d'$ divise toute combinaison linéaire de $a$ et $b$, en particulier $d_0=au+bv$. Donc $d'\le d_0$, et ainsi $d_0=PGCD(a,b)$.

Proposition Théorème de Bézout

Soient $a$ et $b$ deux entiers relatifs non tous deux nuls.
$PGCD(a,b)=1$ si et seulement s'il existe un couple d'entiers relatifs $(u,v)$ tel que $au+bv=1$.

Preuve

$(\Rightarrow)$ Si $PGCD(a,b)=1$, l'existence de $(u,v)$ découle de la proposition précédente.
$(\Leftarrow)$ Supposons qu'il existe des entiers relatifs $u,v$ tels que $au+bv=1$. Soit $d=PGCD(a,b)$. Comme $d\mid a$ et $d\mid b$, on a $d\mid (au+bv)$, donc $d\mid 1$. Comme $d$ est un entier positif, on obtient $d=1$.

Méthode Trouver des coefficients de Bézout

Soient $a$ et $b$ deux entiers relatifs avec $b\neq 0$.

Appliquer l'algorithme d'Euclide à $(|a|,|b|)$ pour obtenir $PGCD(a,b)$.
Remonter les égalités pour écrire $PGCD(a,b)$ comme combinaison linéaire de $a$ et de $b$.

Exemple

Déterminer des entiers relatifs $u$ et $v$ tels que $47u+39v=1$.

Correction

On commence par appliquer l'algorithme d'Euclide pour trouver le PGCD :

$47 = 39 \times 1 + 8\quad \textcircled{1}$
$39 = 8 \times 4 + 7 \quad \textcircled{2}$
$8 = 7 \times 1 + 1 \quad \textcircled{3}$

On exprime chaque reste à partir des égalités précédentes :

D'après $\textcircled{3}: 1 = 8 - 7 \times 1$
D'après $\textcircled{2}: 7 = 39 - 8 \times 4$
D'après $\textcircled{1}: 8 = 47 - 39 \times 1$

Enfin, on « remonte » les calculs pour exprimer $1$ en fonction de $47$ et $39$ :$$\begin{aligned}1 &= 8 - (39 - 8 \times 4) \times 1 && (\text{en substituant } 7 \text{ d'après } \textcircled{2}) \\ 1 &= 8 \times 5 - 39 && (\text{en simplifiant}) \\ 1 &= (47 - 39 \times 1) \times 5 - 39 && (\text{en substituant } 8 \text{ d'après } \textcircled{1}) \\ 1 &= 47 \times 5 - 39 \times 5 - 39 && (\text{en développant}) \\ 1 &= 47 \times 5 + 39 \times (-6) && (\text{forme finale})\end{aligned}$$Ainsi, le couple $(u;v) = (5;-6)$ est une solution.

Théorème de Gauss

Theorem Théorème de Gauss

Soient $a,b,c$ trois entiers relatifs non nuls.
Si $a$ divise le produit $bc$ et si $a$ et $b$ sont premiers entre eux, alors $a$ divise $c$.

Preuve

Supposons que $a \mid bc$ et que $PGCD(a,b)=1$.

Puisque $a \mid bc$, il existe un entier relatif $k$ tel que $bc=ka$.
Puisque $PGCD(a,b)=1$, d'après le théorème de Bézout, il existe des entiers relatifs $u$ et $v$ tels que $$ au+bv=1. $$
En multipliant par $c$, on obtient $$ c(au+bv)=c \implies acu+bcv=c. $$
On réécrit $a(cu)+(bc)v=c$ et on remplace $bc$ par $ka$ : $$ a(cu)+(ka)v=c \implies a(cu+kv)=c. $$
Comme $(cu+kv)$ est un entier relatif, on en déduit que $a\mid c$.

Proposition Corollaires du théorème de Gauss

Si un entier est divisible par des entiers $a$ et $b$ premiers entre eux, alors il est divisible par leur produit $ab$.
Si un nombre premier divise un produit $ab$, alors il divise au moins l'un des facteurs $a$ ou $b$.
Si un nombre premier $p$ divise un produit de nombres premiers, alors $p$ est égal à l'un d'entre eux.
Un nombre premier $p$ est premier avec $a$ et $b$ si et seulement si $p$ est premier avec leur produit $ab$.

Theorem Petit théorème de Fermat

Soit $p$ un nombre premier et soit $a$ un entier naturel non multiple de $p$. Alors :$$a^{p-1} \equiv 1 \pmod{p}.$$Pour tout entier naturel $a$, on a :$$a^p \equiv a \pmod{p}.$$

Preuve

La démonstration s'effectue en deux étapes.

Cas où $a$ n'est pas divisible par $p$ :
Considérons les $p-1$ produits $a,2a,\dots,(p-1)a$ modulo $p$ :$$S=\{a,2a,3a,\dots,(p-1)a\}.$$
- Restes distincts : Soient $i$ et $j$ deux entiers distincts de $\{1,\dots,p-1\}$. Si $ia \equiv ja \pmod{p}$, alors $p\mid a(i-j)$.
  Comme $p$ est premier et $p\nmid a$, d'après le théorème de Gauss on a $p\mid (i-j)$. Or $|i-j| Ainsi, les restes de \(a,2a,\dots,(p-1)a$ modulo $p$ sont tous distincts.
- Restes non nuls : Pour tout $k\in\{1,\dots,p-1\}$, on a $p\nmid k$ et $p\nmid a$, donc $p\nmid ka$. Ainsi, aucun de ces restes n'est $0$.
- Conclusion sur l'ensemble : Les restes de $S$ modulo $p$ sont donc exactement $\{1,2,\dots,p-1\}$ dans un certain ordre.
En multipliant, on obtient$$(1a)(2a)\cdots((p-1)a)\equiv 1\cdot 2\cdots (p-1)\pmod{p},$$c'est-à-dire$$a^{p-1}(p-1)! \equiv (p-1)! \pmod{p}.$$Comme $p$ est premier, il ne divise aucun des facteurs $1,2,\dots,p-1$, donc $\gcd\bigl((p-1)!,p\bigr)=1$; on peut simplifier par $(p-1)!$ modulo $p$, et on obtient$$a^{p-1}\equiv 1 \pmod{p}.$$
Cas général ($a^p \equiv a \pmod{p}$) :
- Si $p\nmid a$, on multiplie $a^{p-1}\equiv 1 \pmod{p}$ par $a$ et on obtient $a^p\equiv a \pmod{p}$.
- Si $p\mid a$, alors $a\equiv 0 \pmod{p}$ et $a^p\equiv 0 \pmod{p}$, donc $a^p\equiv a \pmod{p}$.