CHP.1 DIVISION EUCLIDIENNE NOVEMBRE 2011 BTS1 ET TS SPE
Il s'agit d'une branche très ancienne des mathématiques consacrée aux nombres.
1. DIVISION EUCLIDIENNE D'UN ENTIER NATUREL PAR UN
ENTIER NATUREL NON NUL.
. Soit a dans IN et b dans IN*.
Il existe un unique couple ( q ; r ) dans IN × IN tel que: a =bq + r
avec 0 ≤ r < b .
On dit que: a est le dividende
b le diviseur
q le quotient
r le reste
2 . Schéma : On pose en général la division euclidienne ainsi:
| a | | b |
| r | | q |
En Python 2.7 : q = a / / b et r = a % b
3. EXEMPLE:
a = 17 b = 2 17 = 2 × 8 + 1
On a : q = 8 r = 1
4. JUSTIFICATION:
a est dans IN et b dans IN*.
• Existence de q et r .
• • a = b
Alors a = 1 × b + 0 q = 1 et r = 0 0 ≤ r < b
• • a < b
On a seulement a = 0 × b + a q = 0 r =a
On a bien 0 ≤ a < b c-à-d 0 ≤ r < b
• • a > b
On peut sur la droite des réels lister dans l'ordre croissant
les multiples strictement positifs de b jusqu'à ( a + 1 )b.
1 b ; 2 b ; 3 b ; .... etc ... ; k b ; ( k + 1 ) b ; .... ; ( a + 1 ) b
où k dans IN compris entre 1 et a + 1.
Comme b est dans IN* on a b ≥ 1
et d'autre part : ( a + 1 ) b = a b + b
Donc a b + b > a c-à-d a < ( a + 1 ) b
Mais on a : b < a et a < ( a + 1 ) b
Donc 1 b < a < ( a + 1 ) b
a est strictement compris est entre le premier terme b
et le dernier terme ( a + 1) b de cette liste.
a et donc compris entre deux termes consécutifs de cette liste.
Il existe un unique entier naturel q tel que q b ≤ a < ( q + 1 ) b
c-à-d tel que q b ≤ a < q b + b
Donc, en retranchant q b à chaque membre: on a 0 ≤ a − q b < b
Posons: r = a − q b
On a donc o ≤ r < b r entier naturel
D'où :
Il existe un unique entier naturel q et un entier naturel r tel que
a = bq + r avec o ≤ r < b
Conclusion: L'existence de q et de r est avérée.
• Unicité.
Raisonnons par l'absurde.
Supposons a = b q + r
a = b q' + r' avec 0 ≤ r < b et 0 ≤ r ' < b
avec q ≠ q' ou r ≠ r'
Alors, par soustraction membre à membre on a : 0 = b q + r − ( b q' + r ' )
c-à-d 0 = b q + r − b q' − r '
c-à-d r ' − r = b q − b q ' c-à-d b ( q − q ' ) = r ' − r
Donc on en déduit que : b divise r ' − r
Mais 0 ≤ r < b 0 ≤ r ' < b
Donc l'écart entre r et r ' est strictement inférieur à b.
Donc: b ne peut pas diviser r ' − r à moins que r ' − r = 0 ,
auquel cas b ( q − q ' ) = r ' − r donne b ( q − q ' ) = 0
et ainsi q = q' ( b étant non nul )
Mais alors on a : r = r ' et q = q '
Il y a une contradiction.
Conclusion: L'unicité est prouvée.
5. DIVISION EUCLIDIENNE D'UN ENTIER RELATIF PAR UN
ENTIER RELATIF NON NUL.
Soit a et b dans l'ensemble des entiers relatifs avec b non nul.
Il existe un unique couple ( q , r ) d'entiers relatifs tels que
a = b × q + r avec 0 ≤ r < | b |
Dans le cas où b est dans IN* on a :
a = b × q + r avec 0 ≤ r < b
Cela résulte de la division de | a | par | b | .
------------------------------------------------------------------------------------------------