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)$.

  1. Déterminer la liste des diviseurs de 175 et de 315.

  2. En déduire $PGCD(175,315)$, le plus grand commun diviseur des deux nombres 175 et 315.

  3. Code de déblocage de la correction :

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

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

Code de déblocage de la correction :

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)$

  1. 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$.

  2. Conclure quant aux PGCD.

Code de déblocage de la correction :

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.

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

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

  1. $PGCD(315,175)=PGCD(175,140)$ d'après la ligne 1.
  2. $PGCD(175,140)=PGCD(140,35)$ d'après la ligne 2.
  3. $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 :

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$

Code de déblocage de la correction :

É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$.

Code de déblocage de la correction :

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

Code de déblocage de la correction :

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$.

  1. Cas où $b$ divise $a$. Montrer que $PGCD(ka,kb)=k\times PGCD(a,b).$

  2. 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).$

Code de déblocage de la correction :

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.

  1. Soit $d$ un diviseur de $a$ et de $b$.

      Cas où $b$ divise $a$.

    1. Montrer qu'alors $d$ divise $PGCD(a,b)$.

    2. Cas où $b$ ne divise pas $a$.

    3. Écrire la succession des égalités liées à l'algorithme d'Euclide pour trouver le PGCD de $a$ et de $b$.

    4. Justifier que $d$ divise chacun des restes successifs obtenus dans la mise en oeuvre de l'algorithme d'Euclide.

    5. Qu'en déduire ?

  2. Soit $d$ un diviseur de $PGCD(a,b)$.

    Justifer que $d$ divise $a$ et $b$.

  3. Qu'avez-vous ainsi montré ?

Code de déblocage de la correction :

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.

  1. 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 ?

  2. Réciproquement on suppose que $\frac{a}{D}$ et $\frac{b}{D}$ sont premiers entre eux.
    Montrer que $PGCD(a,b)=D$.

Code de déblocage de la correction :

Exercices

Calculer le PGCD des nombres suivants :

  1. $a=826$ et $b=644$.

  2. $a=1210$ et $b=308$.

  3. $a=3256$ et $b=-2354$.

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

  1. $\dfrac{1864}{1631}$
  2. $\dfrac{3103650}{3420}$

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

Vous pouvez étuider 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.

  1. Montrer que si $d$ divise $a$ et $b$ alors $|d|=1$.

  2. 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.

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

  2. $a=5n+7$ et $b=2n+3$.

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

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=1734$ et $PGCD(a,b)=17$.

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

  1. 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)$

  2. 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  
                    
  1. Que renvoie l'instruction suivante :

     >>> mystere(142,76)

  2. Quel est le rôle de cette fonction ?

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

  1. Créer une fonction PGCD qui renvoie le PGCD de deux nombres entiers donnés comme arguments.

  2. 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$.

  3. Conjecturer le PGCD de $A$ et de $B$ suivant les valeurs de $n$.

    Partie B : preuve de la conjecture :

  1. Effectuer la division euclidienne de $A$ par $B$.

  2. En déduire que $PGCD(A,B)=PGCD(n+2,1)$.

  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.

Code de déblocage de la correction :

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

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 :

  1. Créer une fonction PGCD qui renvoie le PGCD de deux nombres entiers donnés comme arguments.

  2. 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$.

  3. Conjecturer le PGCD de $A$ et de $B$ suivant les valeurs de $n$.

    Partie B : preuve de la conjecture :

  1. Justifier que pour tout entier naturel $n\ge 2$ : $4n^2+4n-9>n+6$.

  2. Effectuer la division euclidienne de $A$ par $B$.

  3. Démontrer que $PGCD(A,B)=PGCD(n+6,3)$.

  4. 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.

Code de déblocage de la correction :

Demander le programme !

Licence Creative Commons
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