Arithmétique dans Z

Introduction

L'arithmetique etudie les proprietes des nombres entiers, en particulier la divisibilite. Elle introduit des outils fondamentaux (division euclidienne, PGCD, nombres premiers entre eux, theoremes de Bezout et de Gauss) utilises en cryptographie, en algorithmique et dans de nombreux problemes de codage.

1. Divisibilite dans Z

Soient a et b deux entiers relatifs. On dit que b divise a (ou b est un diviseur de a, ou a est un multiple de b) s'il existe un entier k tel que a = k.b. On note b | a.

Proprietes usuelles : si b|a et c|b, alors c|a (transitivite) ; si b|a et b|a', alors b|(a+a') et b|(a-a') ; si b|a, alors b|(k.a) pour tout entier k.

2. Division euclidienne

Soient a un entier relatif et b un entier naturel non nul. Il existe un unique couple d'entiers (q, r) tel que :

a = b.q + r, avec 0 <= r < b

q est appele le quotient et r le reste de la division euclidienne de a par b. On a b|a si et seulement si r = 0.

3. PGCD et PPCM de deux entiers

Soient a et b deux entiers naturels non nuls. Le plus grand commun diviseur de a et b, note PGCD(a,b), est le plus grand entier qui divise a la fois a et b. Le plus petit commun multiple, note PPCM(a,b), est le plus petit entier naturel non nul multiple a la fois de a et de b.

On a la relation : PGCD(a,b) x PPCM(a,b) = a x b.

4. Algorithme d'Euclide

L'algorithme d'Euclide permet de calculer PGCD(a,b) par divisions euclidiennes successives, en utilisant la propriete : PGCD(a,b) = PGCD(b, r) ou r est le reste de la division euclidienne de a par b. On repete le procede jusqu'a obtenir un reste nul : le dernier reste non nul est le PGCD cherche.

Exemple resolu

Calculer PGCD(252, 108) par l'algorithme d'Euclide.

252 = 108x2 + 36 108 = 36x3 + 0

Le dernier reste non nul est 36, donc PGCD(252,108) = 36.

5. Nombres premiers entre eux, theoremes de Bezout et de Gauss

Deux entiers a et b sont dits premiers entre eux si PGCD(a,b) = 1.

Theoreme de Bezout : a et b sont premiers entre eux si et seulement s'il existe deux entiers relatifs u et v tels que a.u + b.v = 1.

Theoreme de Gauss : si a divise b.c et si a et b sont premiers entre eux, alors a divise c.

Ces deux theoremes permettent notamment de resoudre des equations du type a.x + b.y = c dans Z (equations diophantiennes), et de demontrer des proprietes de divisibilite dans des situations ou le calcul direct est difficile.

Schema-bilan

Divisibilite (b|a) -> division euclidienne (a=bq+r, 0<=r<b) -> PGCD/PPCM (avec PGCD x PPCM = a x b) -> algorithme d'Euclide pour calculer PGCD(a,b) -> nombres premiers entre eux (PGCD=1) -> theoremes de Bezout et de Gauss.