I) PGCD de deux entiers naturels :

1) Déf :

Soient a ,b .
a + b est un sous-groupe de  et   d tq a + b = d

Dém :

a + b car a + b 

Soit x,y a + b ,  ( k,l )   , x = ak +bl

( k',l' ) ² tq y = ak' +bl'

x - y = a(k - k') + b(l - l') a + b

Donc a + b sous-groupe de 

Par conséquent ,  ! d  tq a + b = d

Théorème :

d est l'unique entier vérifiant :

(i) d | a et d | b
(ii) Si d'  tel que d' | a et d' | b alors d' | d

Preuve :

(i) a d et b  d

Donc :

k  , a = kd

k' , b = k'd

d | a et d | b

(ii) d'   tq d' | a et d' | b

a  d'  et b  d'

a + b  d'
C'est-à-dire :

d  d' d'où  : d' | d

Rque :

d est le plus grand diviseur au sens de la relation d'ordre 

Déf :

d est appelé le plus grand diviseur commun de a et b .On le note pgcd(a,b)

2) Relation de Bezout :

a ,b ^* , d = pgcd(a,b). Alors :  ( u,v ) ² tq au + bv = d

Rque :

L'ensemble des diviseurs de a et b est l'ensemble des diviseurs de leur pgcd.

3) Propriétés :

a,b,c  , pgcd(a,0) = a = pgcd(a,a)

pgcd(a,b) = pgcd(b,a)

Associativité : pgcd( a ,(pgcd(b,c)) = pgcd((pgcd(a,b),c)

pgcd(ca,cb) = c pgcd(a,b)

Preuve de l'associativité :

Soit d =pgcd(b,c) ,D = pgcd(a,d)

alors D | a et D | d

Donc D | a ,D | b , D | c

Donc D | c et D | pgcd(a,b)

Soit k  tq k | c et k | pgcd(a,b)

alors k | c , k | a , k | b

k | a et k | pgcd(b,c) = d

Donc k | pgcd(a,d) = D

4) Recherche du PGCD :

Soit a,b  tq a = bq + r avec 0r < b
Alors pgcd(a,b) = pgcd(b,r)

Théorème :

Soit (a_n)_n et (b_n)_n tq a₀ = a
b₀ = b
a_n+1 = b_n
Tant que b_n0 , b_n+1 = reste de la division euclidienne de a_n par b_n .

Alors  p ,a_p = 0 et pgcd(a,b) = a_p

 ( Programme sur la calculatrice : cf leçon précédente )

II) PPCM de deux entiers naturels :

1) Déf :

a,b 

ab est un sous-groupe de  et  ! m  tq ab =m

Théorème :

m est l'unique entier vérifiant :

(i) a | m et b | m
(ii) Si m'  tq a | m' et b | m' alors m | m'

Déf :

m est appelé le plus petit multiple commun à a et b . On le note ppcm(a,b)

2) Propriétés :

a,b,c   ppcm(a,a) = a = ppcm(a,1)

ppcm(a,b)=ppcm(b,a)

ppcm(a,ppcm(b,c)) = ppcm( ppcm(a,b),c)
 

II) Nombres premiers entre eux :

1) Déf :

a,b  . a et b sont premiers entre eux  pgcd(a,b) = 1

Conséq :

a,b  .  (a,b)  (0,0)

d =pgcd(a,b)   a'  tq a = da'

b' tq b = db' et pgcd ( a',b' ) = 1

2) Théorème de Bezout :

a,b  :

pgcd(a,b) = 1   (u,v) , au +bv = 1

Rque :

( u,v ) n'est pas unique

3) Théorème de Gauss :

Si pgcd(a,b) = 1 et a | bc

Alors : a | c

 Corollaire :

a,b,n 

Si a | n et b | n avec pgcd(a,b) = 1 ,

alors ab | n

4) Relation entre PGCD et PPCM :

a,b , d =pgcd(a,b) , m = ppcm(a,b)

Alors :

Démo :

• Cas où pgcd(a,b) = 1 :

m = ppcm(a,b)   (c,c') ² tq m = ac = bc'

Donc a | bc'

or pgcd(a,b) = 1 d'où a | c' ( th de Gauss )

k  tq c' = ak

D'où : m = kab

Donc : k = 1  (car ab multiple de a et b et m est le plus petit de ces multiples )

C'est-à-dire : md = ab

• Cas où a et b non premiers entre eux :

d = pgcd(a,b) ,  a'  tq a = da'

b'  tq b = db'   avec pgcd(a',b') = 1

On a ppcm(a',b') = a'b' (en utilisant le cas précédent)

d²( ppcm(a',b')) = d² a'b' = ab ( car da' = a et db' = b )

D'où d(ppcm(da',db')) = ab

Donc : d(ppcm(a,b)) = ab .C'est-à-dire : md = ab

Lemme :

pgcd(a,b) = 1

Alors : ppcm(a,b) = ab

Prop :

a,b  tq a | b

alors ppcm(a,b) = b
 

IV) Applications :

1) Equation diophantienne :

a,b  . Déterminer tous les couples (x,y) de ² tq ax + by = c (E)

• Si d ne divise pas c alors (E) n'a pas de solution
• Si d | c :

 d = pgcd(a,b)  a',b'  tq a = da'

D'où :  (u,v)² , a'u + b'v = 1

Donc le couple ( cu/d , cv/d ) est solution de (E)

Par conséquent ,l'ensemble (S) des solutions est donné par :

S = { ( uc/d + kb/a , cv/d - ka/d ) , k }

2) Congruence :

a,b 
Si pgcd(a,b) = 1 ,alors :

/ ab    / a   / b