A3 : PGCD

Vous pouvez télécharger une version imprimable résumant le contenu de ce cours en format .pdf avec ce lien.

PGCD de deux entiers

Soient $a$, $b$ et $c$ trois entiers relatifs non nuls.

PGCD de deux entiers relatifs

Étant donnés deux entiers relatifs $a$ et $b$ dont au moins un est non nul, l'ensemble des diviseurs communs à $a$ et à $b$ admet un plus grand élément, que l'on appelle le plus grand commun diviseur à $a$ et $b$ et que l'on note $PGCD(a,b)$.

Déterminer la liste des diviseurs de 175 et de 315.
En déduire $PGCD(175,315)$, le plus grand commun diviseur des deux nombres 175 et 315.

Soient deux entiers relatifs $a$ et $b$ , avec $a\ne 0$, on a :

$a$ étant positif, $PGCD(a,0)=a$; $PGCD(a,1)=1$.
$PGCD(a,b)=PGCD(|a|,|b|)$.
Si $b$ divise $a$, $PGCD(a,b)=|b|$.
Si $b$ est premier et ne divise pas $a$, $PGCD(a,b)=1$.

Démontrer le dernier point de la propriété précédente.

Algorithme d'Euclide

Soient $a$ et $b$ deux entiers naturels non nuls avec $b<a$.
On appelle $r$ le reste de la division euclidienne de $a$ par $b$. $$PGCD(a,b)=PGCD(b,r)$$

Démonstration de $PGCD(a,b)=PGCD(b,r)$

Montrer que $\{d \in\mathbb{N}$, $d|a$ et $d|b\}=\{d \in\mathbb{N}$, $d|b$ et $d|r\}$. Autrement dit l'ensemble des diviseurs de $a$ et de $b$ est aussi l'ensemble les diviseurs de $b$ et de $r$.
Conclure quant aux PGCD.

Algorithme d'Euclide

Cette dernière propriété permet de mettre en place une procédure pour déterminer le PGCD de deux entiers c'est l'algorithme d'Euclide.

315 = 175 $\times$ 1 + 140
175 = 140$\times$ 1+ 35
140 = 35$\times$ 4 +0

On obtient donc en appliquant la propriété précédente successivement :

$PGCD(315,175)=PGCD(175,140)$ d'après la ligne 1.
$PGCD(175,140)=PGCD(140,35)$ d'après la ligne 2.
$PGCD(140,35)=PGCD(35,0)$ d'après la ligne 3.

Comme $PGCD(35,0)=35$, on en déduit que $PGCD(315,175)=35$.

Algorithme d'Euclide

Lorsque $b$ ne divise pas $a$, l'algorithme d'Euclide consiste :

à effectuer la division euclidienne de $a$ par $b$,
à répéter les divisions euclidiennes de diviseur et du reste de la division euclidienne précédente.
à s'arrêter lorsque l'on obtient un reste nul.

Le PGCD des deux nombres entiers naturels $b$ et $a$ est égal au dernier reste non nul obtenu par l'algorithme d'Euclide.

En notant la succession des quotients obtenus $q_0, q_1, q_2, ..., q_{n-1}, q_{n}, q_{n+1}$ et la succession des restes obtenus $r_0, r_1, r_2, ..., r_{n-1}, r_{n}$, on peut visualiser l'algorithme ainsi :

schmématisatisation colorée de l'algorithme d'Euclide

Cet algorithme est appellée algorithme d'Euclide car la mathématicien Euclide a décrit dans le livre VII des ses Éléments vers 300 avant notre ère un algorithme similaire.

La méthode décrite par Euclide propoe de répéter le fait d'enlever au plus grand nombre le plus petit, ceci autant que possible, puis d'enlever le reste au plus petit des nombres. On arrête lorsque l'on obtient un nombre qui divise le précédent.

Avec des notations actuelles, cette méthode utilise l'égalité : $PGCD(a,b)=PGCD(a-b,b)$.

Cet algorithme a été trouvé indépendamment par des mathématiciens chinois et indiens. Une utilité de cette méthode était de résoudre des problèmes d'astronomie, en particulier pour obtenir des calendriers plus précis.
Si vous êtes intéressé.e.s par cette application, vous pouvez chercher le TP2 p.131 de votre manuel.

Appliquer l'algorithme d'Euclide pour déterminer le PGCD de $7260$ et de $1107$

Écrire une fonction euclide en Python qui prend comme argument deux entiers $a$ et $b$ et qui renvoie le PGCD de $a$ et de $b$.

Si vous rencotrez un problème avec votre IDE, vous pouvez utiliser ce trinket.

Pourquoi est-on sûr que l'algorithme d'Euclide s'arrête au bout d'un nombre fini d'étapes ?

Homogénéité :

Soient trois entiers naturels $a$, $b$, et $k$. $$PGCD(ka,kb)=k\times PGCD(a,b).$$

Démonstration de l'homogénéité du PGCD

On suppose, quitte à permuter $a$ et $b$ que $a ≥ b$. Notons $r$ le reste de la division euclidienne de $a$ par $b$.

Cas où $b$ divise $a$. Montrer que $PGCD(ka,kb)=k\times PGCD(a,b).$
Cas où $b$ ne divise pas $a$.
1. Écrire les divisions euclidiennes de $a$ par $b$ et de $ka$ par $kb$.
2. En déduire que $kr$ est le reste de la division euclidienne de $ka$ par $kb$.
3. Utiliser l'algorithme d'Euclide et la suite des restes des divisions euclidiennes, pour démontrer que $PGCD(ka,kb)=k\times PGCD(a,b).$

Soient $a$ et $b$ deux entiers non simultanément nuls.

$d$ est un diviseur commun à $a$ et à $b$ si, et seulement si, $d$ divise $PGCD(a,b)$.

Quitte à multiplier par $-1$, on peut supposer que les deux nombres $a$ et $b$ sont positifs.

Soit $d$ un diviseur de $a$ et de $b$.
1. Montrer qu'alors $d$ divise $PGCD(a,b)$.
2. Écrire la succession des égalités liées à l'algorithme d'Euclide pour trouver le PGCD de $a$ et de $b$.
3. Justifier que $d$ divise chacun des restes successifs obtenus dans la mise en oeuvre de l'algorithme d'Euclide.
4. Qu'en déduire ?
Soit $d$ un diviseur de $PGCD(a,b)$.

Justifer que $d$ divise $a$ et $b$.
Qu'avez-vous ainsi montré ?

Nombres premiers entre eux

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

Lorsque $PGCD(a,b)=1$, on dit que les entiers $a$ et $b$ sont premiers entre eux.

Cette définition revient à dire que les seuls diviseurs entiers communs aux entiers $a$ et $b$ sont 1 et -1.

Soient $a$ et $b$ deux entiers naturels.
$D=PGCD(a,b)$ si, et seulement si $\frac{a}{D}$ et $\frac{b}{D}$ sont des entiers premiers entre eux.

Démonstration de $D=PGCD(a,b)$ si, et seulement si $\frac{a}{D}$ et $\frac{b}{D}$ sont des entiers premiers entre eux.
Soient $a$ et $b$ deux entiers naturels non nuls.

Idée : travailler par double implication pour démontrer l'équivalence.

On note $D=PGCD(a,b)$.
1. Justifier que $\frac{a}{D}$ et $\frac{b}{D}$ sont des entiers naturels non nuls.
2. On note $d=PGCD(\frac{a}{D},\frac{b}{D})$. En utilisant la propriété d'homogénéité montrer que $d=1$.
3. Qu'a-t-on déjà réussi à démontrer ?
Réciproquement on suppose que $\frac{a}{D}$ et $\frac{b}{D}$ sont premiers entre eux.
Montrer que $PGCD(a,b)=D$.

Soient $a$, $b$ et $c$ trois nombres entiers non nuls.
Ces trois nombres ont le même Plus Grand Commun Diviseur : $PGCD(PGCD(a,b),c)=PGCD(a,PGCD(b,c))$, ce nombre peut être noté $PGCD(a,b,c)$.

Idée :
Comme $PGCD(PGCD(a,b),c) >0$ et $PGCD(a,PGCD(b,c))>0$, il suffit de montrer que $PGCD(PGCD(a,b),c) | PGCD(a,PGCD(b,c))$ et $PGCD(a,PGCD(b,c)) | PGCD(PGCD(a,b),c)$, pour montrer que $PGCD(PGCD(a,b),c) = PGCD(a,PGCD(b,c))$, d'après le deuxième propriété de ce cours A1.

Premier sens de la divisibilité
Montrons d'abord que $PGCD(PGCD(a,b),c) | PGCD(a,PGCD(b,c))$.
Soit $d$ le $PGCD$ des nombres $PGCD(a,b)$ et $c$.
Comme $d$ divise $PGCD(a,b)$, $d$ divise $a$ et $b$, d'après la propriété 5.
Dès lors, $d$ divise $b$ et $c$ donc aussi $PGCD(b,c)$ (même propriété).
Ainsi, $d$ divise $a$ et $PGCD(b,c)$ donc leur PGCD : $PGCD(a,PGCD(b,c))$(même propriété).

Second sens de la divisibilité
Montrons désormais que $PGCD(a,PGCD(b,c)) | PGCD(PGCD(a,b),c)$.
Il suffit de permuter les rôles de $a$ et de $c$ qui jouent un rôle symétrique.
Soit $d$ le $PGCD$ des nombres $PGCD(b,c)$ et $a$.
Comme $d$ divise $PGCD(b,c)$, $d$ divise $c$ et $b$, d'après la propriété 5.
Dès lors, $d$ divise $b$ et $a$ donc aussi $PGCD(a,c)$ (même propriété).
Ainsi, $d$ divise $c$ et $PGCD(a,b)$ donc leur PGCD : $PGCD(PGCD(a,b),c)$(même propriété).

Comme $PGCD(PGCD(a,b),c) | PGCD(a,PGCD(b,c))$ et $PGCD(a,PGCD(b,c)) | PGCD(PGCD(a,b),c)$, $PGCD(a,PGCD(b,c)) = PGCD(PGCD(a,b),c)$.

Exercices

Calculer le PGCD des nombres suivants :

$a=826$ et $b=644$.
$a=1210$ et $b=308$.
$a=3256$ et $b=-2354$.

À l'aide du PGCD donner la version irréductible de ces fractions :

$\dfrac{1864}{1631}$
$\dfrac{3103650}{3420}$

Déterminer l'ensemble des entiers naturels $n$ inférieurs à 100 tels que $PGCD(n,324)=12$.

Vous pouvez étudier la liste des diviseurs de 324 si vous restez bloqué.e.s.

Déterminer l'ensemble des entiers naturels $n$ inférieurs à 100 tels que $PGCD(n,150)=6$.

Soient $a=n$ et $b=n+1$, où $n$ est un entier naturel.

Montrer que si $d$ divise $a$ et $b$ alors $|d|=1$.
En déduire que $a$ et $b$ sont premier entre eux.

Même énoncé avec $a=n+1$ et $b=2n+1$

Soit $n$ un entier naturel non nul. En utilisant l'algorithme d'Euclide, démontrer que les entiers $a$ et $b$ sont premiers entre eux.

$a=3n+2$ et $b=n+1$.

Code de déblocage de la correction :
$a=5n+7$ et $b=2n+3$.

Code de déblocage de la correction :
$a=3n^2+5n+1$ et $b=3n+1$.

Code de déblocage de la correction :

Calculer les valeurs entières positives de $a$ et $b$ possibles sachant que $a+b=360$ et $PGCD(a,b)=18$.

Calculer les valeurs entières positives de $a$ et $b$ possibles sachant que $a-b=105$ et $PGCD(a,b)=15$ et que $a$ et $b$ sont inférieurs à 300.

Calculer les valeurs entières positives de $a$ et $b$ possibles sachant que $ab=5202$ et $PGCD(a,b)=17$.

Soient $a$ et $b$ deux entiers relatifs non nuls et $n$ un entier naturel non nul.

On suppose que $a$ peut s'écrire sous la forme $a=k\times n +b$, où $k$ est un entier relatif. Montrer que le $PGCD(a,n)=PGCD(b,n)$
Montrer que la réciproque est fausse.

On considère la fonction Python suivante dont les arguments sont $a$ et $b$ deux entiers naturels.

def mystere(a,b):
    n = 1
    while n <= a and n <= b:
        if a % n == 0 and b % n == 0:
            p = n
        n = n+1
    return p

Que renvoie l'instruction suivante :
```
 >>> mystere(142,76)
```
Quel est le rôle de cette fonction ?

Partie A : conjecture grâce à un programme en langage Python :

Créer une fonction PGCD qui renvoie le PGCD de deux nombres entiers donnés comme arguments.
Soit $n$ un entier naturel supérieur ou égal à 2.

On considère les entiers $A$ et $B$ définis par $A=n^2+4n+5$ et $B=n+2$.

Créer un fonction liste_PGCD qui prend en argument un entier $p$ et qui renvoie la liste des $PGCD(A,B)$ lorsque $n$ décrit toute la liste des entiers natrurels entre 2 et $p$.
Conjecturer le PGCD de $A$ et de $B$ suivant les valeurs de $n$.

Partie B : preuve de la conjecture :

Effectuer la division euclidienne de $A$ par $B$.
En déduire que $PGCD(A,B)=PGCD(n+2,1)$.
En déduire le $PGCD$ de $A$ et de $B$ suivant les valeurs de $n$ pour prouver ou corriger la conjecture émise à la partie A.

Un pianiste produit un son complexe est composé en appuyant sur trois touches à la fois d'un piano quelque peu désaccordé :

touche n°85 du $La_6$ de fréquence 3520 Hz,
touche n°82 du $Fa_6\text{#}$ de fréquence 2960 Hz,
touche n°71 du $Sol_5$ de fréquence 1568 Hz.

Source : wikipedia

On admet que le son complexe produit par ces trois touches admet une fréquence égale au PGCD des trois fréquences.

Quelle est la fréquence de ce son complexe ?

Une boîte parallélépipédique rectangle est de dimensions intérieures 31.2 cm, 13 cm et 7.8 cm.

Elle est entièrement remplie par des cubes à jouer dont l'arête est un nombre entier de millimètres.

Quel nombre minimal de cubes peut contenir cette boîte ?

Partie A : conjecture grâce à un programme en langage Python :

Créer une fonction PGCD qui renvoie le PGCD de deux nombres entiers donnés comme arguments.
Soit $n$ un entier naturel supérieur ou égal à 2.

On considère les entiers $A$ et $B$ définis par $A=2n^3+7n^2-21n+15$ et $B=n^2+4n-9$.

Créer un fonction liste_PGCD qui prend en argument un entier $p$ et qui renvoie la liste des $PGCD(A,B)$ lorsque $n$ décrit toute la liste des entiers natrurels entre 2 et $p$.
Conjecturer le PGCD de $A$ et de $B$ suivant les valeurs de $n$.

Partie B : preuve de la conjecture :

Justifier que pour tout entier naturel $n\ge 2$ : $4n^2+4n-9>n+6$.
Effectuer la division euclidienne de $A$ par $B$.
Démontrer que $PGCD(A,B)=PGCD(n+6,3)$.
En déduire le $PGCD$ de $A$ et de $B$ suivant les valeurs de $n$ pour prouver ou corriger la conjecture émise à la partie A.

Demander le programme !

La notion de PGCD de deux entiers relatifs.
la notion de couple d'entiers premiers entre eux.

Déterminer le PGCD de deux entiers naturels.
Déterminer les diviseurs communs de deux entiers naturels.
Reconnaître des nombres premiers entre eux.

Les différents auteurs mettent l'ensemble du site à disposition selon les termes de la licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International

▲