Médaille
N°1 pour apprendre & réviser du collège au lycée.
PGCD et fractions irréductibles

Déjà plus de

1 million

d'inscrits !

Avant de commencer, regarde la vidéo

Introduction :

Ce cours va introduire un nouvel outil mathématique utilisé en arithmétique. On y trouvera des définitions, des propriétés, des méthodes et des exemples.

Diviseurs d’un nombre entier

bannière propriete

Propriété

aa et bb désignent des nombres entiers positifs avec b0b \neq 0. Faire la division euclidienne de aa par bb, c’est déterminer le quotient qq et le reste rr tels que : a=b×q+ra = b \times q + r, avec :

  • qq et rr des nombres entiers positifs,
  • r<br < b (r est strictement inférieur à b).
bannière exemple

Exemple

Effectuons la division euclidienne de 159159 par 1717.

On écrit : 159=17×9+6159 = 17 \times 9 + 6 et 6<17 6 < 17. 159159 est le dividende, 1717 est le diviseur, 99 est le quotient et 66 est le reste.

bannière propriete

Propriété

aa et bb désignent des nombres entiers positifs avec b0b \neq 0.

On dit que bb est un diviseur de aa lorsque le reste de la division euclidienne de aa par bb est égal à 00. On écrit : a=b×qa = b \times q .

On dit aussi que aa est un multiple de bb.

bannière exemple

Exemple

Écrivons la liste des diviseurs de 2828.

28=1×2828 = 1 \times 28

28=2×1428 = 2 \times 14

28=4×728 = 4 \times 7

  • Les diviseurs de 2828 sont donc {1;2;4;7;14;28}\lbrace 1 ; 2 ; 4 ; 7 ; 14 ; 28 \rbrace.
bannière definition

Définition

Nombre premier :

Un nombre entier strictement plus grand que 11 qui admet exactement deux diviseurs (11 et lui-même) est appelé nombre premier.

bannière exemple

Exemple

2;3;5;7;11;13;17;192 ; 3 ; 5 ; 7 ; 11 ; 13 ; 17 ; 19 sont des nombres premiers.

1;4;6;8;9;101 ; 4 ; 6 ; 8 ; 9 ; 10 ne sont pas des nombres premiers.

PGCD de deux nombres premiers

bannière definition

Définition

Diviseur commun :

On dit qu’un nombre est un diviseur commun de deux nombres aa et  bb s’il divise à la fois aa et bb.

bannière exemple

Exemple

Établissons la liste des diviseurs communs de 2828 et 7070.

Les diviseurs de 2828 sont {1;2;4;7;14;28}\lbrace 1 ; 2 ; 4 ; 7 ; 14 ; 28 \rbrace.

Les diviseurs de 7070 sont {1;2;5;7;10;14;35;70}\lbrace 1; 2; 5; 7; 10; 14; 35; 70 \rbrace.

Les diviseurs communs de 2828 et 7070 sont donc {1;2;7;14}\lbrace 1 ; 2 ; 7 ; 14 \rbrace.

bannière propriete

Propriété

aa et bb désignent des nombres entiers strictement positifs.

Le plus grand des diviseurs commun à aa et bb s’appelle le PGCDPGCD (Plus Grand Commun Diviseur) des nombres aa et bb. Il se note PGCD(a;b)PGCD(a ; b).

bannière exemple

Exemple

Calculs des PGDC

  • Dans l’exemple précédent, dans la liste des diviseurs communs de 2828 et 7070, 1414 est le plus grand nombre. On a donc 14=PGCD(28;70)14 = PGCD(28;70).
  • Pour les nombres 1212 et 2121 :

Les diviseurs de 1212 sont {1;2;3;4;6;12}\lbrace 1 ; 2 ; 3 ; 4 ; 6 ; 12 \rbrace

Les diviseurs de 2121 sont {1;3;7;21}\lbrace 1; 3; 7; 21 \rbrace

Les diviseurs communs de 1212 et 2121 sont {1;3}\lbrace 1 ; 3 \rbrace

Donc PGCD(12;21)=3PGCD(12 ; 21) = 3.

bannière propriete

Propriété

aa et bb désignent des nombres entiers strictement positifs.

  • PGCD(a;b)=PGCD(b;a)PGCD(a;b) = PGCD(b ;a),
  • PGCD(a;a)=aPGCD( a;a)=a,
  • PGCD(a;1)=1PGCD( a;1)=1,
  • si bb est un diviseur de aa, PGCD(a;b)=bPGCD( a;b)=b.
bannière à retenir

À retenir

Deux nombres aa et bb sont premiers entre eux s’ils ont pour seul diviseur commun 11. En d’autres termes, deux nombres aa et bb sont premiers entre eux si PGCD(a;b)=1PGCD( a;b)=1.

bannière exemple

Exemple

Les nombres 1010 et 4949 sont-ils premiers entre eux ?

Les diviseurs de 1010 sont {1;2;5;10}\lbrace 1; 2; 5; 10 \rbrace.

Les diviseurs de 4949 sont {1;7;49}\lbrace 1; 7; 49 \rbrace.

Le seul diviseur commun de 1010 et 4949 est 11.

Donc PGCD(1;49)=1PGCD(1 ; 49) = 1 et ainsi, on montre que 1010 et 4949 sont premiers entre eux.

Algorithme d’Euclide

bannière astuce

Astuce

Méthode de détermination du PGCDPGCD pour des nombres relativement peu élevés :

  • lister l’ensemble des diviseurs de aa,
  • lister l’ensemble des diviseurs de bb,
  • lister l’ensemble des diviseurs communs de aa et de bb,
  • prendre le plus grand élément de cette liste et l’identifier comme PGCD(a;b)PGCD( a;b).
bannière propriete

Propriété

aa et bb désignent des nombres entiers strictement positifs avec a>ba>b.

On note rr le reste de la division euclidienne de aa par bb.

Alors :

PGCD(a;b)=PGCD(b;r)PGCD(a;b)=PGCD(b;r).

bannière exemple

Exemple

Calculons le PGCDPGCD de 10581 058 et 7676.

On effectue la division euclidienne de 10581 058 par 7676 :

1058=76×13+701 058 = 76 \times 13 + 70

d’où PGCD(1058;76)=PGCD(76;70)PGCD(1 058 ; 76) = PGCD(76 ; 70)

76=70×1+676 = 70 \times 1 + 6

d’où PGCD(76;70)=PGCD(70;6)PGCD(76 ; 70) = PGCD(70 ; 6)

70=6×11+470 = 6 \times 11 + 4

d’où PGCD(70;6)=PGCD(6;4)PGCD(70 ; 6) = PGCD(6;4)

6=4×1+26=4\times1+2

d’où PGCD(6;4)=PGCD(4;2)PGCD(6 ; 4) = PGCD(4;2)

4=2×2+04=2\times2+0

Or PGCD(4;2)=2PGCD(4;2)=2 donc PGCD(1058;76)=2PGCD(1 058; 76) = 2

Récapitulons dans le tableau suivant :

bannière à retenir

À retenir

Dans l’algorithme d’Euclide, le PGCDPGCD est le dernier reste non nul (22 dans cet exemple).

Applications du PGCD

Les fractions irréductibles

bannière definition

Définition

Fraction irréductible :

La fraction ab\dfrac{a}{b} est dite irréductible si les nombres aa et bb sont premiers entre eux.

bannière à retenir

À retenir

Une fraction est irréductible lorsque l’on ne peut plus simplifier son écriture, c’est-à-dire si son numérateur et son dénominateur n’admettent pas de diviseurs communs (à part 11).

bannière exemple

Exemple

158\dfrac{15}{8} est irréductible car 1515 et 88 n’ont en commun que 11 comme diviseur. On peut aussi dire que 1515 et 88 sont premiers entre eux.

bannière astuce

Astuce

Le PGCDPGCD est très utile pour simplifier des écritures fractionnaires : pour rendre une fraction ab\dfrac{a}{b} irréductible, il suffit de la simplifier par le PGCDPGCD de aa et bb.

bannière exemple

Exemple

Simplifions 7028\dfrac{70}{28} et 105876\dfrac{1058}{76}

  • On a vu que PGCD(28;70)=14PGCD(28;70) = 14, donc 7028=70÷1428÷14=52\dfrac{70}{28} = \dfrac{70 \div 14}{28 \div 14} = \dfrac{5}{2}, qui est une fraction irréductible.
  • On a vu que PGCD(1058;76)=2PGCD(1058;76) = 2, donc 105876=1058÷276÷2=52938\dfrac{1058}{76} = \dfrac{1058 \div 2}{76 \div 2} = \dfrac{529}{38}, qui est une fraction irrréductible.

Un problème de partage

bannière à retenir

À retenir

Dans les problèmes de partage de quantités en parts identiques, on utilise le PGCDPGCD de ces quantités pour la recherche des solutions optimales.

bannière exemple

Exemple

Dans un collège, il y a 108108 filles et 135135 garçons. On veut utiliser tous les élèves pour créer des groupes identiques (contenant chacun autant de filles que de garçons.

Le nombre de groupes possible doit nécessairement être un diviseur commun de 108108 et 135135.

Le nombre maximal de groupes possible sera le plus grand de ces diviseurs communs, c’est-à-dire PGCD(135;108)=27PGCD(135;108) = 27.

On pourra donc former au maximum 2727 groupes identiques.

De plus, il y aura 44 filles et 55 garçons dans chaque groupe.