Division euclidienne

Division euclidienne

Définition

Soient a et b deux entiers relatifs (b non nul). Il existe un unique couple (q, r) d'entiers avec \( 0 \leqslant r \leqslant b-1 \).
q est appelé quotient de la division euclidienne de a par b et r reste de la division euclidienne de a par b.

On parle parfois de division entière plutôt que de division euclidienne.

Exemple.

\( 11 = 4 \times 2 +3 \) montre que le quotient de la division euclidienne de 11 par 4 est 2 et le reste est 3.
Par contre le quotient de la division de 11 par 2 n'est pas 4, puisque 3 n'est pas inférieur à b=2.

Exemple.

Soit k>0 un entier. Quel est le quotient de la division euclidienne de a = 2^k-1 par b=2 ?

Comme \( 2 \times 2^{k-1} = 2^k \) et que 2^k > a, on voit que 2^k-1 est un peu trop grand pour être le quotient.
On essaie donc c=2^k-1-1.
On a 2c=2^k-2, donc 2c+1=a. De a=bc+1 et 0≤ 1 < b, on déduit que le couple ( 2^k-1-1 , 1 ) est le couple (quotient, reste) de la division de a par b.

Quotient et partie entière

Soient a et b deux entiers naturels (b non nul). Le quotient q de la division euclidienne de a par b est égal à \( \lfloor \frac{a}{b} \rfloor \) ( partie entière de \( \frac{a}{b} \) ).

Justification

Soient a et b deux entiers naturels, b non nul. Notons q et r le quotient et le reste dans la division euclidienne de a par b.

On a 0≤ r< b d'où bq ≤ bq+r < bq+b ou encore bq ≤ a < b(q+1). On en déduit : \[ q \leqslant \frac{a}{b} < q+1\] c'est à dire \[ q = \lfloor \frac{a}{b} \rfloor \]

En langage python.

a//b donne le quotient, a%b le reste.

On peut également utiliser divmod().

a=11
b=4

print("Quotient et reste de la division euclidienne de {} par {}. ".format(a,b))
print("Quotient : ", a//b)
print("Reste : ", a%b)
print("Couple (quotient, reste) : ", divmod(a,b))

Ce qui donne :

Quotient et reste de la division euclidienne de 11 par 4. 
Quotient :  2
Reste :  3
Couple (quotient, reste) :  (2, 3)

Les chiffres d'un entier

L'un des usages que nous aurons de la division euclidienne est l'accès aux chiffres d'un entier (en écriture décimale ou binaire ou dans une autre base).

Le chiffre des unités

Le chiffre des unités de l'écriture en base 10 d'un entier a est égal au reste de la division entière de a par 10.

De même, le chiffre des unités de l'écriture en base 2 d'un entier a est égal au reste de la division entière de a par 2.

Justification.

Exemple avec l'entier n=5234.
On a \[ n= 5\times 10^3 + 2 \times 10^2 + 3\times 10^1 + 4 \] soit \[ n= 10 \times \left( 5\times 10^2 + 2 \times 10^1 + 3\times 10^0\right) + 4 \] Comme 0≤ 4 < 10, 4 est le reste de la division euclidienne de n par 10. On voit également que le nombre de dizaines est le quotient de n par 10.
Le chiffre des dizaines sera quant à lui le chiffre des unités du nombre des dizaines, c'est à dire le reste de la division par 10 du quotient de la division par 10 de l'entier n.
En itérant, on aurait aussi le chiffre des centaines, des milliers ...

Le chiffre de poids 10^k

Dans l'écriture d'un entier en base 10, le chiffre coefficient de 10^k est appelé chiffre de poids 10^k (vocabulaire analogue en base 2, en base 16...)

Exemple avec l'entier n=5234.
\[ n= 5\times 10^3 + 2 \times 10^2 + 3\times 10^1 + 4 \] Le chiffre de poids 10² est 2 (chiffre des centaines), le chiffre de poids 10¹ est 3 (chiffre des dizaines), le chiffre de poids 10⁰ est 4 (chiffre des unités).

Le chiffre de poids 10^k de l'entier a est le reste de la division euclidienne par 10 du quotient de la division euclidienne de n par 10^k.
Avec la notation python : (n//10**k)%10

De façon analogue (n//2**k)%2 donnera le chiffre de poids 2^k dans une écriture binaire de l'entier. C'est d'ailleurs là une définition de l'écriture binaire d'un entier.