Division euclidienne.

PPCM-PGCD.

1. Division euclidienne dans ℕ .......................... p2 5. Nombres premiers entre eux............................ p16

2. Systèmes de numération.................................. P3 6. Plus petit commun multiple.............................. p18
3. Algorithme d'Euclide....................................... p5 7. Utilisation d'un logiciel.................................... p21
4. Plus grand commun diviseur............................ p8

Copyright  meilleurenmaths.com. Tous droits réservés

 Division euclidienne. PPCM. PGCD

1. Division euclidienne dans ℕ

1.1. Définition

Soit a un entier naturel et b un entier naturel non nul alors il existe un unique couple
(q ; r ) d'entiers naturels vérifiant: a=bq+r avec 0⩽r <b
q est le quotient et r est le reste de la division euclidienne de a par b

1.2. Exemple

Si a=31 et b=5 alors q=6 et r =1

31=6×5+1

1.3. Propriétés

a ∈ℕ b∈ℕ *
b divise a ⇔ (le reste de la division euclidienne de a par b est nul)
Si q est le quotient de la division euclidienne de a par b alors: bq⩽a<b (q+1)

1.4. Utilisation d'un tableur

Avec le tableur d'openoffice.

Taper:
En A1:a En B1=b En C1: quotient En D1: reste

Taper:
En A2:31 En B2 :5
On va programmer le tableur pour qu'il calcule le quotient et le reste de la division euclidienne de 31 par 5.
En C2, on saisit: «=quotient(A2;B2) », on tape sur entrée
En D2, on saisit: «=mod(A2;B2) », on tape sur entrée

Copyright  meilleurenmaths.com. Tous droits réservés Page 2

 Division euclidienne. PPCM. PGCD
On obtient:

On peut effectuer d'autres divisions euclidiennes en donnant de nouvelles valeurs à a et b et en étirant les deux
formules.
Exemple:

2. Systèmes de numération

2.1. Introduction

Soit le nombre a que l'on représente dans le système décimal par 8 239.
Ceci veut dire:
a=8×103+2×102 +3×101 +9×10 0
9 est le chiffre des unités
3 est le chiffre des dizaines
2 est le chiffre des centaines
8 est le chiffre des milliers

On représente tous les entiers naturels en utilisant 10 chiffres: 0; 1; 2; 3; 4; 5; 6; 7; 8; 9

Si m; c; d; u sont des chiffres et m≠0, note mcdu= m×10 3+c×10 2+d ×101+u×10 0

2.2. Base quelconque

b∈ℕ b⩾2
La numération en base b nécessite l'emploi de b symboles.
Si b⩽10, on utilise les symboles (chiffres) du système décimal, si b>10 on doit faire intervenir d'autres
symboles.

Copyright  meilleurenmaths.com. Tous droits réservés Page 3

 Division euclidienne. PPCM. PGCD
Exemples:
en base2: les symboles sont: 0; 1
en base 6: les symboles sont: 0; 1; 2; 3; 4; 5
en base 12: les symboles sont: 0; 1; 2; 3; 4; 5; 6; 7; 8; 9; ; 
Le nombre noté mcdu en base b est égal à a=m×b3+c×b 2+d ×b1+u×b0

Exemples:
a s'écrit 2035 en base 6.
3 2 1 0
a=2×6 +0×6 +3×6 +5×6
a=2×216+3×6+5×1
a=432+18+5
a=455

a s'écrit 10 011 011 en base 2.

a=1×27+0×26+0×2 5+1×24+1×23+0×22+1×21+1×2 0
α =1×128+1×16+1×8+1×2+1×1
a=128+16+8+2+1
a=155

a s'écrit 85 α 2β en base 12.

a=8×124+5×123+α×122 +2×121+β×120
a=8×20736+5×1728+10×144+2×12+11×1
a=165888+8640+1440+24+11
a=176003

Le nombre a s'écrit 1461 en base 10. L'écrire en base 6.

Pour cela, il suffit d'effectuer une suite de division euclidienne dont le diviseur est 6.

1 4 6 1 6 2 4 3 6 4 0 6 6 6 1 6
2 6 2 4 3 0 3 4 0 4 6 0 1 1 0
2 1 3
3

On continue les divisions jusque l'obtention d'un quotient égal à zéro (et non d'un reste nul)
On obtient a=1×64+0×6 3+4×6 2+3×6 1+3×6 0
Donc a=10433 en base 6

Copyright  meilleurenmaths.com. Tous droits réservés Page 4

 Division euclidienne. PPCM. PGCD
2.3. Utilisation d'un logiciel

Avec le tableur d'openoffice.

Taper:
En A1: a en base 10 En B1: base En D1: chiffres dans la base

En A2: 1461 En B2: 6 En C2: « =quotient(A2;B2) » En D2: « =mod(A2;B2) »

En A3: « =C2 » En B3: « =$B2 » En C3: « =quotient(A3;B3) » En D3: « =mod(A3:B3) »

Puis on étire la ligne jusqu'à obtention d'un quotient égal à 0.

3. Algorithme d'Euclide

a ∈ℕ* b∈ℕ*
On se propose de déterminer l'ensemble des diviseurs communs de a et b.

Copyright  meilleurenmaths.com. Tous droits réservés Page 5

 Division euclidienne. PPCM. PGCD
3.1. Activités

a) 1er exemple
a=252 et b=18
On effectue la division euclidienne de a par b
252=14×18
donc 18 est un diviseur de 252
Tout diviseur de 18 est un diviseur de 252
Conclusion: tous les diviseurs communs de 252 et 18 sont les diviseurs de 18

b) 2ième exemple
a=963 et b=153
On effectue la division euclidienne de a par b
963=153×6+45 0⩽45<153
Soit d un diviseur commun de 963 et 153 alors d divise 153 et 963−153×6=45
De même si d divise 153 et 45 alors d divise 153 et 153×6+45=963 donc d est un diviseur commun de 963 et
153
Conclusion: L'ensemble des diviseurs communs de 963 et 153 est l'ensemble des diviseurs communs de 153 et
45.

3.2. Théorème

a et b sont deux entiers naturels non nuls. On note r le reste de la division euclidienne
de a par b.
Si r=0 alors a=bq
L'ensemble des diviseurs communs de a et b est l'ensemble des diviseurs de b.
Si r0 alors a=bq+r 0<r<b
L'ensemble des diviseurs communs de a et b est l'ensemble des diviseurs
communs de b et r.

3.3. Activité

a=963 b=153

963=6×153+45 0<45<153
L'ensemble des diviseurs communs de 963 et 153 est l'ensemble des diviseurs communs de 153 et 45.

Copyright  meilleurenmaths.com. Tous droits réservés Page 6

 Division euclidienne. PPCM. PGCD
153=3×45+18 0<18<45
L'ensemble des diviseurs communs de 963 et 153 est l'ensemble des diviseurs communs de 45 et 18.

45=18×2+9 0<9<18
L'ensemble des diviseurs communs de 963 et 153 est l'ensemble des diviseurs communs de 18 et 9.

18=9×2+0
L'ensemble des diviseurs communs de 963 et 153 est l'ensemble des diviseurs communs de 9.

On effectue donc des divisions euclidiennes successives, le suite des restes est strictement décroissante. Le
nombre important est le dernier reste non nul, ici 9.

On peut aussi utiliser un tableur:

Avec le tableur d'openoffice.
Taper:
En A1: 963 En B1: 153 En C1: « =quotient(A1;B1) » En D1: « =mod(A1;B1)

En A2: « =B1 » En B2: « =D1 »

Puis on étire les différentes formules

Copyright  meilleurenmaths.com. Tous droits réservés Page 7

 Division euclidienne. PPCM. PGCD
2.4. Algorithme d'Euclide

a et b étant 2 entiers naturels non nuls.

On note r 1 et q 1 les reste et quotient de la division euclidienne de a par b.
a=bq 1+r 1 0⩽r 1<b

Si r 1=0 alors l'ensemble des diviseurs communs de a et b est l'ensemble des diviseurs de b.

Si r 1≠0 , on note r 2 et q 2 les reste et quotient de la division euclidienne de b par r 1 .

b=r 1 q 2+r 2 0⩽r 2<r 1

Si r 2=0 alors l'ensemble des diviseurs communs de b et r 1 est l'ensemble des diviseurs de r 1 .

Si r 2≠0 , on note r 3 et q 3 les reste et quotient de la division euclidienne de r 1 par r 2 .

r 1=r 2 q3+r 3 0⩽r 3 <r 2

On réitère le procédé, …
La suite des restes est strictement décroissante donc il existe n∈ℕ , n⩾2 tel que r n=0
Donc, r n−2=r n−1×qn +0

Conclusion:
L'ensemble des diviseurs communs de a et b est l'ensemble des diviseurs de r n−1 (dernier reste non nul)

4. Plus grand commun diviseur

4.1. Remarque

Si a=bq alors le plus grand diviseur commun de a et b est b.

Exemple:
252=18×14
D 18=1 ;2 ;3 ;6 ;9 ;18
Le plus grand diviseur commun de 252 et 18 est 18.

Si r n−1≠0 et r n=0
Le plus grand diviseur commun de a et b est r n−1 .
Exemple:
a=963 et b=153
r 3=9 et r 4=0

Copyright  meilleurenmaths.com. Tous droits réservés Page 8

 Division euclidienne. PPCM. PGCD
Le plus grand diviseur commun de 963 et 153 est 9.

4.2. Notation

On note pgcd(a;b) ou (a ∧b) le plus grand diviseur commun de a et b.

4.3. Conséquence

L'ensemble des diviseurs communs de a et b est l'ensemble des diviseurs de

pgcd(a;b).

4.4. Propriété 1

a et b étant 2 entiers naturels non nuls.

pgcd(a;b)=pgcd(b;a) ou a ∧b=b∧a

Exemple:
a=963 et b=153 pgcd(a;b)=9
pgcd(b;a)?
153=0×963+153 0⩽153<963

4.5. Propriété 2

a, b et k étant 3 entiers naturels non nuls.

pgcd(ka;kb)=kpgcd(b;a)

Exemple:
a=963 et b=153 pgcd(a;b)=9
k=5
5a=4815 5b=765
4815=6×765+225
765=3×225+90
225=2×90+45
90=2×45+0
pgcd(4815;765) =45=5×9

Copyright  meilleurenmaths.com. Tous droits réservés Page 9

 Division euclidienne. PPCM. PGCD
4.6. Propriété 3
* *
Si d est un diviseur commun de a et b.On note a=da' et b=db' ( a ' ∈ℕ et b ' ∈ℕ )
pgcd(a;b) =δ et pgcd(a';b') =δ '
Alors δ=d δ'
Démonstration:
pgcd(a;b)=pgcd(da';db')=d pgcd(a';b')
a ∧b=(da ' )∧( db' )=d (a ' ∧b ')

4.7. Activité

a=963 b=153 pgcd(a;b)=9

On veut écrire 9 comme combinaison linéaire de a et b c'est à dire on veut trouver 2 entiers relatifs u et v tels
que: ua+vb=9

963=6×153+45 a=6×b+45
On exprime le reste en fonction de a et b
45=a−6 b

153=3×45+18 b=3×(a−6 b)+18

18=−3 a+19 b

45=2×18+9 a−6 b=2×(−3 a+19 b)+9

Donc
9=7 a−44 b
Attention cette écriture n'est pas unique.

4.8. Théorème

Pour tous entiers naturels non nuls a et b il existe 2 entiers relatifs u et v tels que:
au+bv=pgcd(a;b)
Démonstration:
Si b divise a
a=bq et pgcd(a;b)=b
On peut écrire 0 a+1 b=b
(u=0 et v=1)

Si b ne divise pas a, on considère l'algorithme d'Euclide:

a=bq 1+r 1
Donc, r 1=a−bq 1

Copyright  meilleurenmaths.com. Tous droits réservés Page 10

 Division euclidienne. PPCM. PGCD
b=r 1 q 2+r 2
b=( a−bq1 ) q2+r 2
b=aq 2−bq1 q 2+r 2
Donc, r 2=−aq 2+(1+q 1 q 2 )b

r 1=r 2 q3+r 3
r 1=(−aq 2+(1+q 1 q2 )b) q 3+r 3
a−bq 1=(−aq2+(1+q1 q 2)b)q3+r 3
a−bq 1=−aq 2 q3+(1+q1 q2 ) bq3+r 3
a−bq 1=−aq 2 q3+bq 3+q 1 q2 bq3 +r 3
Donc, r 3=a−bq 1+aq 2 q3−bq3−q1 q 2 bq 3
r 3=(1+q 2 q3) a−(q 1+q 3+q 1 q2 q 3) b

On réitère un nombre fini de fois ce procédé, et on trouve 2 entiers relatifs u et v tels que: au+bv=pgcd(a;b)

4.9. Exercices

Pour les exemples suivants, calculer pgcd(a;b) et déterminer des entiers relatifs u et v tels que
au+bv=pgcd(a;b)

a) a=11222 b=279
a b Quotient reste
11222 279 40 62
279 62 4 31
62 31 2 0

pgcd(a;b)=31

a=40 b+62
Donc, 62=a−40 b

b=4×62+31
b=4(a−40 b)+31
b=4 a−160 b+31
Donc, 31=−4 a+161 b
u=-4 et v=161

On peut utiliser un tableur:

Copyright  meilleurenmaths.com. Tous droits réservés Page 11

 Division euclidienne. PPCM. PGCD
En A1: a En B1: b En C1: quotient En D1: reste En E1: u En F1: v
En G1: au+bv

En A2: 11222 En B2: 279 En C2: «=quotient(A2;B2) » En D2: «=mod(A2;B2) »

En E2: « =1 » En F2: « =-C2 » En G2: « =A$2*E2+B$2*F2 »
car:
a=bq 1+r 1
r 1=a−bq 1
Donc, u=1 et v=−q1
r 1=E 2×a+F 2×b

En A3: « =B2 » En B3: « =D2 »

Pour C3 et D3, on étire les formules C2 et D2
En E3: « =-E2*C3 » En F3: « =1-F2*C3 »
car:
b=r 1 q 2+r 2
b=( E 2×a+F 2×b)×C 3+r 2
donc:
r 2=(−E 2×C 3)×a+(1−F 2×C 3)×b
r 2=E 3×a+F 3×b
Pour G3, on étire la formule de G2.

Copyright  meilleurenmaths.com. Tous droits réservés Page 12

 Division euclidienne. PPCM. PGCD
Pour E4; B4; C4; Da, on étire les formules des cellules A3; B3; C3 et D3.
En E4: « =E2-E3∗C4 » En F4: « F2-F3∗C4 »
car:
r 1=r 2 q3+r 3
E 2×a+F 2×b=( E 3×a+F 3×b)×C 4+r 3
r 3=( E 2−E 3×C 4)×a+( F 2−F 3×C 4)×b
Pour G4, on étire la formule de G3.
On continue autant que nécessaire, on arrête lorsque l'on obtient 0 dans la colonne reste.

On retrouve pgcd(a;b)=31=-4a+161b

b) a=6157 b=1645
a b Quotient reste
6157 1645 3 1222
1645 1222 1 423
1222 423 2 376
423 376 1 47
376 47 8 0
pgcd(a;b)=47

a=3 b+1222
Donc, 1222=a−3 b

b=1×1222+423
b=1(a−3 b)+423
b=a−3 b+423
Donc, 423=−a+4 b

1222=2×423+376
a−3 b=2(−a+4 b)+376
a−3 b=−2 a+8 b+376
Donc, 376=3 a−11b

Copyright  meilleurenmaths.com. Tous droits réservés Page 13

 Division euclidienne. PPCM. PGCD
423=1×376+47
−a+4 b=1(3 a−11 b)+47
−a+4 b=3 a−11 b+47
Donc, 47=−4 a+15 b
u=−4 et v=15

On peut aussi utiliser le tableur:

c) a=1027 b=181
a b Quotient reste
1027 181 5 122
181 122 1 59
122 59 2 4
59 4 14 3
4 3 1 1
1 1 1 0

pgcd(a;b)=1

a=5 b+122
Donc, 122=a−5 b

b=1×122+59
b=1(a−5 b)+59
b=a−5 b+59
Donc, 59=−a+6b

122=2×59+4
a−5 b=2(−a+6 b)+4
a−5 b=−2 a+12 b+4
Donc, 4=3 a−17 b

Copyright  meilleurenmaths.com. Tous droits réservés Page 14

 Division euclidienne. PPCM. PGCD
59=14×4+3
−a+6 b=14(3 a−17 b)+3
−a+6 b=42 a−238 b+3
Donc, 3=−43 a+244 b

4=1×3+1
3 a−17 b=1(−43 a+244 b)+1
3 a−17 b=−43 a+244 b+1
Donc, 1=46 a−261 b
u=46 et v=−261

On peut aussi utiliser le tableur:

4.10. Plus grand diviseur commun de n nombres

a , b , c Sont 3 entiers non nuls.

pgcd(a;b) =δ 1 pgcd(a;c) =δ 2 pgcd(b;c) =δ 3
Alors, pgcd(a;b;c)=pgcd( δ1 ;c)=pgcd( δ2 ;b)=pgcd( δ3 ;a)

Si n∈ℕ , n⩾2 .
On peut définir par récurrence le pgcd de n entiers naturels non nuls.
Si pgcd (a 1 ; a 2 ;… ; an )=δ n
Alors, pgcd (a 1 ; a 2 ;… ; an ; a n+1)= pgcd (δn ; a n +1 )=δ n+1

4.11. Remarque

Après avoir décomposé les deux entiers naturels non nuls a et b en produit de facteurs premiers, pour calculer le
pgcd de a et b, on effectue le produit des facteurs premiers communs à a et b, chacun étant affecté de son plus
petit exposant.

Copyright  meilleurenmaths.com. Tous droits réservés Page 15

 Division euclidienne. PPCM. PGCD
Exemple:
a=5282200 b=5505500
a=23×52 ×74×11 b=22 ×53×7×112×13

pgcd(a;b)= 2 2×52×7×11=7700

5. Nombres premiers entre eux

5.1. Définitions

Deux entiers naturels non nuls a et b sont premiers entre eux si et seulement si leur
pgcd est égal à 1.

Des entiers naturels non nuls a 1 ; a 2 ;… ;a n sont premiers entre eux dans leur
ensemble si et seulement si leur pgcd est égal à 1.

5.2. Théorème

Les quotients de deux entiers naturels non nuls par leur pgcd sont deux nombres
premiers entre eux.
Démonstration:
a et b sont deux entiers naturels non nuls.
pgcd (a ;b)=δ
a=δ a ' b=δ b '
pgcd (a ;b)=δ =pgcd (δ a ' ;δ b ' )=δ pgcd (a ' ; b ' )
Donc pgcd (a ' ;b ' )=1
Donc, a ' et b ' sont donc premiers entre eux.

5.3. Théorème de Bezout

Deux entiers naturels non nuls a et b sont premiers entre eux si et seulement si il
existe des entiers relatifs u et v vérifiant au+bv=1.
Démonstration:
On suppose que pgcd (a ;b)=1
Or, il existe des entiers relatifs u et v tels que au+bv =pgcd (a ;b)=1
On suppose qu'il existe des entiers relatifs u et v tels que au+bv=1
Soit d un diviseur commun de a et b. Il faut montrer que d =1 .
d divise a et b donc donc d divise au+bv.
C'est à dire d divise 1 donc d =1 .

Copyright  meilleurenmaths.com. Tous droits réservés Page 16

 Division euclidienne. PPCM. PGCD
5.4. Théorème de Gauss

a; b et c sont trois entiers naturels non nuls.

Si a divise le produit bc et si a est premier avec b alors a divise c.
C'est à dire:
Si a divise bc
Si pgcd(a;b)=1
Alors a divise c.

Démonstration:
a et b sont premiers entre eux. D'après le théorème de Bezout, il existe deux entiers relatifs u et v tels que
au+bv=1
On multiplie par c les deux membres de cette égalité. On obtient:
acu+bcv =c
a divise ac et a divise bc alors a divise acu+bcv
Donc a divise c

5.5. Conséquences

a 1 ; a 2 ;b sont des entiers naturels non nuls. Si a 1 ; a 2 divisent b et si a 1 ; a 2 sont premiers

entre eux alors a 1×a 2 divise b
C'est à dire:
Si a1 divise b
Si a2 divise b
Si pgcd (a 1 ; a 2)=1
Alors a 1×a 2 divise b.
Démonstration:
a 1 divise b donc il existe q∈ℕ * tel que a 1 q=b
Comme a 2 divise b , a 2 divise a 1 q .
pgcd (a 1 ; a 2)=1
Donc, d'après le théorème de Gauss: a 2 divise q.
Il existe q ' ∈ℕ* tel que a 2 q '=q
Ainsi, b=a 1 a2 q '
Donc, a 1×a 2 divise b.

Copyright  meilleurenmaths.com. Tous droits réservés Page 17

 Division euclidienne. PPCM. PGCD

n∈ℕ , n⩾2 . a ; b1 ; b2 ; … ;bn et c sont des entiers naturels non nuls.

Si a divise b1 b2 … bn c
Si pgcd (a ;b1 )=1
Si pgcd (a ;b2 )=1
…
Si pgcd (a ;bn )=1
Alors a divise c.
Pour démontrer ce résultat, on peut effectuer un raisonnement par récurrence.

a ; b ; n et m sont des entiers naturels non nuls.

Si pgcd(a;b)=1
Alors pgcd (a n ;b m)=1

6. Plus petit commun multiple

6.1. Exemple

On considère les multiples entiers naturels non nuls de 9 et 12.

M 9={9 k , k ∈ℕ}={9 ;18; 27 ;36 ;45 ;54 ;63; 72;81 ;90 ;99 ;108 ;117;… }
M 12={12 k , k ∈ℕ}={ 12; 24 ; 36 ; 48 ; 60 ; 72 ; 84 ; 96 ; 108;120 ;… }
L'ensemble des multiples communs non nuls de 9 et 12 est:
M 9∩M 12={36 ; 72;108 ;… }
36 est le plus petit multiple commun non nul de 9 et 12.
Remarque:
108=9×12

6.2. Définition

a et b sont des entiers naturels non nuls. M a ∩M b contient ab donc admet un plus petit élément m .

Le plus petit élément de M a ∩M b se nomme le plus petit multiple commun de a et b

et se note ppcm(a;b) ou a ∨b .

6.3. Remarque

L'ensemble des multiples communs des deux entiers naturels non nuls a et b est
l'ensemble des multiples de leur ppcm

Copyright  meilleurenmaths.com. Tous droits réservés Page 18

 Division euclidienne. PPCM. PGCD
6.4. Propriété

ppcm(a ;b)=ppcm(b ;a)

6.5. ppcm de deux nombres premiers entre eux

a ; b sont des entiers naturels non nuls.

Si pgcd(a ;b)=1 alors ppcm(a ;b)=ab

Démonstration:
Soit m un multiple commun de a et b.
m=qa=q ' b avec q∈ℕ * et q ' ∈ℕ* .
a divise qa donc a divise q'b

a divise q'b
pgcd(a ;b)=1
Donc, d'après le théorème de Gauss: a divise q'
Donc il existe k ∈ℕ* tel que q ' =ka

Donc m=q ' b=kab⩾ab

Par suite,
ppcm(a ;b)=ab

6.6. ppcm de deux entiers naturels non nuls

a ; b sont deux entiers naturels non nuls.

Si pgcd (a ;b)=δ alors ppcm (a ;b)=δ a ' b ' avec a=δ a ' et b=δ b ' .
Démonstration:
pgcd (a ' ;b ' )=1
δ a ' b '=ab ' =ba '
Donc δ a ' b ' est un multiple commun de a et b.

Soit m un multiple commun de a et b

m=qa=q ' b avec q∈ℕ * et q ' ∈ℕ* .
m=q δ a ' =q ' δ b '
Donc qa '=q ' b '

a ' divise q ' b '

Copyright  meilleurenmaths.com. Tous droits réservés Page 19

 Division euclidienne. PPCM. PGCD
pgcd(a' ;b')=1
Donc, d'après le théorème de Gauss
a' divise q'
Il existe k ∈ℕ* tel que q ' =a ' k

Donc: qa '=q ' b '=ka ' b '

m=q δ a ' =δ k a ' b ' ≥δ a ' b '
Donc, ppcm (a ;b)=δ a ' b '

6.7. Relation entre le ppcm et le pgcd de deux entiers naturels non nuls

Si a et b sont deux entiers naturels non nuls.

alors pgcd(a ;b) × ppcm(a ;b)=ab
Démonstration:
pgcd (a ;b)=δ
ppcm (a ;b)=δ a ' b ' avec a=δ a ' et b=δ b '
Donc:
pgcd(a ;b) × ppcm(a ;b)= δ×δ a ' b' =(δ a ')( δ b ')=ab

6.8. Conséquence

Si a; b et k sont des entiers naturels non nuls

alors ppcm(ka ;kb)=kppcm(a ;b)
Démonstration:
pgcd(ka ;kb) × ppcm(ka;kb)=(ka) × (kb)
kpgcd(a ;b) × ppcm(ka;kb)=k²ab
pgcd(a ;b) × ppcm(ka;kb)=kab

Or pgcd(a ;b) × ppcm(a ;b)=ab

Donc: pgcd(a ;b) × ppcm(ka;kb)=kpgcd(a ;b) × ppcm(a ;b)
Et: ppcm(ka;kb)=kppcm(a ;b)

6.9. Remarque

Après avoir décomposé les deux entiers naturels non nuls a et b en produit de facteurs
premiers, pour calculer le ppcm de a et b, on effectue le produit de tous les facteurs
premiers figurant dans a ou dans b chacun affecté de son plus grand exposant.
Exemple:
a=5282200 b=5505500
a=23×52 ×74×11 b=22 ×53×7×112×13
ppcm(a;b)= 23 ×53×74 ×112×13

Copyright  meilleurenmaths.com. Tous droits réservés Page 20

 Division euclidienne. PPCM. PGCD
7. Utilisation d'un logiciel

7.1. Géogébra

Pour la division euclidienne, on a les instructions suivantes :

quotient[a,b] et reste[a,b]
b est un entier naturel non nul et a est un entier relatif.

Exemple
a=10213 et b=57
On entre dans la barre de saisie : q=quotient[10213,57]
Le résultat s'affiche dans la partie algèbre : q=179.
On entre dans la barre de saisie : r=reste[10213,57]
Le résultat s'affiche dans la partie algèbre : r=10.

Pour le pgcd de deux entiers naturels non nuls, on a l'instruction suivante :

pgcd[a,b]

Exemple
a=10213 et b=714
On entre dans la barre de saisie : d=pgcd[10213,714]
Le résultat s'affiche dans la partie algèbre : d=7

Pour le ppcm de deux entiers naturels non nuls, on a l'instruction suivante :

ppcm[a,b]

Exemple
a=10213 et b=714
On entre dans la barre de saisie : m=ppcm[10213,714]
Le résultat s'affiche dans la partie algèbre : m=10 471 726

7.2. Xcas

Dans l'application arithmétique.

Pour la division euclidienne, on a les instructions suivantes :
iquo(a,b) pour le quotient.
irem(a,b) pour le reste.

Copyright  meilleurenmaths.com. Tous droits réservés Page 21

 Division euclidienne. PPCM. PGCD
Exemple
a=10213 et b=57
On entre dans la barre de saisie : iquo(10213,57)
Le résultat affiché est 179.
On entre dans la barre de saisie : irem(10213,57)
Le résultat affiché est 10.

Pour le pgcd de deux entiers naturels non nuls, on a l'instruction suivante :

gcd(a,b)

Exemple
a=10213 et b=714
On entre dans la barre de saisie : gcd(10213,714)
Le résultat affiché est 7.

Pour le ppcm de deux entiers naturels non nuls, on a l'instruction suivante :

lcm(a,b)

Exemple
a=10213 et b=714
On entre dans la barre de saisie : lcm(10213,714)
Le résultat affiché est 1 041 726.

Copyright  meilleurenmaths.com. Tous droits réservés Page 22