TS Spé Lycée Beaussier Mathématiques

1

Chapitre 1

Arithmétique

Partie 2 : Division euclidienne

Propriété d'Archimède

Soit b un entier naturel non nul.

Pour tout entier naturel a, il existe un entier naturel n tel que a < b× n.

Remarque

Cela revient à dire que si b est positif, il existe toujours un multiple positif de b plus grand que

n’importe quel entier naturel a fixé au préalable.

Démonstration Nous donnons ici deux démonstrations de la proposition précédente.

• Démo 1 : comme b est un entier naturel non nul, 1 b≤ . Donnons nous un entier a

quelconque. En multipliant l’égalité précédente par l’entier positif a + 1, on tire :

( ) ( )1 1a b a+ ≤ × + or 1a a< + et finalement : ( )1a b a< × + . Choisissons n = a + 1 et

nous avons ainsi bien trouvé un entier n vérifiant a b n< × , ce qu’il fallait démontrer.

• Démo 2 : Ecrivons notre propriété avec des quantificateurs :

( )Soit , 0. , /b b a n a b n∈ ≠ ∀ ∈ ∃ ∈ < ×ℕ ℕ ℕ .

Faisons une démonstration par l’absurde : supposons que le contraire de la

proposition ( ), /a n a b n∀ ∈ ∃ ∈ < ×ℕ ℕ soit vrai, on aurait donc ( )/ ,a n a b n∃ ∈ ∀ ∈ ≥ ×ℕ ℕ

ce qui équivaut (b étant non nul) à l’existence d’un entier naturel a tel que

pour tout entier n, a

nb≥ . Tout entier n serait donc plus petit qu’un nombre réel

a

b fixé

ce qui ne se peut pas. La proposition contraire de la proposition à montrer étant fausse,

notre propriété est vraie.

Exemple

Si b = 5 et a = 51 dès que l’on choisit un entier n ≥ 11, on a < b×n.

Rappel : Technique de la division d'entiers naturels

Poser la division de 71 par 9.

On peut écrire 71 = 9 x 7 + 8.

71 s'appelle le dividende, 9 le diviseur, 7 le quotient et 8 le reste.

On a 8 < 9, le reste doit toujours être strictement inférieur au diviseur.

Remarque

Pour chercher le quotient q de la division de a entier naturel par b entier naturel non nul, on

cherche en pratique les multiples du diviseur b et on choisit celui qui précède immédiatement

le multiple strictement supérieur au dividende.

Si ,q b q× ∈ℕ est le multiple recherché, alors q est le quotient et r a b q= − × est le reste de la

division de a par b.

71 9

8 7

TS Spé Lycée Beaussier Mathématiques

2

Propriété 1 : Division euclidienne dansℕℕℕℕ (Admis)

Soit a un entier naturel et b un entier naturel non nul.

Il existe un unique couple (q ; r) d'entiers naturels tel que : a b q r= × + et 0 r b≤ <

On dit que a est le dividende, b le diviseur, q le quotient et r le reste

de la division euclidienne de a par b.

On dit que le couple unique (q ; r) est le résultat de la division euclidienne de a par b.

Démonstration

On considère l’ensemble { }/H n a b n= ∈ < ×ℕ .

Commençons par quelques remarques utiles pour la suite :

• Tout entier naturel élément de H vérifie a b n< × , tout entier naturel qui n’appartient

pas à H vérifie donc a b n≥ × (P1)

• Comme 0a ≥ , on peut écrire 0a b≥ × ce qui entraîne par (P1) que 0 H∉ (P2)

• H est non vide, en effet la propriété d’Archimède assure de l’existence d’un entier

naturel n vérifiant a b n< × (P3)

• H est une partie deℕ par construction (P4)

En utilisant (P3) et (P4) on déduit que H admet un plus petit élément d’après la propriété 0 du

polycopié précédent.

Notons p cet élément et étudions ses propriétés :

• p est un élément de H donc 0a b p a b p< × ⇔ − × < (P5)

• 0 H∉ par (P2) donc 0p ≠ et comme p est un entier naturel, 1 1 0 1p p p≥ ⇔ − ≥ ⇔ − ∈ℕ (P6)

• 1p − ∈ℕ par (P6) et 1p − est strictement plus petit que p qui est le plus petit élément de H,

donc 1p H− ∉ et ainsi par (P1) ( )1a b p≥ × − (P7)

Existence du couple (q ; r) :

Posons 1q p= − . En utilisant (P6) et (P7) on déduit que q∈ℕ et 0a b q− × ≥ .

Posons .r a b q= − × r est un entier et d’après ce qui précède 0r ≥ donc r∈ℕ .

De plus ( )

( )5

1

strictementnégatif par

r a b q a b p a b p b b= − × = − × − = − × + <

P

�����.

On a donc bien montré l’existence de deux entiers naturels p et q tels que a b q r= × + et 0 r b≤ < .

Unicité du couple (q ; r) : Supposons qu’il existe deux couples (q ; r) et (q’ ; r’) solutions du problème initial, on aurait

donc : a b q r= × + et ' 'a b q r= × + .

Quitte à soustraire membres à membres les deux égalités précédentes on obtient :

( )r r b q q′ ′− = × − (P8)

Comme de plus : 0 r b≤ < et 0 r b′≤ < , on a 0 r b≤ < et 0b r′− < − ≤ , en ajoutant membre à

membre on tire b r r b′− < − < (P9).

Combinons (P8) et (P9) pour obtenir ( )b b q q b′− < × − < ce qui équivaut puisque b est

strictement positif après simplification à ( )1 1q q

∈

′− < − <

ℤ

�����et par suite 0q q q q′ ′− = ⇒ = .

On a donc a b q r= × + et 'a b q r= × + donc r r′= .

L’unicité du couple (q ; r) est finalement démontrée.

TS Spé Lycée Beaussier Mathématiques

3

Remarque

Si le reste r est nul, alors a est divisible par b et réciproquement.

Exemple

Division euclidienne de 249 par 7: 249 = 7 x 35 + 4.

a = 249 ; b = 7 ; q = 35 et r = 4. Remarquons que l’on a bien 0 7r≤ < .

Avec une calculatrice

On dit qu’un nombre réel x admet pour partie entière a si et seulement si a est l’unique entier

relatif tel que 1a x a≤ < + . Par exemple la partie entière de 208,32 est 208 ; celle de 249 est

249 lui-même, celle de -17,31 est -18 !

Pour faire par exemple avec une calculatrice quelconque la division euclidienne de a par

b si a est entier naturel et b entier naturel non nul :

Remarque

• Le reste d'une division euclidienne par 2 est soit 0 soit 1.

• Tout nombre pair s'écrit sous la forme 2k avec k∈ℤ .

• Tout nombre impair s'écrit sous la forme 2k + 1 avec k∈ℤ .

Evaluer a/b, si le résultat est un entier c’est le quotient et le reste est

nul. Sinon prendre la partie entière q du résultat obtenu et

calculer r a b q= − × . q est le quotient et r est le reste de la division de

a par b. Dans l’exemple ci contre, on a réalisé la division euclidienne

de a = 1815 par b = 17, on trouve q = 106 et r = 13

Programme de division euclidienne

de deux entiers naturels pour une TI 82

PROGRAM:DIVISION

:ClrHome

:Lbl A

:Disp "B>0"

:Input "A=",A

:Input "B=",B

:If B<=0

:Goto A

:int(A/B)→Q

:A-B*Q→R

:Disp "Q=",Q

:Disp "R=",R

Programme de division euclidienne

de deux entiers naturels pour une Casio

"A"?→A

"B"?→B

Int(A ÷B)→Q

A-B×Q→R

"LE QUOTIENT EST"

Q

"LE RESTE EST"

R

TS Spé Lycée Beaussier Mathématiques

4

Propriété 2 : Division euclidienne dansℤℤℤℤ (Admis)

Soit a un entier relatif et b un entier naturel non nul.

Il existe un unique couple (q ; r) etq r∈ ∈ℤ ℕ tel que : a b q r= × + et 0 r b≤ <

On dit que a est le dividende, b le diviseur, q le quotient et r le reste

de la division euclidienne de a par b.

On dit que le couple unique (q ; r) est le résultat de la division euclidienne de a par b.

Remarque

Ce résultat bien qu’admis est démontré en annexe de cette leçon.

Exemple

la méthode de division d’un entier relatif a par un entier naturel non nul

b à l’aide d’une calculatrice est strictement identique à celle décrite dans

le cadre de la division dansℕ .

Par exemple pour la division euclidienne de -477 par 13 :

Evaluer -477/13 et en prendre la partie entière :

attention la partie entière de -36,69… est -37 !!

Calculer -477-(-37× 13) = 4. On a donc q = -37 et r = 4.

Exercices sur la division euclidienne Exercice 1

a/ Quels peuvent être le diviseur et le quotient d’une division dont le dividende est 557 et

le reste 89 ?

b/ Quels peuvent être le diviseur et le reste d’une division dont le dividende est 1517 et le

quotient 75 ?

Exercice 2

La différence de deux entiers naturels est 538.

Si l’on divise l’un par l’autre, le quotient est 13 et le reste est 22.

Quels sont ces entiers ?

Exercice 3

Soit x est un entier relatif tel que le reste de la division euclidienne de x par 7 est 2.

Quels sont les restes des divisions euclidiennes par 7 de 2x et de 3x ?

Exercice 4

Quel est le reste dans la division euclidienne par 11 de 10 ; 100 ; 1 000 ; 10 000

Quelle conjecture peut-on faire sur le reste dans la division euclidienne par 11 de10n lorsque n∈ℕ ?

Exercice 5

Démontrer que si n est un entier naturel impair, alors 2 1n − est divisible par 8.

Exercice 6

Quels sont les restes possibles dans la division euclidienne d'un entier naturel n par 3.

En déduire que tout entier relatif peut s'écrire sous l'une des formes 3k ; 3k + 1 ou 3k + 2 avec k∈ℤ .

Exercice 7

Le 9 septembre 2010 est un jeudi, quel jour de la semaine sera le 9 septembre 2011 ?

TS Spé Lycée Beaussier Mathématiques

5

Annexe

Démonstration de la division euclidienne dansℤℤℤℤ

On peut effectuer une démonstration utilisant celle effectuée dansℕ qui traîne dans n’importe

quel livre de terminale S.

Nous présentons ici une démonstration valable dans le cas de la division euclidienne

dansℕ etℤ . Son seul désavantage est de faire intervenir un nombre réel, ce qui dans le cadre

de l’étude des propriétés des entiers est mal venu.

Sa simplicité reste le meilleur argument en sa faveur.

Existence du couple (q ; r)

On considère le réela

b et q sa partie entière. On a donc et 1

aq q q

b∈ ≤ < +ℤ et quitte à

multiplier chaque membre de l’inégalité par b positif on déduit :b q a b q b× ≤ < × + .

Posons r a b q= − × : r est entier relatif et des inégalités précédentes on tire 0 etr r b≤ < .

L’existence du couple (q ; r) est démontrée.

Unicité du couple (q ; r)

Elle est strictement identique à celle démontrée dans le cadre de la division euclidienne dansℕ .