La Bnbox !

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
Alors 3|-12, 3 divise -12.

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^*)
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'

Alors c=aqq' or qq' appartientà Z, donc par définition : a|c

2)
Si a|b alors ac|bc
Démonstration
Hypothèses :

• a|b <=> Il existe un entier relatif q tel que : b=aq

Donc bc=acq
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'

k et k' appartenant à Z on a :
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^er 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^ème 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 () sont tels que :
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

Donc : PGCD(80,35) = 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>