Arithmétique/Exercices/Division euclidienne

Exercice 1-1

Si l'on divise 4 294 et 3 521 par un même entier positif, on obtient respectivement pour restes 10 et 11. Quel est ce nombre ?

Solution

Ce nombre est strictement supérieur à 11, et est un diviseur de 4 294 – 10 = 4 284 et de 3 521 – 11 = 3 510, qui sont tous deux divisibles par 2 et 9.

3 510 = 2 × 9 × 5 × 13

4 284 = 2 × 9 × 238

5 et 13 sont premiers et ne divisent pas 238, donc pgcd(3 510, 4 284) = 2 × 9 = 18.

Le nombre cherché est donc le seul diviseur de 18 strictement supérieur à 11, c'est-à-dire 18 lui-même.

 

Exercice 1-2

Dans une division euclidienne entre deux entiers positifs, quels peuvent être le diviseur et le reste dont le dividende est 1 517 et le quotient 75 ?

Solution

0 ≤ 1 517 – 75b < b ⇔ 1 517 / 76 < b ≤ 1 517 / 75 donc diviseur b = 20 et reste r = 1 517 – 20 × 75 = 17.

 

Exercice 1-3

On divise cinq entiers naturels consécutifs par 5. Combien obtient-on de restes distincts et quels sont ces restes ?

Solution

Quand on ajoute 1 à un nombre, le reste de sa division par 5 est augmenté de 1, sauf s'il était égal à 4, auquel cas le nouveau reste est 0.

On obtient donc une suite de cinq restes distincts : (0, 1, 2, 3, 4) ou (1, 2, 3, 4, 0) ou (2, 3, 4, 0, 1) ou (3, 4, 0, 1, 2) ou (4, 0, 1, 2, 3).

 

Exercice 1-4

a et b sont deux naturels, avec b non nul. Dans la division euclidienne de a par b, le quotient n'est pas nul. Prouvez que a est strictement supérieur au double du reste.

Solution

a = bq + r avec r < b et q ≥ 1 (et b > 0) donc a ≥ b + r > 2r.

 

Exercice 1-5

a et b sont deux naturels. Dans la division euclidienne de a par b, le reste est supérieur ou égal au quotient q. Prouvez que si l'on divise a par b + 1, on obtient le même quotient.

Solution

a = bq + r avec 0 ≤ q ≤ r < b donc a = (b + 1)q + (r – q) avec 0 ≤ r – q < b.

 

Exercice 1-6

Trouver un nombre qui, divisé par 21, donne pour reste 4 et qui, divisé par 17, donne le même quotient et pour reste 16.

Solution

21q + 4 = 17q + 16 ⇔ (21 – 17)q = 16 – 4 ⇔ 4q = 12 ⇔ q = 3, donc la seule solution est 21×3 + 4 = 17×3 + 16 = 67.

 

Exercice 1-7

Le dividende d'une division est inférieur à 900. Le quotient est 72 et le reste 12. On cherche le diviseur et dividende. Expliquer pourquoi il n'y a pas de solution.

Solution

Diviseur b ≥ 13 donc dividende 72b + 12 ≥ 72×13 + 12 = 948.

 

Exercice 1-8

Dans une division euclidienne entre entiers naturels, quels peuvent être le diviseur et le quotient lorsque le dividende est 320 et le reste 39 ?

Solution

Diviseur b > 39 et bq = 320 – 39 = 281 est premier donc diviseur b = 281 et quotient q = 1.

 

Exercice 1-9

Dans une division euclidienne entre entiers naturels, quels peuvent être le diviseur et le reste lorsque le dividende est 990 et le quotient 70 ?

Solution

0 ≤ 990 – 70b < b ⇔ 990 / 71 < b ≤ 990 / 70 donc diviseur b = 14 et reste r = 990 – 70×14 = 10.

 

Exercice 1-10

On effectue la division euclidienne de x par 4 et l'on appelle y le quotient et r le reste.

1. Écrivez les relations qui traduisent cette division.
2. x étant donné, on lui associe y, définissant ainsi une suite. Représenter graphiquement cette suite pour x entier relatif de –12 à 11.

Solution

1. x = 4y + r et 0 ≤ r < 4.
2. y est la partie entière de x/4 :

   ${\begin{array}{c|ccccccc|}x&-12&-11&-10&-9&-8&-7&-6&-5&-4&-3&-2&-1&0&1&2&3&4&5&6&7&8&9&10&11\\\hline y&-3&-3&-3&-3&-2&-2&-2&-2&-1&-1&-1&-1&0&0&0&0&1&1&1&1&2&2&2&2\\\hline \end{array}}$

 

Exercice 1-11

On effectue la division euclidienne de x par 4 et l'on appelle q le quotient et y le reste.

1. Écrivez les relations qui traduisent cette division.
2. x étant donné, on lui associe y, définissant ainsi une suite. Démontrer que cette suite est périodique, et la représenter graphiquement pour x entier relatif de –12 à 11.

Solution

1. x = 4q + y et 0 ≤ y < 4.
2. La suite est 4-périodique car si x = 4q + y alors x + 4 = 4(q + 1) + y.

   ${\begin{array}{c|ccccccc|}x&-12&-11&-10&-9&-8&-7&-6&-5&-4&-3&-2&-1&0&1&2&3&4&5&6&7&8&9&10&11\\\hline y&0&1&2&3&0&1&2&3&0&1&2&3&0&1&2&3&0&1&2&3&0&1&2&3\\\hline \end{array}}$

 

Exercice 1-12

b est un entier tel que 0 < b ≤ 11.

c et r sont respectivement le quotient et le reste de la division euclidienne de 132 par b.

1. Écrivez les relations qui traduisent ces hypothèses.
2. Démontrer que b ≤ c.
3. Démontrer que dans la division euclidienne de 132 par c, le quotient est b et le reste est inchangé (c'est-à-dire r).
4. Montrer par un contre-exemple que si l'on abandonne l'hypothèse : 0 < b ≤ 11, le résultat de la question 3 n'est pas toujours vrai.

Solution

1. 132 = bc + r et 0 ≤ r < b.
2. 132 – bc < b ⇒ 132/c < b + 1 ≤ 12 ⇒ c > 132/12 = 11 ≥ b (on a donc même b < c).
3. r < c d'après la question précédente.
4. La plus petite valeur de b pour laquelle c ≤ r est b = 15. La plus grande (avec c > 0 pour que la question ait un sens) est évidemment b = 131. (Entre les deux, certaines valeurs de b conviennent et d'autres non.)

 

Exercice 1-13

a et b sont des entiers naturels tels que 0 < b² ≤ a.

c et r sont respectivement le quotient et le reste dans la division euclidienne de a par b.

1. Écrivez les relations qui traduisent ces hypothèses.
2. Démontrer que b ≤ c.
3. Démontrer que dans la division euclidienne de a par c, le quotient est b et le reste est inchangé (c'est-à-dire r).
4. Trouver un contre-exemple qui montre que si a < b², il peut arriver que le quotient de a par c ne soit pas égal à b.

Solution

1. a = bc + r et 0 ≤ r < b.
2. a – bc < b ⇒ b² ≤ a < b(c + 1) ⇒ b < c + 1 ⇒ b ≤ c.
3. r < c d'après la question précédente.
4. Cf. exercice précédent, ou plus simplement : a = 3 et b = 2.

 

Exercice 1-14

Soient a et b deux entiers relatifs distincts. On divise a et b par la différence a – b. Comparer les quotients et les restes de ces deux divisions euclidiennes.

Solution

En remarquant que a = a – b + b, on trouve que si q et r sont le quotient et le reste de la division de b par a – b alors ceux de la division de a par a – b sont q + 1 et r.

 

Exercice 1-15

Soit b un entier strictement positif et q un entier relatif. Pour quels entiers relatifs a le quotient de la division de a par b est-il égal à q ?

Solution

Pour a = bq + r avec 0 ≤ r < b, c'est-à-dire pour bq ≤ a < b(q+1).

 

Exercice 1-16

Une division d'entiers positifs étant effectuée, on recommence la même opération après avoir augmenté le diviseur de x unités (x ≥ 0).

Peut-on choisir x non nul pour que les deux opérations conduisent au même quotient ?

Lorsque le problème est possible, indiquer un procédé pour déterminer les solutions.

Solution

Soit a = bq + r la première division. Alors, a = (b + x)q + (r – qx), donc la seconde division a pour quotient q si et seulement si r – qx ≥ 0.

Si q = 0, n'importe quel x (≥ 1) convient.

Si q > 0, la condition sur x est : x ≤ r/q, donc il existe de tels x (≥ 1) si et seulement si r ≥ q, et les solutions x sont alors tous les entiers de 1 à X, où X est le plus grand entier tel que qX ≤ r, c'est-à-dire le quotient de la division de r par q.