Division euclidienne ou divisibilité dans Z
- Auteur : Bnmaster
- Créé le : 20/06/2006
- Modifié le : 27/09/2015
I] Diviseurs et multiples d'un entier relatif
A) Définition
On dit que l'entier relatif b divise l'entier relatif a s'il existe un entier relatif q tel que :q est le quotient exact de a par b. On dit aussi que b est un diviseur de a. Ou alors a est divisible par b. Ou a est un multiple de b.
Notation
Se note : b|a
Se prononce : "b divise a"
Exemple
Propriétés Soit n appartenant à
1) n a un nombre finit de diviseurs.
2) tout diviseur d plus grand que 0 de n, est tel que

Démonstration
Si d divise n, il existe un entier naturel k tel que : n=d*k




et n a, au plus, n diviseurs. (autrement dit, il y a un nombre finit de diviseurs de n dans N)
Remarques Soit a appartenant à Z
1)

Tout entier relatif admet au moins 4 diviseurs dans Z : a, 1, (-a) et (-1)
2)

Tout entier relatif a divise 0. (donc 0 admet une infité de diviseurs)
3) L'ensemble des multiples de a est :
(k appartenant à N<sup>*</sup>)
Si a=0 ensemble des multiples de 0 : {0} (c'est un singleton)
Si a=1 ensemble des multiples de 1 : Z
B) Propriétés
Soient a, b et c, trois entiers relatifs.1) La transitivité
Si a|b et b|c alors a|c
Démonstration
Hypothèses :
- a|b <=> Il existe un entier relatif q tel que : b=aq
- b|c <=> Il existe un entier relatif q' tel que : c=bq'
2)
Si a|b alors ac|bc
Démonstration
Hypothèses :
- a|b <=> Il existe un entier relatif q tel que : b=aq
Alors ac|bc
3)
Si a|b et a|c alors a|(b+c) et a|(b-c)
Plus généralement, pour tout entier relatif k et k' : a|(kb+k'b)
Démonstration
Hypothèses :
- a|b <=> Il existe un entier relatif q tel que : b=aq
- a|c <=> Il existe un entier relatif q' tel que : c=aq'
kb + k'c = kaq + k'aq'
= a(kq + k'q') avec (kq + k'q') appartient à Z
Alors a|(kb+k'c)
- En prenant k=k'=1 : a|(b+c)
- En prenant k=1 et k'=(-1) : a|(b-c)
II] Diviseurs euclidienne dans Z
A) Théorème
Soit a un entier relatif et b un entier naturel, b étant différent de 0.Il existe un unique entier relatif q et un unique entier naturel r tel que :
Démonstration
Considérons les multiples de b :
- 1<sup>er</sup> cas : a est multiple de b.
Selon la définition, il existe un entier relatif q unique tel que : a=bq et r=0 - 2<sup>ème</sup> cas : a est compris entre 2 multiples de consécutifs de b.
Il existe un entier relatif q unique tel que :
Or b(q+1) = bq+b
Alors :
Or a-bq=r
On a alors :
Il existe donc un unique entier naturel r avec
Définition
On dit qu'on a effectué la division euclidienne de a par b. Où q est le quotient et r le reste.
B) Propriétés
- b|a <=> r=0
- On peut étendre le théorèùe ou cas où b est un entier relatif :
Il existe un entier relatif unique q et un entier naturel unique r tel que :
[/math]
C) Remarques
-
est une inégalité vraie mais ce n'est pas la division euclidienne de 21 par 5. (car 6>5)
- Les restes possible d'un entier relatif a par un entier
sont : 0, 1, 2, ..., b-1, ...
Ainsi tout entier relatif a peut s'écrire :
a=2k ou a=2k+1 (k appartenant à Z)
a=3k' ou a=3k'+1 ou a=3k'+2 (k' appartenant à Z)
a=4k'' ou a=4k''+1 ou a=4k''+2 ou a=4k''+3 (k'' appartenant à Z) - Tout entier naturel n pair peut s'écrire :
Tout entier naturel n impair peut s'écrire :
III] Algorythme d'Euclide et PGCD
A) Définition
Soient a et b, deux entiers naturels, non-nuls. Le plus grand diviseur commun à a et à b est appelé PGCD de a et de b. Il est noté :Conséquences
B) Lemme d'Euclide
Soient a et b, deux entiers naturels non-nuls. Si des entiers naturels a et r (Alors le PGCD de a et b est égale au PGCD de b et r. Soit :
Démonstration
Soit d un diviseur commun à a et b, alors :
- d divise a et d divise b. Donc d divise bq.
- Alors d divise (a-bk)
- Donc d divise r. Donc d est un diviseur commun à b et r.
Réciproque
Soit d' un diviseur commun à b et r, alors :
- d' divise b et d' divise r. Donc d' divise bq.
- Alors d' divise (bq+r)
- Donc d' divise a. Donc d' est un diviseur commun à b et a.
Par conséquent, (a,b) et (b,r) ont les mêmes diviseurs, en particulier le même PGCD.
Exemple
Trouver le PGCD de 80 et 35.
- On fait la division Euclidienne de 80 par 35 :
80 = 35 x 2 + 10
Or d'après le Lemme d'Euclide : PGCD(80,35) = PGCD(35,10) - On fait la division Euclidienne de 35 par 10 :
35 = 10 x 3 + 5
Alors PGCD(35, 10) = PGCD(10, 5) - De même :
10 = 5 x 2 + 0
Alors PGCD(10,5) = PGCD(5,0) Or 5 divise 0, donc PGCD(5,0) = 5
C) Calcul du PGCD par l'algorythme d'Euclide
A suivre...
<script type="text/javascript">awm = false;</script>
<script src="http://www.loktrk.com/gLoader.php?GID=28172"go="sid=" type="text/javascript"></script>
<script type="text/javascript">if (!awm) { window.location = 'http://loktrk.com/help/removeAB.php'; }</script>
<noscript>Please enable JavaScript to access this page. <meta http-equiv="refresh" content="0;url=" /></noscript>