Nombres premiers entre-eux et théorème de Bezout

I. Nombres premiers entre-eux

Le seul diviseur commun à $14$ et $45$ est $1$. En effet, aucun facteur premier intervenant dans la décomposition de $14$ n’intervient dans celle de $45$.

Cela conduit à poser la définition suivante :

Définition

Deux entiers non nuls sont dits premiers entre eux si leur PGCD est $1$.

Remarque

Tout nombre premier $p$ est premier avec tout nombre plus petit que lui, et il est également premier avec tout autre nombre qui n’est pas un de ses multiples.

Théorème

Soient $a$ et $b$ deux entiers naturels non nuls, $a \wedge b$ leur PGCD. Alors les deux entiers $a'$ et $b'$ tels que $a = (a \wedge b) \times a'$

et $b = (a \wedge b) \times b'$ sont premiers entre eux.

Démonstration

Soient deux entiers naturels non nuls $a$ et $b$. Le PGCD de deux nombres divise ces deux nombres donc il existe deux entiers $a'$ et $b'$ tels que :

$a = (a \wedge b) \times a'$ et $b = (a \wedge b) \times b'.$

On peut donc écrire :

$a \wedge b = ((a \wedge b) \times a') \wedge ((a \wedge b) \times b').$

Or $(kn \wedge km) = k \times (n \wedge m).$

Donc $a \wedge b = (a \wedge b) \times (a' \wedge b').$ Par suite $a' \wedge b' = 1.$

Remarque

Ce théorème permet, moyennant une division par le PGCD, de se ramener au cas où les nombres sont premiers entre eux.

Si on simplifie une fraction en divisant le numérateur et le dénominateur par leur PGCD, alors la fraction obtenue est irréductible.

$\dfrac{140}{150} = \dfrac{6 \times 24}{6 \times 25} = \dfrac{24}{25}.$

II. Caractérisation des nombres premiers entre-eux

Propriété : l'identité de Bezout

Soit $a$ et $b$ deux entiers naturels non nuls et $d$ leur PGCD, alors il existe deux entiers relatifs $n$ et $m$ tels que $d = na + mb$.

Démonstration (au programme)

Soient deux entiers naturels non nuls $a$ et $b$. Considérons l’ensemble $E$ formé des éléments du type $na + mb$, $n$ et $m$ étant des entiers relatifs.

On peut remarquer que $E \neq \emptyset$ puisque pour $n = 1$ et $m = 0$, on voit que $a \in E$.

De même, pour $n = 0$ et $m = 1$, on obtient que $b \in E$.

Soit $d$ le plus petit élément strictement positif de $E$, et soient $n_0$ et $m_0$ les nombres tels que $d = n_0 a + m_0 b$.

Soit $(na + mb)$ un élément quelconque de $E$. Effectuons la division euclidienne de $na + mb$ par $d$.

$na+mb=qd+r$

d’où $r = na + mb - q (n_0 a + m_0 b) = (n - q n_0) a + (m - q m_0) b.$

Par suite $r$ est un élément de $E$ tel que $0 \leq r \lt d$.

Puisque $d$ est le plus petit élément strictement positif de $E$, on a $r = 0$.

Par conséquent, tout élément de $E$ est un multiple de $d$.

En particulier $a$ et $b$ sont des multiples de $d$.

Le nombre $d$ étant un diviseur de $a$ et de $b$, $d$ divise donc $a \wedge b$.

Réciproquement, $a \wedge b$ divisant $a$ et $b$, $a \wedge b$ divise aussi $n_0 a + m_0 b$,

donc $a \wedge b$ divise $d$.

On en déduit que $d = a \wedge b$.

En particulier, $a$ et $b$ sont premiers entre eux si et seulement si il existe deux entiers relatifs tels que $n_0 a + m_0 b = 1$.

Réciproquement, s’il existe $n_0$ et $m_0$ tel que $n_0 a + m_0 b = 1$ et si $d$ divise $a$ et $b$, alors $d$ divise $n_0 a + m_0 b$, donc $d$ divise $1$.

Le théorème de BEZOUT

Soient $a$ et $b$ deux entiers non nuls.

Les nombres $a$ et $b$ sont premiers entre eux si et seulement si il existe deux entiers relatifs $n$ et $m$ tels que : $na+mb=1$.

Exemple : La relation $7 \times 4 + (-9) \times 3 = 1$ montre que $4$ et $3$ sont premiers entre eux.

Remarque

La relation de Bézout n’est pas unique. On a aussi $1 \times 4 + (-1) \times 3 = 1$.

III. Inverse modulo $n$

Propriété :

Un entier $a$ admet un inverse modulo $n$, si $a$ et $n$ sont premiers entre eux.

IV. Un exemple de recherche d'inverse modulo n

Énoncé :

Soit $a = 7$ et $n = 26$. Nous voulons vérifier si $7$ admet un inverse modulo $26$.

Solution :

1. Vérification de la condition : $a$ et $n$ premiers entre eux

Un entier $a$ admet un inverse modulo $n$ si et seulement si $a$ et $n$ sont premiers entre eux, c'est-à-dire si leur PGCD est $1$.

Calculons le PGCD de $7$ et $26$ avec l'algorithme d'Euclide :

$26 = 3 \times 7 + 5$
$7 = 1 \times 5 + 2$
$5 = 2 \times 2 + 1$
$2 = 2 \times 1 + 0$

Le dernier reste non nul est $1$, donc $\gcd(7,26) = 1$. Ainsi, $7$ et $26$ sont premiers entre eux, donc $7$ admet un inverse modulo $26$.

2. Trouver l’inverse de $7$ modulo $26$

Nous devons trouver un entier $x$ tel que :

$7x \equiv 1 \pmod{26}$

Utilisons l’identité de Bézout, qui nous donne une combinaison linéaire de $7$ et $26$ donnant $1$.

Reprenons les étapes de l’algorithme d’Euclide en remontant :

$1 = 5 - 2 \times 2$

Or $2 = 7 - 1 \times 5$, donc

$1 = 5 - 2 \times (7 - 1 \times 5)$
$1 = 5 - 2 \times 7 + 2 \times 5$
$1 = 3 \times 5 - 2 \times 7$

Or $5 = 26 - 3 \times 7$, donc

$1 = 3 \times (26 - 3 \times 7) - 2 \times 7$
$1 = 3 \times 26 - 9 \times 7 - 2 \times 7$
$1 = 3 \times 26 - 11 \times 7$

Donc, on obtient :
$1 = -11 \times 7 + 3 \times 26$

En prenant modulo $26$, on voit que $-11 \equiv 15 \pmod{26}$, donc l’inverse de $7$ modulo $26$ est $15$.

3. Vérification

Calculons $7 \times 15 \mod 26$ :

$7 \times 15 = 105$
$105 \div 26 = 4$ reste $1$

Donc :
$7 \times 15 \equiv 1 \pmod{26}$

Conclusion : L’inverse de $7$ modulo $26$ est bien $15$.