PGCD – PPCM Théorèmes de BÉZOUT, de GAUSS et de FERMAT

I. PGCD On note d (a) l’ensemble des diviseurs de l’entier relatif a et d (a ; b) l’ensemble des diviseurs communs aux entiers relatifs a et b.

L’ensemble des diviseurs de 12 est : d (12) = {

L’ensemble des diviseurs de 18 est : d (18) = {

L’ensemble de leurs diviseurs communs est : d (12 ; 18) = {

Définition 1 Soit a et b des entiers (relatifs) non nuls.

Un diviseur commun à a et b est un entier qui divise à la fois a et b .

Le plus grand diviseur commun à a et b est noté PGCD (a ; b).

d (a ; b) = d (a) ∩ d (b)

exemples : PGCD (12 ; 18) = ; PGCD (12 ; – 18) = ; PGCD (15 ; 16) =

Propriété 1 Soit a, b et k des entiers (relatifs) non nuls.

� PGCD (a ; b) = PGCD (b ; a) = PGCD ( |a| ; |b| ). � PGCD (a ; b) ≥ 1.

� Si b ≠ 0, alors b | a si, et seulement si, PGCD (a ; b) = |b|. � PGCD (ka ; kb) = |k| PGCD (a ; b)

Dans la pratique, déterminer le PGCD des entiers a et b revient à déterminer le PGCD des entiers naturels |a| et |b|.

Lemme d’Euclide Soit a et b des entiers naturels non nuls.

Soit q et c deux entiers naturels tels que a = b q + c.

• Si c = 0 alors d (a ; b) = d (b) et PGCD (a ; b) = |b|.

• Si c ≠ 0 alors d (a ; b) = d (b ; c) et PGCD (a ; b) = PGCD (b ; c).

c n’est pas forcément le reste de la division euclidienne de a par b. On peut avoir c ≥ b.

Algorithme d'Euclide Soit a et b des entiers naturels non nuls avec a > b et tels que b ne divise pas a.

Pour déterminer PGCD (a ; b), on utilise l'algorithme d'Euclide qui découle du lemme précédent en utilisant des divisions euclidiennes successives. On remplace (a,b) par des couples de nombres de plus en plus petits qui ont le même ensemble de diviseurs communs.

opérations reste commentaire

On divise a par b. r1 0 £ r1 < b et PGCD (a ; b) = PGCD (b ; r1)

Si r1 ≠ 0, on divise b par r1. r2 0 £ r2 < r1 et PGCD (b ; r1) = PGCD (r1 ; r2)

Si r2 ≠ 0, on divise r1 par r2. r3 0 £ r3 < r2 et PGCD (r1 ; r2) = PGCD (r2 ; r3) M M

Si rn ≠ 0, on divise rn – 1 par rn. 0 PGCD (rn – 1 ; rn) = rn

Après un nombre fini de divisions, on trouve un reste nul, car les restes sont des entiers naturels positifs qui vont en décroissant strictement, si on note rn le dernier reste non nul : 0 < rn < rn – 1 < …. < r1 < b. Ci-dessus, on note rn le dernier reste non nul.

Donc PGCD (a ; b) = PGCD (b ; r1) = … = PGCD (rn – 1 ; rn) = rn

1/4

Propriété 2 Lorsque b ne divise pas a, le PGCD des entiers naturels non nuls a et b est égal au dernier reste non nul obtenu par l'algorithme d'Euclide.

Propriété 3 Les diviseurs communs à deux entiers naturels a et b, sont les diviseurs de PGCD (a ; b).

Exercice 1 Déterminer avec l’algorithme d’Euclide le PGCD de 97020 et 3150.

Exercice 2 Si on divise 4373 et 826 par un même entier naturel non nul n, on obtient respectivement 8 et 7 comme restes. Quel est ce nombre n ?

Exercice 3 Trouver tous les couples ( a ; b) d’entiers naturels non nuls tels que a + b = 112 PGCD (a ; b) = 14 .

II. NOMBRES PREMIERS ENTRE EUX

Définition 2 Soit a et b des entiers relatifs non nuls.

Dire que a et b sont premiers entre eux signifie que PGCD(a ; b) = 1.

Deux entiers premiers entre eux ont comme diviseurs communs : Exercice 4 8 et 15 sont-ils premiers entre eux ? 98 et 119 sont-ils premiers entre eux ?

Propriété 4 Soit a et b des entiers relatifs non nuls et d un diviseur commun de a et b..

PGCD (a ; b) = d si, et seulement si, il existe des entiers relatifs a’ et b’ premiers entre eux tels que a = da′ et b = db′.

III. THÉORÈME DE BÉZOUT

Théorème de Bézout Soit a et b des entiers relatifs non nuls.

a et b sont premiers entre eux si et seulement si il existe des entiers relatifs u et v tels que au + bv = 1.

8 et 15 sont premiers entre eux car 8 × 2 + 15 × (– 1) = 8 × (– 13) + 15 × 7 = 8 × 17 + 15 × (– 9) = … = 1.

Les entiers u et v ne sont pas uniques. Exercice 5 Existe-t-il des entiers u et v tels que 99 u + 56 v = 1 ? 99 u + 54 v = 1 ? 99 u + 56 v = 8 ?

Exercice 6 Démontrer que, pour tout entier naturel n, 3n + 2 et 5n + 3 sont premiers entre eux.

Exercice 7 Les entiers a et b sont premiers entre eux. Démontrer que b et a + b aussi.

Exercice 8

1) Montrer que PGCD (99 ; 56) = 1 en utilisant la méthode des divisions euclidiennes successives.

2) En déduire un couple d’entiers (u ; v) tel que 99 u + 56 v = 1.

3) Déterminer à l’aide du tableur de la calculatrice un autre couple d’entiers (u ; v) tel que 99u + 56v = 1

4) En déduire deux couples d’entiers (u ; v) tel que 99 u + 56 v0 = 10.

Corollaire Soit a et b des entiers relatifs non nuls.

Si d = PGCD (a ; b) alors il existe des entiers relatifs u et v tels que au + bv = d.

La réciproque est fausse: 2 × 3 + 4 × 5 = 26 mais 2/4

Exercice 9 1) Déterminer un couple d’entiers (u ; v) tel que 594 u + 336 v = PGCD (594 ; 336). 2) Déterminer un couple d’entiers (u ; v) tel que 258 u + 210 v = PGCD (258 ; 210).

IV. THÉORÈME DE GAUSS

Théorème de Gauss Soit a, b et c des entiers relatifs non nuls.

Si a divise bc et si a est premier avec b, alors a divise c.

Exercice 10 1) Déterminer tous les couples d’entiers (x ; y) tel que 99 x + 56 y = 0.

2) Déterminer tous les couples d’entiers (x ; y) tel que 99 x + 56 y = 10 (voir ex 9).

Définition 3 Les équations du type a x + b y = c où a, b, c sont des entiers relatifs donnés, et x, y des entiers relatifs inconnus sont des équations diophantiennes.

On dit que l’on résout dans ² (l’ensemble des couples d’entiers) l’équation (diophantienne) ax + by = c

Propriété 5 L’équation diophantienne a x + b y = c , d’inconnues x et y, admet des solutions

si, et seulement si, c est un multiple de PGCD (a ; b).

Méthode � On détermine une solution particulière (x0 ; y0) soit directement, soit à l’aide de la

calculatrice (tableur ou programme), soit à l’aide d’un tableur, soit en exploitant la détermination de PGCD (a ; b) par la méthode des divisions euclidiennes successives.

� À l’aide du théorème de Gauss on exprime x en fonction de x0 et y en fonction de y0 .

� On vérifie que les couples trouvés sont effectivement solution.

Exercice 11 Déterminer tous les entiers naturels n tels que 3n + 2 divise 11 (5n + 3). (voir ex. 7)

Corollaires Soit a, b et c des entiers relatifs et p un nombre premier.

� Si a et b sont premiers entre eux et divisent c, alors ab divise c.

� Si p divise ab, alors p divise au moins l’un des entiers a et b.

4 et 3 divisent n donc

2 et 6 divisent n donc

Exercice 12 Soit n un entier naturel. Démontrer que a = n (2 n + 1) (7 n + 1) est divisible par 6.

Exercice 13 Montrer que pour tout nombre premier p, p est premier avec (p – 1) ! V. PETIT THÉORÈME DE FERMAT

« petit » Théorème de Fermat Soit p un nombre premier et a un entier relatif.

Si p ne divise pas a, alors a p – 1 ≡ 1 [p] .

p divise a p – 1 – 1

Corollaire Pour tout nombre premier p et tout entier relatif a, a p ≡ a [p] .

Exercice 14 Démontrer que 9 12 – 1 est divisible par 13.

Exercice 15 p est un nombre premier différent de 3. Démontrer que pour tout entier naturel n, a n =3 n + p – 3 n + 1 est divisible par p.

3/4

Exercice 16 Démontrer que pour tout entier naturel n non nul, n 7 – n est divisible par 42. VI. PPCM

Définition 4 Soit a et b des entiers relatifs non nuls.

Le plus petit multiple strictement positif commun à a et b est appelé le PPCM de a et de b.

On le note PPCM (a ; b).

PPCM (9 ; 12) = et PPCM ( 10 ; – 6) =

Propriété 6 Soit a et b des entiers relatifs non nuls.

� PPCM (a ; b) = PPCM (b ; a) = PPCM ( |a| ; |b| )

� PPCM (1 ; a) = PPCM (a ; a) =

� PPCM (a ; b) = |a| si, et seulement si,

PPCM ( – 1176 ; – 540) = Pour déterminer le PPCM de deux entiers naturels a et b à partir de leur décomposition on multiplie tous les nombres premiers entrant dans la décomposition de a ou de b, chacun avec l'exposant le plus élevé.

Propriété 7 Soit a et b des entiers relatifs non nuls. L'ensemble des multiples communs à a et à b est l'ensemble des multiples de PPCM (a ; b).

Exercice 17 Déterminer le plus petit entier naturel n supérieur ou égal à 32 dont le reste de la

division euclidienne par 26 et par 32 est égal à 12.

Propriété 8 Soit a et b des entiers relatifs non nuls. PGCD (a ; b) ×××× PPCM (a ; b) = | ab | .

On en déduit : PGCD (a ; b) = 1 ⇔ PPCM (a ; b) =

Exercice 18 Trouver les entiers naturels a et b avec a < b tels que

==

108);(PPCM

18);(PGCD

ba

ba.

Exercice 19 Soit n un entier naturel non nul, a = n ² + 3 n et b = (2n + 1) (n + 3). Déterminer PPCM (a ; b).

Propriété 9 Soit a et b des entiers relatifs non nuls.

Pour tout entier k relatif non nul, on a : PPCM (ka ; kb) = | k | × PPCM (a ; b)

Exercice 20 n désigne un entier naturel non nul, a = 7 n ( 5 n + 2 – 5 n ) et b = 5 n ( 7 n + 2 – 7 n ) .

Déterminer PPCM (a ; b). Théorème de Fermat Hors programme

Dans 3 l’équation x n + y n = z n n’a pas de solution autre que (0 ; 0 ; 0) lorsque n > 2 Quelques solutions pour n = 2 : 3² + 4² = 5² ; 6² + 8² = 10² ; 5² + 12² = 13²

4/4