j'ai compris mes maths
J'ai compris.com
Cours et exercices corrigés en vidéo comme en classe
lycée
collège
primaire
Manuel scolaire

Web


En construction

En construction

Terminale S

PGCD - Spé Maths


PGCD de 2 entiers ou plus


Comprendre la notion de PGCD: Cours de math en vidéo
  • Diviseurs communs
    Dire que $d$ est un diviseur commun de $a$ et $b$
    $\Updownarrow$
    $d$ divise $a$ et $d$ divise $b$
    $a$, $b$ sont des entiers relatifs.
    $d$ est un entier relatif non nul.

      3 est un diviseur commun de 9 et 12.
    Car 3 divise 9 et 3 divise 12.
  • Comprendre la notion de PGCD sur un exemple:
    ${\rm PGCD}(15;20)$
    L'ensemble des diviseurs communs à $15$ et $20$ est non vide
    Il contient 1 qui divise 15 et 20.

    L'ensemble des diviseurs communs à $15$ et $20$ est fini
    Donc l'ensemble des diviseurs communs à $15$ et $20$ admet un plus grand élément
    Si un ensemble est non vide et fini,
    alors cet ensemble
    a un plus grand élément.

    Ce plus grand élément s'appelle le PGCD de $15$ et $20$
    Le PGCD de 15 et 20 se note
    PGCD(15;20)


    Les diviseurs de 15 sont: -15;-5;-3;-1;1;3;5;15
    Les diviseurs de 20 sont: -20;-10;-5;-4;-2;-1;1;2;4;5;10;20
    Donc les diviseurs communs à 15 et 20 sont -5;-1;1;5
    Et donc le PGCD(15,20)=5
    Car le plus grand élément
    parmi les diviseurs communs à 15 et 20
    est 5.
  • Définition du ${\rm PGCD}(a;b)$
    L'ensemble des diviseurs communs à $a$ et $b$ est non vide
    Il contient 1 qui divise toujours $a$ et $b$.

    L'ensemble des diviseurs communs à $a$ et $b$ est fini
    Donc l'ensemble des diviseurs communs à $a$ et $b$ admet un plus grand élément
    Si un ensemble est non vide et fini,
    alors cet ensemble
    a un plus grand élément.

    Ce plus grand élément s'appelle le PGCD de $a$ et $b$
    Le PGCD de $a$ et $b$ se note
    PGCD($a$;$b$)

    Quand on parle de ${\rm PGCD}(a;b)$
    $a$ et $b$ sont des entiers relatifs.
    Et l'un des deux au moins est non nul.
  • Premiers entre eux
    Lorsque ${\rm PGCD}(a;b)=1$, on dit que $a$ et $b$ sont premiers entre eux.
    15 et 8 sont premiers entre eux
    Car le plus grand diviseur commun à 15 et 8 est 1.
    Donc le PGCD(15;8)=1.


    15 et 12 ne sont pas premiers entre eux
    Car le plus grand diviseur commun à 15 et 12 est 3.
    Donc le ${\rm PGCD(15;12)}=3\ne 1$.


Propriétés du PGCD: Cours de math en vidéo et Cours de math en vidéo
  • Propriétés du PGCD
    Si $a$ divise $b$
    Si $a$ divise $b$ alors ${\rm PGCD}(a;b)=|a|$

    ${\rm PGCD}(a;b)=1$
    Lorsque le PGCD de $a$ et $b$ vaut 1
    On dit que $a$ et $b$ sont premiers entre eux

    Exemple avec 3 et 8:
    Les diviseurs de 3 sont : -3;-1;1;3
    Les diviseurs de 8 sont : -8;-4;-2;-1;1;2;4;8
    Les diviseurs communs à 3 et 8 sont : -1;1
    Donc le plus grand diviseur commun à 3 et 8 est 1
    Donc PGCD(3;8)=1
    Donc 3 et 8 sont premiers entre eux.

    ${\rm PGCD}(a;0)$
    Tous les entiers divisent 0.
    Par exemple 3 divise 0.
    Car $0=3\times 0$.

    Donc les diviseurs communs à 0 et $a$ sont les diviseurs de $a$.
    Et le plus grand diviseur de $a$ est $|a|$.
    Donc le ${\rm PGCD}(0;a)=|a|$.
    Exemple
    Les diviseurs de -6 sont -6;-3;-2;-1;1;2;3;6
    Les diviseurs de 0 sont tous les entiers.
    Donc les diviseurs communs à 0 et -6 sont les diviseurs de -6.
    Donc le plus grand diviseur commun à 0 et -6 est 6
    Donc le PGCD(0;-6)=6

    ${\rm PGCD}(a;1)$
    ${\rm PGCD}(a;1)=1$

    car
    Les seuls diviseurs de 1 sont : -1 et 1
    Et -1 et 1 sont aussi diviseurs de $a$.
    Donc les diviseurs communs à $a$ et 1 sont -1 et 1
    Donc le plus grand diviseur commun à $a$ et 1 est 1.

    ${\rm PGCD}(-a;b)$
    ${\rm PGCD}(-a;b)={\rm PGCD}(a;b)$
    Car les diviseurs de -a sont les mêmes que les diviseurs de a.
    PGCD(-24;9)=PGCD(24;9)


    L'intérêt de cette propriété:
    Quand on a un PGCD avec un entier négatif,
    on se ramenera à un entier positif.

    ${\rm PGCD}$ et reste
    ${\rm PGCD}(a;b)={\rm PGCD}(b;r)$
    $a$ et $b$ sont des entiers positifs non nuls,
    avec $a\gt b$.
    $r$ est le reste de la division euclidienne $a$ par $b$.


    Exemple
    PGCD(57;15)=PGCD(15;12)
    Faisons la division euclidienne de 57 par 15:
    $57=3\times 15 +12$ donc le reste $r=12$.

    Donc
    PGCD(57;15)=PGCD(15;12).

    ${\rm PGCD}(a-b;b)$
    ${\rm PGCD}(a-b;b)={\rm PGCD} (a;b)$
    ${\rm PGCD}(23;8)$ $={\rm PGCD}(23-8;8)={\rm PGCD}(15;8)$
    $={\rm PGCD}(15-8;8)={\rm PGCD}(7;8)=1$


    ${\rm PGCD}(ka;kb)$
    ${\rm PGCD}(ka;kb)=k\times {\rm PGCD}(a;b)$
    où $a$, $b$ et $k$ sont des entiers strictement positifs.


    Cette propriété s'appelle propriété d'homogénéité.


    ${\rm PGCD}(a;p)$
    Soit $p$ un nombre premier,
    $a$ un entier relatif non nul, non divisible par $p$
    alors
    ${\rm PGCD}(a;p)=1$
    Autrement dit,
    $p$ est premier avec tout entier qui n'est pas un de ses multiples.


  • Propriété très utile en exercice du PGCD
    ${\rm PGCD}(a;b)=$
    ${\rm PGCD}(a;b)={\rm PGCD}(a;b-ka)$
    $a$, $b$ et $k$ sont des entiers,
    et $a\ne 0$.

    Cette propriété s'appelle
    le lemme d'Euclide


    Exemple:
    Déterminer pour tout entier naturel $n$ non nul, ${\rm PGCD}(9n+4;2n+1)$
    ${\rm PGCD}(9n+4;2n+1)$ $={\rm PGCD}(9n+4-4(2n+1);2n+1)$
    $={\rm PGCD}(n;2n+1)={\rm PGCD}(n;2n+1-2n)$
    $={\rm PGCD}(n;1)$=1
    Attention
    on ne change qu'un des deux nombres à la fois dans le PGCD
    pas les 2 à la fois!

  • Propriété caractéristique du PGCD
    Soit $a=da'$ et $b=db'$
    Si ${\rm PGCD}(a';b')=1$ alors ${\rm PGCD}(a;b)=d$
    $\left. \begin{array}{l} a=5a' \\ b=5b' \\ {\rm PGCD}(a';b')=1 \end{array} \right\}$ alors \[{\rm PGCD}(a; b )=5\]


    Si ${\rm PGCD}(a;b)=d$ alors ${\rm PGCD}(a';b')=1$
    $\left. \begin{array}{l} a=5a' \\ b=5b' \\ {\rm PGCD}(a;b)=5 \end{array} \right\}$ alors \[{\rm PGCD}(a'; b' )=1\]

Algorithme d'Euclide expliqué en vidéo Cours de math en vidéo et Cours de math en vidéo
  • ${\rm PGCD}(a;b)={\rm PGCD}(b;r)$
    L'algorithme d'Euclide repose sur cette propriété:
    ${\rm PGCD}(a;b)={\rm PGCD}(b;r)$
    $a$ et $b$ sont des entiers positifs non nuls,
    avec $a\gt b$.
    $r$ est le reste de la division euclidienne $a$ par $b$.

    Cours de math en vidéo
  • Algorithme d'Euclide
    L'algorithme d'Euclide expliqué en vidéo Cours de math en vidéo
    L'algorithme d'Euclide
    permet de trouver le PGCD en appliquant la propriété
    ${\rm PGCD}(a;b)={\rm PGCD}(b;r)$
    $a$ et $b$ sont des entiers positifs non nuls,
    avec $a\gt b$.
    $r$ est le reste de la division euclidienne $a$ par $b$.

    jusqu'à obtenir un reste nul.

    Cherchons PGCD(57;15)
    PGCD(57;15)=PGCD(15;12)
    On fait la division euclidienne de 57 par 15
    $57=3\times 15+12$ donc le reste est 12.
    Donc PGCD(57;15)=PGCD(15;12)


    On recommence avec PGCD(15;12)
    On fait la division euclidienne de 15 par 12
    $15=1\times 12+3$ donc le reste est 3.
    Donc PGCD(15;12)=PGCD(12;3)

    PGCD(15;12)=PGCD(12;3)

    On recommence avec PGCD(12;3)
    PGCD(12;3)=PGCD(3;0)
    On fait la division euclidienne de 12 par 3
    $12=3\times 4+0$ donc le reste est 0.
    Donc PGCD(12;3)=PGCD(3;0)

    On s'arrète dès qu'on trouve un reste nul.
    PGCD(3;0)=3
    Donc le PGCD est le dernier reste non nul.


    Finalement
    PGCD(57;15)=PGCD(15;12)=PGCD(12;3)=PGCD(3;0)=3
    On est sûr que l'algorithme d'Euclide se termine, car:
    A chaque fois fait une division euclidienne,
    le reste diminue d'au moins 1 en restant positif.
    Le reste finit donc nécessairement par atteindre 0.
Compléments importants
  • Diviseur commun et PGCD
    Les diviseurs communs $a$ et $b$ sont les diviseurs du ${\rm PGCD}(a;b)$.

    Pour trouver les diviseurs communs à 15 et 20,
    il suffit de trouver les diviseurs du ${\rm PGCD}(15;20)$.
    Or ${\rm PGCD}(15;20)=5$
    Et les diviseurs de 5 sont -5;-1;1;5
    Donc les diviseurs communs à 15 et 20 sont -5;-1;1;5.
  • PGCD de 3 entiers ou plus
    Pour trouver le PGCD de 3 entiers,
    On cherche le PGCD de 2 d'entre eux, que l'on note D.
    Puis on cherche le PGCD de D avec le 3ièm entier.

    Déterminer ${\rm PGCD}(12;28;10)$:
    ${\rm PGCD}(12;28)={\rm PGCD}(4\times 3;4\times 7)=4\times {\rm PGCD}(3;7)=4$
    Car ${\rm PGCD}(3;7)=1$


    Puis on cherche ${\rm PGCD}(4;10)={\rm PGCD}(2\times 2;2\times 5)=2\times {\rm PGCD}(2;5)=2$
    Car ${\rm PGCD}(2;5)=1$


    Donc ${\rm PGCD}(12;28;10)={\rm PGCD}(4;10)=2$
  • 5 méthodes pour déterminer un PGCD
    Méthode 1: Faire la liste des diviseurs
    PGCD(15;20)
    1) Trouver tous les diviseurs de 15.
    2) Trouver tous les diviseurs de 20.
    3) Trouver les diviseurs communs à 15 et 20.
    4) Parmi ces diviseurs communs, trouver le plus grand. C'est le PGCD(15;20)


    Méthode 2: Algorithme d'Euclide
    Voir explication plus haut


    Méthode 3: Factoriser $a$ et $b$
    1) Factoriser en cherchant des facteurs communs à $a$ et $b$.
    2) Utiliser la propriété ${\rm PGCD}(k\times a;k \times b)=k\times {\rm PGCD}(a;b)$

    ${\rm PGCD}(15;20)={\rm PGCD}(3\times 5;4\times 5)=5\times {\rm PGCD}(3;4)=5$
    ${\rm PGCD}(3;4)=1$



    Méthode 4: Facteurs premiers
    ${\rm PGCD}(28224;3024)$
    $28224=2^6\times 3^2 \times 7^2$
    $75600=2^4\times 3^3\times 7\times 5^2$

    ${\rm PGCD}(28224;3024)=2^4\times 3^2\times 7$
    On garde les facteurs premiers communs
    avec un exposant égal au plus petit des 2 exposants.

    S'il n'y a pas de facteur premier commun,
    les nombres sont premiers entre eux.



    Méthode 5: Chercher une combinaison de $a$ et $b$ la plus simple possible
    ${\rm PGCD}(4n+1;5n+3)$

    $5(4n+1)-4(5n+3)=-7$
    Donc ${\rm PGCD}(4n+1;5n+3)$ divise 7
    Ce qui limite beaucoup la recherche du PGCD!
    Penser à utiliser cette technique
    quand les nombres dépendent d'un entier $n$
    comme avec ${\rm PGCD}(4n+1;5n+3)$


Ce qu'il faut savoir sur le PGCD - Résumé du cours + Méthodes: Cours de math en vidéo



Corrigé en vidéo
Exercices 1:

PGCD avec décomposition en facteurs premiers - Arithmétique - Spé Maths


Déterminer le $\rm PGCD$ de $4480$ et $400$ à l'aide de la décomposition en facteurs premiers.

Corrigé en vidéo
Exercices 2:

PGCD avec l'algorithme d'Euclide - Arithmétique - Spé Maths


Déterminer le $\rm PGCD$ de $3045$ et $300$ à l'aide de l'algorithme d'Euclide.

Exercices 3:

Diviseurs communs à 2 nombres - PGCD - Arithmétique - Spé Maths


Déterminer les diviseurs communs à 168 et 204.

Exercices 4:

Diviseurs communs à 2 nombres - PGCD - Arithmétique - Spé Maths


Soit deux entiers naturels non nuls $m$ et $n$ tels que $m+n$ soit un nombre premier.
Montrer que $m$ et $n$ sont premiers entre eux.

Corrigé en vidéo
Exercices 5:

PGCD en fonction de n - Arithmétique - Spé Maths


Déterminer en fonction de l'entier naturel n, le PGCD de 5n+1 et 2n-1.
Exercices 6:

PGCD et fraction irréductible - Arithmétique - Spé Maths


Déterminer l'ensemble des entiers naturels $n$ tels que la fraction $\displaystyle \frac{3n+2}{n+2}$ soit irréductible.
Exercices 7:

PGCD avec un paramètre - 2 méthodes - Lemme d'Euclide - Arithmétique - Spé Maths


Soit $n$ un entier naturel.
Déterminer le PGCD de $9n + 4$ et de $2n + 1$ par 2 méthodes.
Exercices 8:

PGCD avec un paramètre - 2 méthodes - Lemme d'Euclide - Arithmétique - Spé Maths


Déterminer en fonction de l'entier naturel $n$ le PGCD de $n + 4$ et de $3n + 7$ par 2 méthodes.
Corrigé en vidéo
Exercices 9:

Savoir utiliser la propriété caractéristique du PGCD - Arithmétique - Spé Maths


Trouver les entiers naturels $a$ et $b$ avec $a \lt b$ tels que : $ab = 7776$ et $\text{PGCD}(a~;~b) = 18$
 
Exercices 10:

Savoir utiliser la propriété caractéristique du PGCD - Arithmétique - Spé Maths


Trouver les entiers naturels $a$ et $b$ tels que : $ab-b^2 = 2028$ et $\text{PGCD}(a~;~b) = 13$
 
Exercices 11:

Savoir utiliser le lemme d'Euclide - Arithmétique - Spé Maths


1) Déterminer l'ensemble des entiers naturels $n$ tels que $\text{PGCD}(2n + 3; n) = 3$.
2) En déduire l'ensemble des entiers naturels $n$ tels que $\text{PGCD}(2n + 3; n) = 1$.
Exercices 12:

Savoir utiliser le lemme d'Euclide - Arithmétique - Spé Maths


Déterminer pour tout entier naturel $n$, $\text{PGCD}(9n + 4; 2n + 1)$.

Corrigé en vidéo
Exercices 13:

PGCD et diviseurs communs - Arithmétique - Spé Maths


Si on divise $4294$ et $3521$ par un même entier naturel non nul $n$, les restes respectifs sont $10$ et $11$.
Quel est cet entier?
Corrigé en vidéo
Exercices 14:

PGCD pour partager un pavé en cube


Une boîte parallélépipédique rectangle de dimensions intérieures $31,2$ cm, $13$ cm et $7,8$ cm
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 ?
Corrigé en vidéo
Exercices 15:

PGCD et PPCM à partir de la décomposition en facteurs premiers


On pose $a = 588$ et $b = 616$.
1) Décomposer $a$ et $b$ en produits de facteurs premiers.
2) En déduire PGCD$(a~;~b)$.
3) Déduire également de la première question PPCM$(a~;~b)$
     (c'est à dire le plus petit multiple commun à $a$ et à $b$).
Corrigé en vidéo
Exercices 16:

PGCD et suite - arithmétique - spé maths


Soit $(u_n)$ la suite définie pour tout entier naturel $n$ par $u_0 =0$ et $u_{n+1} = 4u_n+1$.
1) a. Calculer $u_1$, $u_2$ et $u_3$.
b. Montrer que pour tout entier naturel $n$, $u_{n+1}$ et $u_n$ sont premiers entre eux.
2) On pose pour tout entier naturel $n$, $v_n = u_n + \dfrac{1}{3}$.
a) Montrer que $(v_n)$ est une suite géométrique.
b) En déduire l'expression de $v_n$ puis celle de $u_n$ en fonction de $n$.
3) Calculer PGCD($4^{n+1}-1~;~4^n-1$).
Exercices 17:

PGCD et suite - arithmétique - spé maths


Soit $(u_n)$ la suite définie pour tout entier naturel $n$ par $u_0 =14$ et $u_{n+1} = 5u_n+6$.
  1. Calculer les premiers termes de la suite.
    Que peut-on conjecturer pour le PGCD de $u_n$ et $u_{n+1}$ ?
  2. Démontrer par récurrence que pour tout entier naturel $n$, $u_n$ est divisible par 2 mais pas par 3.
  3. Démontrer la conjecture faite à la première question.
Corrigé en vidéo
Exercices 18:

Nombres de Fermat et infinitude des nombres premiers - arithmétique - spé maths


On rappelle que les nombres de Fermat sont les entiers ${\rm F}_n = 2^{2^n}+1$ avec $n$ un entier naturel.
1) Etablir que pour tous entiers naturels $n$ et $k$, on a : ${\rm F}_{n+k} - 1 = ({\rm F}_n -1)^{2^k}$.
2) En déduire que si $k$ est un entier naturel non nul alors pour tout entier naturel $n$, on a : ${\rm F}_{n+k} \equiv 2 [{\rm F}_n]$
3) En déduire que deux nombres de Fermat distincts sont premiers entre eux.
4) Retrouver alors qu'il existe une infinité de nombres premiers.
Corrigé en vidéo
Exercices 19:

PGCD : l'algorithme d'Euclide - Arithmétique - Spé Maths


Soient $a$ et $b$ deux entiers naturels, on note $\mathscr{D}(a~;~b)$ l'ensemble des diviseurs communs à $a$ et $b$.
Dans la suite, on considère que $a \geqslant b >0$.
1. a) Montrer que $\mathscr{D}(a~;~b) = \mathscr{D}(a-b~;~b)$.
b) En déduire que $\text{PGCD}(a~;~b) = \text{PGCD}(a-b~;~b)$.
2. Soit $r$ le reste dans la division euclidienne de $a$ par $b$, montrer,
en vous aidant de la question précédente, que $\text{PGCD}(a~;~b) = \text{PGCD}(r~;~b)$.
3. En vous aidant des divisions euclidiennes ci-dessous, déterminer : $\text{PGCD}(416~;~182)$.
$416 = 2 \times 182 +52$
$182 = 3 \times 52 + 26$
$52 = 2 \times 26 + 0$
4. Ecrire en langage naturel un algorithme permettant de déterminer le PGCD de $a$ et $b$.
Corrigé en vidéo
Exercices 20:

Démontrer PGCD(a;b)=PGCD(b;r) - Propriété très importante - Arithmétique - Spé Maths


Soient $a$ et $b$ deux entiers tels que 0 < $b\leqslant a$.
Démontrer que ${\rm PGCD}(a;b)={\rm PGCD} (b;r)$ où $r$ est le reste dans la division euclidienne de $a$ par $b$.
Corrigé en vidéo
Exercices 21:

PGCD égal à la différence - Arithmétique - Spé Maths


Soient $a$ et $b$ deux entiers naturels avec $a >b > 0$. Montrer que:
$\text{PGCD}(a~;~b) = a -b$ si et seulement si, il existe un entier $k$ tel que $a = (k+1)(a - b) $ et $b = k(a - b) $.

PGCD arithmétique - Spé Maths - Terminale S : Exercices à Imprimer

Ce site vous a été utile? Ce site vous a été utile
alors dites-le !


Merci à vous.
Contact

N'hesitez pas à envoyer un mail à:
jaicompris.com@gmail.com

Liens
Qui sommes-nous? Nicolas Halpern-Herla
Agrégé de Mathématiques
Professeur en S, ES, STI et STMG depuis 28 ans
Créateur de jeux de stratégie: Agora et Chifoumi

Stephane Chenevière
Agrégé de Mathématiques
Professeur en S, ES et STMG depuis 19 ans
Champion de France de magie en 2001: Magie