Nombres premiers entre eux

Soient $a$ et $b$ deux entiers relatifs non nuls.
On dit que $a$ et $b$ sont premiers entre eux lorsque leurs seuls diviseurs communs sont $1$ et $-1$. Autrement dit, $a$ et $b$ sont premiers entre eux lorsque $\mathrm{PGCD}(a;b)=1.$

Deux nombres premiers distincts sont premiers entre eux.

Soient $d^{\prime }=\mathrm{PGCD}\left(a^{\prime };b^{\prime }\right)$ et $k_1$ et $k_2$ les entiers tels que $a^{\prime }=d^{\prime }{k}_1$ et $b^{\prime }=d^{\prime }{k}_2$.
On doit montrer que $d=1$.
En effet, $a=d{d}^{\prime }{k}_1$ et $b=d{d}^{\prime }{k}_2$ donc $d{d}^{\prime }$ est un diviseur commun à $a$ et $b$. Comme $d=\mathrm{PGCD}(a;b)$, on a nécessairement $d{d}^{\prime }⩽d$ donc, puisque $d>0,d^{\prime }=1$.
Réciproquement, $\mathrm{PGCD}(a;b)$ $=\mathrm{PGCD}\left(d{a}^{\prime };d{b}^{\prime }\right)$ $=d\mathrm{PGCD}\left(a^{\prime };b^{\prime }\right)$ $=d$ car $a^{\prime }$ et $b^{\prime }$ sont premiers entre eux.

$36=12\times 3$ et $60=12\times 5$. Puisque $3$ et $5$ sont premiers entre eux, alors $\mathrm{PGCD}(60;36)=12$.

Déterminer l'ensemble des couples $(a;b)\in {\mathbb{N}}^2$ tels que $\{\begin{array}{l}ab=300\\ \mathrm{PGCD}(a;b)=5\end{array}$.

• Introduire les entiers $a^{\prime }$ et $b^{\prime }$ premiers entre eux tels que $\{\begin{array}{l}a=5a^{\prime }\\ b=5b^{\prime }\end{array}$.
• Écrire une équation vérifiée par le produit $a^{\prime }{b}^{\prime }$ et lister les couples d'entiers premiers entre eux vérifiant cette équation.
• En déduire les valeurs possibles pour $a$ et $b$.

Puisque $\mathrm{PGCD}(a;b)=5$, il existe deux entiers $a^{\prime }$ et $b^{\prime }$ premiers entre eux tels que $\{\begin{array}{l}a=5a^{\prime }\\ b=5b^{\prime }\end{array}$.
On a alors $ab=25a^{\prime }{b}^{\prime }$ donc $25a^{\prime }{b}^{\prime }=300$ et ainsi $a^{\prime }{b}^{\prime }=12$.
Or $12=1\times 12=2\times 6=3\times 4$.
Comme $a^{\prime }$ et $b^{\prime }$ doivent être premiers entre eux, les couples possibles sont $(1;12),(12;1),(3;4)$ et $(4;3)$ ce qui donne pour $(a;b)$ les couples $(5;60),(60;5),(15;20)$ et $(20;15)$.
Réciproquement, chacun de ces couples est solution du système.

Exercices

33

et

34

p. 132.

Tout sous-ensemble non vide de $\mathbb{N}$ admet un plus petit élément.

Le théorème de Bézout donne l'existence d'entiers $u$ et $v$ mais ne donne pas de méthode pour en déterminer.

Soit $(a;b)$ un couple d'entiers relatifs non nuls.
Alors $a$ et $b$ sont premiers entre eux si, et seulement si, il existe deux entiers relatifs $u$ et $v$ tels que $au+bv=1$.

Il n'y a pas unicité des entiers $u$ et $v$ tels que $au+bv=1$.

• On commence par justifier qu'il existe bien un couple d'entiers $(u;v)$ tel que $29u+12v=1$.
• On applique l'algorithme d'Euclide pour connaître tous les restes successifs jusqu'au reste égal à $1$.
• On utilise les divisions euclidiennes obtenues en « remontant » l'algorithme d'Euclide pour déterminer $u$ et $v$.

Puisque $29$ est un nombre premier, $29$ et $12$ sont premiers entre eux.
Il existe donc deux entiers $u$ et $v$ tels que $29u+12v=1$.
D'après l'algorithme d'Euclide, on a les égalités suivantes :
$29=12\times 2+5\left({\mathrm{E}}_1\right);12=5\times 2+2\left({\mathrm{E}}_2\right)$ et $5=2\times 2+1\left({\mathrm{E}}_3\right)$.
D'après $\left({\mathrm{E}}_3\right)$, on a $1=5-2\times 2$ et, d'après $\left({\mathrm{E}}_2\right)$, on a $2=12-5\times 2$.
Donc, $1=5-2\times (12-5\times 2)=5\times 5-2\times 12$.
D'après $\left({\mathrm{E}}_1\right)$, on a $5=29-2\times 12$ d'où $1=5\times (29-2\times 12)-2\times 12$ soit finalement $1=29\times 5+12\times (-12)$.
On a donc trouvé $u=5$ et $v=-12.$

Exercices

43

et

44

p. 133.

Pour tout couple $(a;b)\in {\mathbb{Z}}^{\ast 2}$, il existe $(u;v)\in {\mathbb{Z}}^2$ tel que $au+bv=\mathrm{PGCD}(a;b)$.

Le couple $(u;v)$ n'est pas unique.

Soient $a$ et $b$ deux entiers relatifs non nuls et on pose $d=\mathrm{PGCD}(a;b)$.
Il existe deux entiers $a^{\prime }$ et $b^{\prime }$ tels que $a=a^{\prime }d$ et $b=b^{\prime }d$ et tels que $\mathrm{PGCD}\left(a^{\prime };b^{\prime }\right)=1$.
D'après le théorème de Bézout, il existe $(u;v)\in {\mathbb{Z}}^2$ tel que $a^{\prime }u+b^{\prime }v=1.$
On a alors $au+bv=a^{\prime }du+b^{\prime }dv=d\left(a^{\prime }u+b^{\prime }v\right)=\mathrm{PGCD}(a;b)$.

L'identité de Bézout est en réalité vraie pour $(a;b)\in {\mathbb{Z}}^2$.

Le $\text{PGCD}$ de $84$ et $18$ est $6$ donc il existe des entiers $u$ et $v$ tels que $84u+18v=6$. Pour les déterminer, on peut se ramener à l'équation diophantienne $14u+3v=1$ dont une solution est $(-1;5)$. On vérifie : $-84+18\times 5=-84+90=6$.

On appelle équation diophantienne une équation à coefficients entiers, dont on cherche une solution entière (ou rationnelle).

Soient $a$, $b$ et $c$ trois entiers tels que $a$ et $b$ ne sont pas simultanément nuls.
L'équation $ax+by=c$ admet des couples d'entiers $(x;y)$ solutions si, et seulement si, le nombre $c$ est un multiple de $\mathrm{PGCD}(a;b).$

Voir exercice

88

p. 136.

Il existe $a\in \mathbb{Z}$ tel que $30a\equiv 1[23]$ si, et seulement si, il existe $(a;b)\in {\mathbb{Z}}^2$ tel que $30a+23b=1$.

• Vérifier que cette équation admet une solution en écrivant l'algorithme d'Euclide pour déterminer le $\text{PGCD}$ de $30$ et $23$.
• Remonter les lignes de l'algorithme d'Euclide en partant de l'avant-dernière (reste égal à $1$) pour écrire $1$ comme combinaison linéaire des deux derniers restes, puis des deux restes précédents, jusqu'à obtenir une combinaison linéaire de $30$ et $23$.

$30$ et $23$ sont premiers entre eux donc, d'après le théorème de Bézout, il existe un couple d'entiers relatifs $(a;b)$ tel que $30a+23b=1$ donc il existe un entier $a$ tel que $30a\equiv 1[23]$.
L'algorithme d'Euclide et sa remontée permettent d'obtenir $1=30\times 10-23\times 13$.
On en déduit que $(10;-13)$ est un couple solution et donc que $10$ est un inverse de $30$ modulo $23$ :
$30\times 10\equiv 1[23]$

Exercices

48

et

49

p. 133.