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


Continuer sur

Continuer sur

Ce sera prêt pour 2018

Ce sera prêt pour 2017

Terminale S

PGCD - Spé Maths


PGCD de 2 entiers ou plus

  • 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.
  • 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é.


  • 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.
  • 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\]

  • 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}(6;7)=4$
    Car ${\rm PGCD}(6;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)$





Corrigé en vidéo
Exercices 1:

PGCD avec un paramètre - Arithmétique - Spé Maths


Pour tout entier naturel non nul, on pose $a = 5n + 1$ et $b=2n - 1$. On note $\Delta =$ PGCD$(a~;~b)$.
1) Démontrer que les valeurs possibles de $\Delta$ sont 1 ou 7.
2) Déterminer les entiers $n$ tels que $a \equiv 0 \, [7]$ et $b \equiv 0 \, [7]$.
3) En déduire, suivant les valeurs de $n$, la valeur de $\Delta$.
Corrigé en vidéo
Exercices 2:

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 3:

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$
 
Corrigé en vidéo
Exercices 4:

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 5:

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) $.
Corrigé en vidéo
Exercices 6:

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 7:

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 8:

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

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 Herla
Agrégé de Mathématiques
Professeur en S, ES et STI depuis 21 ans
Créateur de jeux de stratégie: Agora et Chifoumi

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