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.

Code javascript

Quotient et partie entière

Lien entre les deux notions

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 \]

Code javascript