Chapitre 2 L’arithmétique des entiers

« Chapitre 2 L’arithmétique des entiers Ce chapitre se déroule dans un décor unique, à savoir l’anneau des entiers relatifs noté Z et défini par : Z = {.

.

.

, −3, −2, −1, 0, 1, 2, 3, .

.

.}. Parfois, on se contentera d’évoluer dans le sous décor constitué des entiers naturels noté N et défini par : N = {0, 1, 2, 3, .

.

.} = {n ∈ Z, n > 0}. 2.1 Divisibilité et division euclidienne Ce décor étant posé, nous allons nous intéresser aux relations qu’il peut se tisser entre les entiers et plus particulièrement à la relation de divisibilité : Définition 2.1 Soit a et b sont deux entiers.

On dit que a divise b, ou que a est un diviseur de b, ou que b est un multiple de a, s’il existe q ∈ Z tel que b = a × q ; on note a | b. Propriété 2.2 On a la liste des propriétés suivantes : (i) ∀a, b, c ∈ Z, a | b et b | c ⇒ a | c ; (ii) ∀a, b ∈ Z, ∀n ∈ N, a | b ⇒ an | bn ; (iii) ∀a, b, c, d ∈ Z, a | c et b | d ⇒ ab | cd ; (iv) ∀a, b, c ∈ Z, a | b et a | c ⇒ a | b + c. Preuve — Laissée au lecteur.  Notons qu’il y a une autre relation courante entre entiers, à savoir a 6 b ou b > a.

Il existe un lien entre ces deux relations ; le voici. Proposition 2.3 dit : (i) Les diviseurs d’un entier b non nul sont tous plus petit que b ; autrement ∀a, b ∈ N∗ , a|b =⇒ a 6 b. ou plus généralement : ∀a, b ∈ Z∗ , a|b 21 =⇒ |a| 6 |b|. 22 CHAPITRE 2.

L’ARITHMÉTIQUE DES ENTIERS (ii) On a : ∀a, b ∈ Z∗ , (a | b et b | a) =⇒ a = ±b. (iii) Zéro est le seul entier divisible par plus grand que lui, c’est-à-dire : ∀a, b ∈ Z, (a | b et |a| > |b|) =⇒ b = 0. Preuve — Ces preuves sont faciles mais permettent de s’entraı̂ner à manier la rhétorique mathématiques. (i) Soit a, b ∈ N∗ tels que a | b.

Alors il existe q ∈ N∗ tel que b = a × q donc b > a. (ii) Par hypothèse, il existe α, β ∈ Z tels que b = aα et a = bβ.

On en déduit que a = aαβ ou encore a(1 − αβ) = 0 donc αβ = 1 car a 6= 0.

Il en resulte que α = β = 1 ou α = β = −1, ce qu’il fallait montrer. (iii) Raisonnons par l’absurde en supposant b 6= 0.

Alors |b| > 0.

Comme |a| > |b| on a donc |a| > 0 ou encore a 6= 0.

Comme par hypothèse a | b, on est en mesure d’appliquer le premier point : on en déduit que |a| 6 |b|.

C’est contraire à l’hypothèse donc b = 0.  Tout petit, on a dû vous apprendre à poser une division Euclidienne ; mais si rappelez vous, cela avait l’allure suivante : 1234 25 234 49 9 et cela voulait dire que 1234 = 25 × 49 + 9.

De plus chacun des protagonistes de cette égalité avait un petit nom : – 1234 s’appelle le dividende, – 25 s’appelle le diviseur, – 49 s’appelle le quotient, – 9 s’appelle le reste. En quoi consiste cette division ? à trouver le plus grand multiple de 25 qui est inférieur ou égal à 1234.

Cela explique pourquoi le reste est toujours strictement inférieur au diviseur.

Cette division remonte à l’antiquité avec Euclide1 . Théorème 2.4 (Division Euclidienne) Soient a, b ∈ Z, avec b 6= 0.

Il existe un unique couple d’entiers (q, r) ∈ Z2 tel que : a = bq + r et 0 6 r < |b|. Preuve — Ce théorème (versant existence) résulte du fait que toute partie non vide de N admet un plus petit élément. Existence : Pour le voir, commençons par supposer a et b positifs et introduisons l’ensemble : N = {y|y = a − n × b, n ∈ N, et y > 0} 1 Euclide, 325-265 avt J.C., Egypte. 23 2.2.

PLUS GRAND COMMUN DIVISEUR Comme on vient de le rappeler, cet ensemble (non vide car contenant a) admet un plus petit élément que l’on appelle r et qui par définition est positif et de la forme r = a − q × b pour un certain q ∈ N.

De plus on a r < b, ce que l’on peut montrer en raisonnant par l’absurde.

Si r > b alors : 0 6 r − b = a − (q + 1) × b =⇒ r − b ∈ N. Cela contredit la définition de r car r − b < r. Unicité : Supposons qu’il existe (q1 , r1 ) et (q2 , r2 ) ∈ Z2 tels que : a = bq1 + r1 = bq2 + r2 et 0 6 r1 , r2 < |b|. Alors b(q1 −q2 ) = r2 −r1 ou encore b | r2 −r1 .

Par ailleurs, les encadrements de r1 et r2 permettent de montrer que −|b| < r2 − r1 < |b|.

Pour que ceci soit compatible avec la relation de divisibilité précédente, il est nécessaire que r1 = r2 .

Du coup, on a aussi bq1 = bq2 ou encore q1 = q2 (car b 6= 0).

L’unicité attendue est prouvée.  L’entier q s’appelle le quotient de la division euclidienne de a par b et r s’appelle le reste de la division euclidienne de a par b. Le lien entre la divisibilité et la division euclidienne est contenu dans l’énoncé de la propriété suivante. Propriété 2.5 Un entier a est divisible par un autre entier b non nul si et seulement si le reste de la division euclidienne de a par b est nul. Preuve — Introduisons (q, r) les quotient et reste de la division euclidienne de a par b, c’est-àdire a = bq + r avec 0 6 r < |b|. Si r = 0 alors a = bq ou encore b | a. Réciproquement si b | a alors il existe q ′ ∈ Z tel que a = bq ′ .

En remplaçant dans le première égalité on obtient bq ′ = bq + r ou encore b(q ′ − q) = r ou encore b | r.

Comme |b| > |r|, il en découle que r = 0.  2.2 2.2.1 Plus grand commun diviseur Définition Soient a et b deux entiers.

On s’intéresse aux diviseurs communs de a et b.

Notons qu’il y a toujours de tels diviseurs car 1 et −1 divisent tous les entiers.

Mieux, nous allons établir qu’il y a toujours un diviseur commun plus grand que tous les autres.

Pour cela, commençons par prouver le théorème : Théorème 2.6 Soient a et b deux entiers.

Il existe un diviseur commun d à a et b qui est somme d’un multiple de a et d’un multiple de b, c’est-à-dire de la forme : d = au + bv avec u, v ∈ Z.

De plus cet entier est unique au signe près. 24 CHAPITRE 2.

L’ARITHMÉTIQUE DES ENTIERS Preuve — Existence : il suffit de le montrer pour a et b positifs ce qui peut se faire par récurrence sur l’entier n = a + b. Si n = 0 alors a = b = 0 et 0 seul diviseur commun à 0 et 0 s’écrit bien sous la forme 0 = 0 × 0 + 0 × 0. On suppose le théorème vrai pour tous les couples d’entiers dont la somme est inférieure ou égale à n. Soit a > b ∈ N tels que a + b = n + 1.

Si b = 0 alors a est un diviseur commun à a et b qui s’écrit a = a × 1 + b × 0.

Sinon, on remarque que a − b et b sont deux entiers positifs de somme a < a + b = n + 1.

On peut donc appliquer l’hypothèse de récurrence aux entiers a − b et b : il existe d un diviseur commun à a − b et b ainsi que u, v ∈ Z tels que : (a − b)u + bv = d =⇒ au + b(v − u) = d. Comme d divise a − b et b il divise aussi a.

Ainsi, on vient bien d’exhiber un diviseur commun à a et b de la forme voulue. Unicité au signe près : soit d et d′ deux diviseurs communs à a et b tous deux de la forme d = au.... »