PGCD de deux entiers

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

Étant donnés deux entiers relatifs $a$ et $b$ dont au moins 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)$.

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

  1. $a$ étant positif, $PGCD(a,0)=a$; $PGCD(a,1)=1$
  2. $PGCD(a,b)=PGCD(|a|,|b|)$.
  3. Si $b$ divise $a$, $PGCD(a,b)=|b|$
  4. 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.

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

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'algortihme 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'Eclide

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

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

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

  2. Cas où $a > b$.

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

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

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

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

    3. Qu'en déduire ?

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

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

  3. Qu'avez-vous ainsi montré ?

3. 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$
  2. Réciproquement on suppose que $\frac{a}{D}$ et $\frac{b}{D}$ sont premiers entre eux.
    Montrer que $PGCD(a,b)=D$

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

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

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

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

Vous pouvez-vous aider de la méthode page 120 de votre livre si vous restez bloqué.e.

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

Soient $a=n$ et $b=n+1$, $a$, $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 de $a$ et $b$ possibles sachant que $a+b=360$ et $PGCD(a,b)=18$.

Calculer les valeurs 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 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. Efectuer la division euclidienne de $A$ par $B$.

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

  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.

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 est le nombre minimal de cubes que peut contenir cette boîte ?

5. Demander le programme !

Licence Creative Commons
NSI de Auteurs : Thomas Lourdet, Johan Monteillet, est mis à disposition selon les termes de la licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.
▲