Multiples et diviseurs

Rappels ensembles

Ensemble des entiers naturels : N = {0 ; 1 ; 2 ; 3 ; 4 ; 5 ; ... ; n ; n+1 ; ... }

Ensemble des entiers relatifs : Z = { ... ; -n-1 ; -n ; ... ; -2 ; -1 ; 0 ; 1 ; 2 ; ... ; n ; n+1 ; ... }

Propriétés des ensembles N et Z :

Toute partie non vide de N possède un plus petit élément
Toute partie finie non vide de Z possède un plus petit élément
Toute partie finie non vide de N ou Z possède un plus grand élément

Généralités

Théorème : Soit a et b deux entiers relatifs, a est un multiple de b s'il existe un entier relatif c tel que a = bc

Si b ≠ 0 (respectivement c ≠ 0), on dit que b est diviseur de a

Exemple - Diviseurs positifs de 60 : { 1 ; 2 ;3 ; 4 ; 5 ; 6 ; 10 ; 12 ; 15 ; 20 ; 30 ; 60 }

Remarques :

0 ne divise aucun entier. ∀b∈Z*, 0 = b x 0, donc 0 n'a qu'un seule multiple, lui même. Et il a une infinité de diviseurs.
∀a∈Z / a≠0, a a une infinités de multiples : { ... ; -2na ; -na ; -a ; 0 ; 2a ; ... ; na ; ... }
∀a∈Z a comme diviseur -a ; -1 ; 1 ; a

Divisions euclidiennes

Rappels dans N

Propriété : Soient a et b deux entiers naturels avec b ≠ 0, il existe un unique couple ( q ; r ) d'entiers naturels tels que a = bq + r avec 0 < r < b

Démonstration de l'existence :

Soit les multiples de b : { 0 ; b ; 2b ; 3b ; qb ; (q + 1)b ; ... ; ab }

Comme a > 0 et b > 1, alors ab > a donc 0 < a < ab

première possibilité : a est l'un des multiples de b, alors a = bq avec 0 < q < a
deuxième possibilité : a n'est pas l'un des multiples de b, alors il est compris entre deux multiples de b consécutifs bq < a < b(q + 1)

Soit : bq < a < b(q + 1) ssi 0 < a - bq < b

en posant r = a - bq, on obtient : 0 < r < b

Conclusion : Dans les deux cas, on a bq < a < b(q + 1) soit 0 < r < b en posant r = a - bq ce qui revient à dire que a = bq + r avec 0 < r < b

Démonstration de l'unicité :

Supposons qu'il existe deux couples ( q1 ; r1 ) et ( q2 ; r2 ) d'entiers naturels tels que a = bq1 + r1 (avec 0 < r1 < b) et a = b2 + r2 (avec 0 < r2 < b)

On a alors bq1 + r1 = bq2 + r2 d'où b(q1q2) = r2 - r1

avec 0 < r1 < b

et 0 < r2 < b

d'où -b < -r1 < 0

et 0 < r2< b

PGCD

Théorème : Soit a et b deux entiers relatifs non nuls, l'ensemble des diviseurs communs à a et b admet un plus grand élément

Démonstration : L'ensemble des diviseurs de a et b est non vide car il contient toujours 1 et -1. De plus, cet ensemble est fini car c'est l'intersection des diviseurs de a (ensemble fini) et ceux de b (ensemble fini). Donc l'ensemble des diviseurs de a et b est une partie fini non vide de Z, il admet un plus grand élément

Définition : Soit a et b deux entiers relatifs non nuls, le plus grand diviseur commun à a et b s'appelle le PGCD de a et b et se note PGCD ( a ; b )

Exemple : Soit 98 et 91, les diviseurs de 98 sont : { 1 ; 2 ; 7 ; 14 ; 49 ; 98 } et ceux de 91 sont { 1 ; 7 ; 13 ; 91 }. Les diviseurs communs sont donc { 1 ; 7 }, soit PGCD ( 91 ; 98 ) = 7

Conséquences :

PGCD ( a ; b ) ∈ N*
Si b divise a, alors PGCD ( a ; b ) = I b I
PGCD ( 0 ; b ) = I b I
PGCD ( a ; b ) = PGCD ( I a I ; I b I )

Algorithme d'Euclide

Théorème : Soient a et b deux entiers naturels tel que 0 < b < a

On a la division euclidienne a = bq + r avec 0 ≤ r ≤ b

alors PCGD ( a ; b ) = PGCD ( b ; r )

Démonstration :

Si b divise a, alors r = 0 : On a PGCD ( a ; b ) = b et PGCD ( b ; r ) = PGCD ( b ; 0 ) = b ; d'où PCGD ( a ; b ) = PGCD ( b ; r )
Si b ne divise pas a : Il existe un unique couple ( q ; r ) d'entiers naturels tel que a = bq + r avec 0 ≤ r < b. Tout diviseur commun de a et b divise toute combinaison linéaire de a et b, en particulier a - bq = r, donc tout diviseur commun à a et b est diviseur de b et r. Réciproquement, tout diviseur commun à b et r, en particulier bq + r = a. Tout diviseur commun à b et r est donc diviseur de a et b.

Conclusion : Les diviseurs communs de a et b sont les mêmes que ceux de b et r ; ils admettent donc le même plus grand élément d'où PGCD ( a ; b ) = PGCD ( b ; r )

Algorithme d'Euclide = divisions successives

Soit a et b deux entiers naturels tels que 0 ≤ a < b

a = bq0 + r0 avec 0 ≤ r0 < b

b = r0q1 + r1 avec 0 ≤ r1 < b

r0 = r1q2 + r2 0 ≤ r2 < b

r1 = r2q3 + r3 0 ≤ r3 < b

r2 = r3q4 + r4 0 ≤ r4 < b

ri = ri+1qi+2 + ri+2 avec 0 ≤ ri+2 < b

On a alors 0 ≤ ... ≤ ri+2 ≤ ri+1 ≤ ri ≤ ... ≤ r2 ≤ r1 ≤ r0 < b

Ces inégalités montrent que la suite des restes est une suite d'entiers naturels strictement décroisante, donc il existe un rang n tel que rn+1 = 0

De plus, par le théorème précédent on a :

PGCD ( a ; b ) = PGCD ( b ; r0 ) = PGCD ( r0 ; r1 ) = ... = PGCD ( rn ; rn+1 ) = PGCD ( rn ; 0 ) = rn

d'où PGCD ( a ; b ) = rn

Théorème : Soit a et b deux entiers naturels tels que 0 < b < a, si b ne divise pas a alors PGCD ( a ; b ) est le dernier reste non nul de la suite des divisions de l'algorithme d'Euclide

Exemple : PGCD ( 138 807 ; 52 089 )

138 807 = 52 089 x 2 + 34 629

52 089 = 34 629 x 1 + 17 460

34 629 = 17 460 x 1 + 17 169

17 460 = 17 169 x 1 + 291

17 169 = 291 x 59 + 0

PGCD ( 138 807 ; 52 089 ) = 291

Théorème 1 : Soit a et b deux entiers distincts non nuls, l'ensemble des diviseurs communs à a et b est l'ensemble des diviseurs de leur PGCD

Démonstration : On a PGCD ( a ; b ) = PGCD ( I a I ; I b I ) donc on peut supposer que a et b sont deux entiers naturels, supposons de plus 0 < b < a

On a donc comme vu précédemment que les diviseurs communs à a et b sont identiques aux diviseurs communs de b et r0 dans la division euclidienne de a par b : a = bq0 + r0 avec 0 ≤ r0 < b et ( q0 ; r0 ) entiers naturels.

De même, soit la division euclidienne de b par r0 : b = r0q1 + r1 avec 0 ≤ r1 < b et ( q1 ; r1 ) entiers naturels.

Ainsi de suite jusqu'aux diviseurs communs de rn-1 et rn qui sont identiques aux diviseurs communs de rn et 0 dans la division euclidienne de rn-1 par rn : rn-1 = rnqn+1 + 0 avec 0 ≤ 0 < rn et ( qn+1 ; 0 ) entiers naturels, soit les diviseurs de rn qui dans la suite de divisions euclidiennes est le PGCD ( a ; b )

Exemple : Soit 54 et 24, les diviseurs de 54 sont { 1 ; 2 ; 3 ; 6 ; 9 ; 18 ; 27 ; 54 } et ceux de 24 qui sont : { 1 ; 2 ; 3 ; 4 ; 6 ; 8 ; 12 ; 24 } ; les diviseurs communs sont donc { 1 ; 2 ; 3 ; 6 }

Or PGCD ( 54 ; 24 ) = 6 et les diviseurs de 6 sont { 1 ; 2 ; 3 ; 6 }

Théorème 2 : Soit a et b deux entiers relatifs non nuls, pour tout entier relatif k non nul, on a PGCD ( ka ; kb ) = I k I PGCD ( a ; b )

Démonstration : On a PGCD ( ka ; kb ) = PGCD ( I ka I ; I kb I ) = PGCD ( I k I I a I ; I k I I b I )

On peut donc supposer que a, b et k sont des entiers naturels et que 0 < b < a

Si b divise a : PGCD ( a ; b ) = b et de plus kb divise ka d'où PGCD ( ka ; kb ) = kb = k PGCD ( a ; b)
Si b ne divise pas a : en multipliant par k toutes les divisions euclidiennes successives on a PGCD ( ka ; kb ) = kr. Or rn = PGCD ( a ; b ) d'où PGCD ( ka ; kb ) = k PGCD ( a ; b )

Exemple : PGCD ( 1050 ; 700 )

Or 1050 = 50 x 7 x 3 et 700 = 50 x 7 x 2, d'où PGCD ( 1 050 ; 700 ) = 50 x 7 x PGCD ( 3 ; 2 ) = 350

Nombres entiers entre eux

Définition : Deux entiers relatifs a et b sont dits premiers entre eux ssi PGCD ( a ; b ) = 1

Exemple : Soient les nombres 65 et 42

Diviseurs de 42 : { 1 ; 2 ; 3 ; 6 ; 7 ;14 ; 21 ; 42 }

Diviseurs de 65 : { 1 ; 5 ; 13 ; 65 }

PCGD ( 42 ; 65 ) = 1

Les nombres 42 et 65 sont premiers entre eux

Remarque : Ne pas confondre nombres premiers entre eux et nombres premiers : 21 et 4 sont premiers entre eux, mais ils ne sont pas premiers

Propriété : Soit a et b deux entiers relatifs non nuls, si PGCD ( a ; b ) = d, alors il existe des entiers relatifs a’ et b’ premiers entre eux tel que a = da’ et b = db’

Démonstration :

Exemple : Soit 1050 et 700, on a PGCD ( 1050 ; 700 ) = 350, d’où