Terminale – Cours – PGCD et applications

PGCD et applications

I PGCD

On considère deux entiers relatifs $a$ et $b$. On note $\Delta(a;b)$ l’ensemble des diviseurs communs à $a$ et $b$.

Exemples :

  • $\Delta(12;18)=\lbrace -6;-3;-2;-1;1;2;3;6\rbrace$
  • $\Delta(-4;6)=\lbrace -2;-1;1;2\rbrace$

Remarque : $\Delta(a;b)=\Delta(b;a)$.

Propriété 1 : On considère deux entiers relatifs $a$ et $b$.
$\Delta(a;b)$ est un ensemble non vide.
Preuve Propriété 1

Tout entier relatif est divisible par $1$ et $-1$.
Donc $\Delta(a;b)$ contient au moins les nombres $1$ et $-1$.
$\quad$

[collapse]

$\quad$

Propriété 2 : On considère deux entiers relatifs $a$ et $b$ tels que $(a;b)\neq (0;0)$.
$\Delta(a;b)$ possède un nombre fini d’éléments.
Preuve Propriété 2

Un entier relatif non nul possède un nombre fini de diviseurs.
Supposons que $a$ soit non nul (s’il est nul alors $b$ ne l’est pas). L’ensemble des diviseurs de $a$ contient donc $\Delta(a;b)$.
Par conséquent $\Delta(a;b)$ possède un nombre fini d’éléments.

[collapse]

$\quad$

Remarque : $\Delta(a;b)$ possède alors un plus grand élément.

Propriété 3 : On considère deux entiers relatifs $a$ et $b$ tels que $b\neq 0$ et $a=bq+r$ où $q$ et $r$ sont des entiers relatifs.
$\Delta(a;b)=\Delta(b;r)$.
Preuve Propriété 3

On va montrer cette propriété par double inclusion, c’est-à-dire que chaque ensemble contient l’autre

  • On considère un élément de $\Delta(a;b)$.
    $d$ est un diviseur commun à $a$ et $b$ il divise alors toutes leurs combinaisons linéaires en particulier $a-bq$, c’est-à-dire $r$.
    Donc $d$ appartient à $\Delta(b;r)$.
  • On considère un élément de $\Delta(b;r)$.
    $d$ est un diviseur commun à $b$ et $r$ il divise alors toutes leurs combinaisons linéaires en particulier $bq+r$, c’est-à-dire $a$.
    Donc $d$ appartient à $\Delta(a;b)$.

Ainsi $\Delta(a;b)=\Delta(b;r)$.
$\quad$

[collapse]

$\quad$

Remarque : Cette propriété est en particulier vraie quand on écrit la division euclidienne de $a$ par $b$, c’est-à-dire quand $0\pp r<b$.

Définition 1 : On considère deux entiers relatifs $a$ et $b$ tels que $(a;b)\neq (0;0)$.
On appelle PGCD de $a$ et $b$ le plus grand élément de $\Delta(a;b)$. Il s’agit donc du plus grand diviseur commun à $a$ et $b$.
On le note $\PGCD(a;b)$.

Remarque : Par convention $\PGCD(0;0)=0$.

Exemple : On a $\Delta(12;18)=\lbrace -6;-3;-2;-1;1;2;3;6\rbrace$ donc $\PGCD(12;18)=6$.

Propriété 4 :On considère deux entiers relatifs $a$ et $b$ tels que $(a;b)\neq (0;0)$.

  1. $\PGCD(a;b)=\PGCD(b;a)$
  2. $\PGCD(a;b)\pg 1$
  3. $\PGCD(1;a)=1$
  4. $\PGCD(a;a)=|a|$
  5. $\PGCD(a;0)=|a|$
  6. $\PGCD(a;b)=\PGCD(-a;b)$ $=\PGCD(a;-b)=\PGCD(-a;-b)$ $=\PGCD\left(|a|;|b|\right)$
  7. Si $b$ divise $a$ alors $\PGCD(a;b)=|b|$
  8. $\PGCD(a;b)=\PGCD(a-b;b)$

Preuve Propriété 4

  1. On a $\Delta(a;b)=\Delta(b;a)$.
    Par conséquent leur plus grand élément est le même et par conséquent $\PGCD(a;b)=\PGCD(b;a)$.
    $\quad$
  2. $1$ appartient à $\Delta(a;b)$ donc son plus grand élément est supérieur ou égal à $1$.
    $\PGCD(a;b)\pg 1$
    $\quad$
  3. On a $\PGCD(1;a)\pg 1$.
    Le plus grand diviseur de $1$ est $1$. Donc $\PGCD(1;a)=1$.
    $\quad$
  4. Le plus grand diviseur de $a$ est $|a|$ donc le plus grand diviseur commun à $a$ et $a$ est $|a|$.
    $\quad$
  5. $0$ est divisible par tous les entiers relatifs non nul en particulier par $|a|$.
    $|a|$ est le plus grand diviseur de $a$ donc $\PGCD(a;0)=|a|$.
    $\quad$
  6. Un nombre et son opposé ont les mêmes diviseurs.
    Donc $\Delta(a;b)=\Delta(-a;b)=\Delta(a;-b)=\Delta(-a;-b)=\Delta(|a|;|b|)$.
    Ainsi :
    $\PGCD(a;b)=\PGCD(-a;b)$ $=\PGCD(a;-b)=\PGCD(-a;-b)$ $=\PGCD\left(|a|;|b|\right)$
    $\quad$
  7. Si $b$ divise $a$ alors $|b|$ est un diviseur commun à $a$ et $b$. $|b|$ est également le plus grand diviseur de $b$.
    Donc $\PGCD(a;b)=|b|$.
    $\quad$
  8. D’après la propriété 3. on a $\Delta(a;b)=\Delta(a-b;b)$
    Par conséquent $\PGCD(a;b)=\PGCD(a-b;b)$.
    $\quad$

[collapse]

$\quad$

Exemples : 

  • $\PGCD(45;12)=\PGCD(12;45)$
  • $\PGCD(-45;12)=\PGCD(12;-45)=\PGCD(12;45)=\PGCD(-12;-45)$
  • $\PGCD(56;7)=7$ car $7$ divise $56$
  • On a :
    $\begin{align*} \PGCD(45;12)&=\PGCD(33;12) \quad \text{car }45-12=33 \\
    &=\PGCD(21;12) \quad \text{car }33-12=21\\
    &=\PGCD(9;12) \quad \text{car }21-12=9\\
    &=\PGCD(9;3)\quad \text{car }12-9=3\\
    &=3\quad \text{car $3$ divise $9$}\end{align*}$

$\quad$

$\quad$

II Algorithme d’Euclide

Propriété 5 : On considère un entiers relatifs $a$ et $b$ tels que $b>0$ et $a=bq+r$ où $q$ est un entier relatif et $r$ est un entier naturel tel que $0\pp r<b$.
$\PGCD(a;b)=\PGCD(b;r)$
Preuve Propriété 5

D’après la propriété 3. on a $\Delta(a;b)=\Delta(b;r)$.
Donc $\PGCD(a;b)=\PGCD(b;r)$
$\quad$

[collapse]

$\quad$

Propriété 6 (algorithme d’Euclide) : On considère deux entiers naturels $a$ et $b$ tels que $a>b>0$.

  • $r_0$ est le reste de la division euclidienne de $a$ par $b$.
  • Si $r_0\neq 0$ on appelle alors $r_1$ le reste de la division euclidienne de $b$ par $r_0$.
  • Si $r_1\neq 0$ on appelle alors $r_2$ le reste de la division euclidienne de $r_1$ par $r_0$.
  • Si $r_{n-1}\neq 0$ on appelle alors $r_n$ le reste de la division euclidienne de $r_{n-2}$ par $r_{n-1}$.
  • Si $r_n\neq 0$ et que le reste de la division euclidienne de $r_{n-1}$ par $r_n$ est nul alors $\PGCD(a;b)=r_n$.

Preuve Propriété 6

  • $a=bq_0+r_0$ avec $0\pp r_0<b$ donc $\PGCD(a;b)=\PGCD\left(b;r_0\right)$
  • $b=r_0q_1+r_1$ avec $0\pp r_1<r_0$ donc $\PGCD\left(b;r_0\right)=\PGCD\left(r_0;r_1\right)$
  • $r_0=r_1q_2+r_2$ avec $0\pp r_2<r_1$ donc $\PGCD\left(r_0;r_1\right)=\PGCD\left(r_1;r_2\right)$
  • $r_{n-2}=r_{n-1}q_n+r_n$ avec $0< r_n<r_{n-1}$ donc $\PGCD\left(r_{n-2};r_{n-1}\right)=\PGCD\left(r_{n-1};r_n\right)$
  • $r_{n-1}=r_nq_{n+1}+0$ donc $\PGCD\left(r_{n-1};r_n\right)=r_n$ car $r_n$ divise $r_{n-1}$

La suite $\left(r_n\right)$ est une suite d’entiers positifs strictement décroissante. Un des restes dans cet algorithme sera donc nul.
On a également :
$\begin{align*} \PGCD(a;b)&=\PGCD\left(b;r_0\right)\\
&=\PGCD\left(r_0;r_1\right)\\
&=\PGCD\left(r_1;r_2\right)\\
&=\ldots \\
&=\PGCD\left(r_{n-1};r_n\right)\\
&=r_n\end{align*}$
$\quad$

[collapse]

$\quad$

Exemple : On veut déterminer $\PGCD(756;120)$
On utilise l’algorithme d’Euclide.
$756=6\times {\textcolor{red}{120}}+{\textcolor{blue}{36}}$
${\textcolor{red}{120}}=3\times {\textcolor{blue}{36}}+{\textcolor{orange}{12}}$
${\textcolor{blue}{36}}=3\times {\textcolor{orange}{12}}+0$
Le dernier reste non nul est $12$ donc $\PGCD(756;120)=12$

Propriété 7 : On considère deux entiers relatifs $a$ et $b$ tels que $(a;b)\neq (0;0)$ et un entier naturel $k$ non nul.
$\PGCD(ka;bk)=k\times \PGCD(a;b)$.
Preuve Propriété 7

  • Si $b$ divise $a$ alors $bk$ divise $ak$ et le plus rand diviseur de $bk$ est $k|b|$.
    Donc $\PGCD(ka;bk)=k|b|$
    Or, du fait que $b$ divise $a$, on également $\PGCD(a;b)=|b|$
    Par conséquent $k\PGCD(a;b)=k|b|$ et donc $\PGCD(ka;bk)=k\PGCD(a;b)$.
    On procède de la même manière si $a$ divise $b$.
  • Si $a$ ne divise pas $b$ et si $b$ ne divise pas $a$.
    D’après la propriété 4. on peut donc se ramener au cas où $a>b>0$.
    $k$ est un entier naturel non nul donc $ka>kb>0$.
    On a $a=bq+r$ avec $0\pp r<b$ par conséquent $ka=kbq+kr$ avec $0\pp kr < kb$
    En appliquant l’algorithme d’Euclide pour déterminer $\PGCD(ka;kb)$ on reprend en fait toutes les étapes du calcul de $\PGCD(a;b)$ en les multipliant par $k$.
    Si $r_n$ est le dernier reste non nul dans l’algorithme permettant de calculer $\PGCD(a;b)$ alors $kr_n$ est le dernier reste non nul dans l’algorithme permettant de calculer $\PGCD(ka;kb)$.
    Par conséquent $\PGCD(ka;bk)=k\times \PGCD(a;b)$.
    $\quad$

[collapse]

$\quad$

Exemple : $\PGCD(57;18)=3\PGCD(19;6)$ car $57=3\times 19$ et $18=3\times 6$.
Or le seuls diviseurs positifs de $6$ sont $1$, $2$, $3$ et $6$ et ceux de $19$ sont $1$ et $19$.
Par conséquent $\PGCD(19;6)=1$ et $\PGCD(57;18)=3$.

Propriété 8 : On considère deux entiers relatifs $a$ et $b$ tels que $(a;b)\neq (0;0)$.
$n$ est un diviseur commun de $a$ et $b$ si, et seulement si $n$ divise $\PGCD(a;b)$.
Preuve Propriété 8

On note $d=\PGCD(a;b)$.
On va montrer que $\Delta(a;b)$ est en fait l’ensemble des diviseurs de $d$.

En reprenant l’algorithme d’Euclide on a :
$\Delta(a;b)=\Delta\left(b;r_0\right)=\Delta\left(r_0;r_1\right)=\ldots=\Delta\left(r_{n-1};r_{n}\right)$.
Mais $r_n$ divise $r_{n-1}$ donc $\Delta\left(r_{n-1};r_{n}\right)$ est l’ensemble des diviseurs de $r_n$.
$r_n$ étant le dernier reste non nul on a $r_n=d$.
Par conséquent $\Delta(a;b)$ est en fait l’ensemble des diviseurs de $d$.

Donc $n$ est un diviseur commun de $a$ et $b$ si, et seulement si $n$ divise $\PGCD(a;b)$.
$\quad$

[collapse]

$\quad$

III Nombres premiers entre eux

Définition 2 : On considère deux entiers relatifs $a$ et $b$ non nuls.
On dit que $a$ et $b$ sont premiers entre eux si $\PGCD(a;b)=1$.

Exemples :

  • $\PGCD(3;2)=1$ donc $2$ et $3$ sont premiers entre eux.
  • $\PGCD(19;6)=1$ donc $19$ et $6$ sont premiers entre eux.
Propriété 9 : On considère deux entiers relatifs $a$ et $b$ non nuls et on note $d=\PGCD(a;b)$.
Les nombres $a’=\dfrac{a}{d}$ et $b’=\dfrac{b}{d}$ sont premiers entre eux.
Preuve Propriété 9

On a donc $a=a’d$ et $b=b’d$.
Par conséquent :
$\begin{align*} d&=\PGCD(a;b) \\
&=\PGCD\left(da’;db’\right) \\
&=d\times \PGCD\left(a’;b’\right)\end{align*}$
Ainsi $\PGCD\left(a’;b’\right)=1$ et les nombres $a’$ et $b’$ sont premiers entre eux.
$\quad$

[collapse]

$\quad$

Exemple : $\PGCD(68;24)=4$ et $\dfrac{68}{4}=17$ et $\dfrac{24}{4}=6$.
Par conséquent $17$ et $6$ sont premiers entre eux.

$\quad$

IV Théorème de Bézout

Propriété 10 (égalité de Bézout) : On considère deux entiers relatifs $a$ et $b$ non nuls et on note $d=\PGCD(a;b)$.
Il existe deux entiers relatifs $u$ et $v$ tels que $au+bv=d$.
Preuve Propriété 10

On suppose que $a$ et $b$ sont des entiers naturels non nuls (la propriété 4.6 nous permet de ne considérer que ce cas).

On considère l’ensemble $\mathscr{E}=\lbrace au+bv \in \N^*,u\in\Z\text{ et }v\in \Z\rbrace$.
$a=a\times 1+b\times 0$. Donc $\mathscr{E}$ est non vide.
$\mathscr{E}$ est donc une partie non vide de $\N$. Il possède donc un plus petit élément $g$.
$g\in \mathscr{E}$ : il existe deux entiers relatifs $u$ et $v$ tels que $g=au+bv$.
On va montrer que $g=d$.

  • Montrons que $d\pp g$
    $d$ divise toutes les combinaisons linéaires de $a$ et $b$. Par conséquent $d$ divise $g$.
    $d$ et $g$ sont deux entiers naturels donc $d\pp g$.
  • Montrons que $g\pp d$
    On a $a=gq+r$ avec $0\pp r<g$.
    Par conséquent :
    $\begin{align*} r&=a-gq \\
    &=a-(au+bv)q \\
    &=a-auq-bvq \\
    &=a(1-uq)-bvq\end{align*}$
    $r$ est donc une combinaison linéaire de $a$ et $b$ .
    Supposons que $r> 0$  alors $r\in \mathscr{E}$ et $r<g$, ce qui est absurde car $g$ est le plus petit élément de $\mathscr{E}$.
    Donc $r=0$
    Ainsi $g$ divise $a$.
    On montre de la même manière que $g$ divise $b$.
    $g$ est par conséquent un diviseur commun à $a$ et $b$.
    Par conséquent $g\pp d$.

Cela signifie donc que $d=g$
Il existe par conséquent deux entiers relatifs $u$ et $v$ tels que $au+bv=d$.
$\quad$

[collapse]

$\quad$

Remarques : 

  • Le couple $(u;v)$ tel que $au+bv=d$ n’est pas unique.
  • On peut utiliser l’algorithme d’Euclide pour déterminer un tel couple $(u;v)$.

Exemple : On a vu (exemple de l’algorithme d’Euclide) que $\PGCD(756;120)=12$.
On veut déterminer un couple $(u;v)$ tel que $756u+120v=12$
– $756=6\times 120+36$ donc $36=756-6\times 120$
– $120=3\times 36+12$ donc $12=120-3\times 36$
Par conséquent $12=120-3(756-6\times 120)$ soit $12=120-3\times 756+18\times 120$
Donc $12=-3\times 756+19\times 120$

Théorème 1 (théorème de Bézout) : Deux entiers relatifs $a$ et $b$ sont premiers si, et seulement si, il existe deux entiers relatifs $u$ et $v$ tels que $au+bv=1$.
Preuve Théorème 1

  • Si $a$ et $b$ sont premiers entre eux alors $\PGCD(a;b)=1$ et, d’après la propriété précédente, il existe deux entiers relatifs $u$ et $v$ tels que $au+bv=1$.
  • On suppose qu’il existe deux entiers relatifs $u$ et $v$ tels que $au+bv=1$.
    On appelle $d$ un diviseur commun à $a$ et $b$. Il divise donc toutes les combinaisons linéaires de $a$ et $b$, en particulier $au+bv$.
    $d$ divise par conséquent $1$.
    Ainsi $d=-1$ ou $d=1$.
    Le seul diviseur positif commun à $a$ et $b$ est donc $1$.
    Ainsi $a$ et $b$ sont premiers entre eux.
    $\quad$

[collapse]

$\quad$

Exemple : Montrons que, pour tout entier naturel $n$, les nombres $2n+1$ et $7n+3$ sont premiers entre eux.
Pour tout entier naturel $n$, $2n+1$ et $7n+3$ sont également des entiers naturels.
On a :
$\begin{align*} 7(2n+1)-2(7n+3) &=14n+7-14n-6 \\
&=1\end{align*}$
D’après le théorème de Bézout les nombres $2n+1$ et $7n+3$ sont donc premiers entre eux.

Propriété 11 : On considère trois entiers relatifs non nuls $a$, $b$ et $c$.
Si $\PGCD(a;b)=1$ et si $\PGCD(a;c)=1$ alors $\PGCD(a;bc)=1$.
Preuve Propriété 11

$\PGCD(a;b)=1$ : il existe donc deux entiers relatifs $u$ et $v$ tels que $au+bv=1$
$\PGCD(a;c)=1$ : il existe donc deux entiers relatifs $m$ et $n$ tels que $am+cn=1$
Par conséquent $(au+bv)(am+cn)=1$
Or
$\begin{align*} (au+bv)(am+cn)&=auam+aucn+bvam+bvcn \\
&=a(aum+ucn+bvm)+bc(vn)\end{align*}$
Ainsi $a(aum+ucn+bvm)+bc(vn)=1$
D’après le théorème de Bézout les nombres $a$ et $bc$ sont premiers entre eux, c’est-à-dire $\PGCD(a;bc)=1$.
$\quad$

[collapse]

$\quad$

V Théorème de Gauss

Théorème 2 (théorème de Gauss) : On considère trois entiers relatifs non nuls $a$, $b$ et $c$.
Si $a$ est premier avec $b$ et divise $bc$ alors $a$ divise $c$.
Preuve Théorème 2

$a$ et $b$ sont premiers entre eux. D’après le théorème de Bézout, il existe donc deux entiers relatifs $u$ et $v$ tels que $au+bv=1$.
Par conséquent $acu+bcv=c$.
$a$ divise donc $acu$ et $bcv$ (car il divise $bc$). $a$ divise donc toutes leurs combinaisons linéaires, en particulier $acu+bcv$ c’est-à-dire $c$.
$\quad$

[collapse]

$\quad$

Propriété 12 : On considère trois entiers relatifs non nuls $a$, $b$ et $c$.
Si $b$ et $c$ sont premiers entre eux et divisent $a$ alors $bc$ divise $a$.
Preuve Propriété 12

$a$ est divisible par $b$. Il existe alors un entier relatif $k$ tel que $a=bk$.
$a$ est divisible par $c$, donc $bk$ est divisible par $c$ avec $b$ et $c$ premiers entre eux.
D’après le théorème de Gauss, $c$ divise $k$.
Il existe donc un entier relatif $k’$ tel que $k=k’c$.
Par conséquent $a=bck’$.
$bc$ divise donc $a$.
$\quad$

[collapse]

$\quad$

Exemple : Si un entier $n$ est divisible par $2$ et par $3$ alors, puisque $2$ et $3$ sont premiers entre eux, $n$ est divisible par $6$.

Propriété 13 (conséquence) : On considère un entier relatif $a$, un entier naturel $k$ et deux entiers naturels premiers entre eux $m$ et $n$.
Si $a\equiv k~[n]$ et $a\equiv k~[m]$ alors $a\equiv k~[mn]$.
Preuve Propriété 13

$a\equiv k~[n]$ et $a\equiv k~[m]$
Donc $a-k$ est divisible par $n$ et $m$ premiers entre eux.
D’après la propriété précédente, $a-k$ est divisible par $mn$, c’est-à-dire $a\equiv k~[mn]$.
$\quad$

[collapse]

$\quad$

Exemple :  $1~145\equiv 5~[12]$ et $1~145\equiv 5~[19]$. $12$ et $19$ sont premiers entre eux et $12\times 19=228$.
Donc $1~145\equiv 5~[228]$.

VI Équations diophantienne

On considère trois entiers relatifs $a$, $b$ et $c$ tels que $c$ soit un multiple de $\PGCD(a;b)$. On souhaite déterminer l’ensemble des couples d’entiers $(x;y)$ solutions de l’équation $ax+by=c$.

Exemple : On veut déterminer l’ensemble des couples d’entiers $(x;y)$ solutions de l’équation $(E) :\quad 6x+8y=56$.

  • 1ère étape : On simplifie l’équation par $\PGCD(a;b)$ et on obtient l’équation $a’x+b’y=c’$
    $\PGCD(6;8)=2$ : $6x+8y=56\ssi 3x+4y=28$
    $\quad$
  • 2ème étape : On cherche une solution particulière de l’équation $a’x+b’y=1$
    On cherche donc ici une solution de l’équation $3x+4y=1$
    On peut reprendre la méthode vue dans l’exemple de l’identité de Bézout ou voir, ici, que $3\times 3+4\times (-2)=1$.
    $\quad$
  • 3ème étape : On cherche une solution particulière de l’équation $a’x+b’y=c’$.
    On multiplie chacun des nombres du couple solution par $c’$
    Ainsi $(3\times 28;-2\times 28)$ soit $(84;-56)$ est une solution de l’équation $3x+4y=28$.
    $\quad$
  • 4ème étape : On détermine toutes les autres solutions
    On considère $(x;y)$ une solution de l’équation $3x+4y=28$.
    On a donc $3\times 84+4\times (-56)=28$ et $3x+4y=28$
    Par différence, on obtient alors $3(84-x)+4(-56-y)=0$
    Soit $3(84-x)=4(56+y) \quad (1)$
    $3$ et $4$ sont premiers entre eux.
    Donc, d’après le théorème de Gauss, $3$ divise $56+y$.
    Il existe alors un entier relatif $k$ tel que $56+y=3k$.
    En remplaçant dans l’équation $(1)$ on obtient $3(84-x)=4\times 3k$ soit $84-x=4k$.
    Par conséquent $56+y=3k$ et $84-x=4k$ soit $x=84-4k$ et $y=-56+3k$
    Les solutions de l’équation $(E)$ sont donc de la forme $(84-4k;-56+3k)$.
    $\quad$
    Montrons que la réciproque est vraie, c’est-à-dire que, pour tout entier relatif $k$, le couple $(84-4k;-56+3k)$ est solution de l’équation $(E)$.
    $\begin{align*} 6(84-4k)+8(-56+3k)&=504-24k-448+24k\\
    &=56\end{align*}$
    $\quad$
  • Conclusion : Les solutions de l’équation $(E)$ sont les couples $(84-4k;-56+3k)$ pour tout $k\in\Z$.
    $\quad$