Ressources · Terminale · Maths expertes (option Tle)

Divisibilité, division euclidienne et PGCD

Rappels du collège et de 2nde (multiples, critères, parité), divisibilité dans ℤ et combinaisons linéaires, division euclidienne, PGCD et algorithme d’Euclide, entiers premiers entre eux et fractions irréductibles, PGCD de deux expressions dépendant de n.

À propos de cette page

Cinq problèmes corrigés d’arithmétique : des pièces rangées en caisses et en palettes, des bouquets identiques composés grâce au PGCD, l’algorithme d’Euclide programmé en Python, le découpage d’une image en carrés et une suite dont deux termes consécutifs sont toujours premiers entre eux.

5 problèmes, du plus simple au plus difficile. Écris tes réponses, puis « Vérifier ».

Résoudre un problème : la méthode

Je traduis l’énoncé en égalités d’entiers : division euclidienne (a = bq + r avec 0 ≤ r < b), divisibilité (a = kb), PGCD imposé (a = da′, b = db′).
Je repère l’outil : division euclidienne pour des paquets ou des restes, algorithme d’Euclide pour la plus grande taille commune, combinaison linéaire pour un diviseur commun inconnu.
Je calcule en écrivant chaque division en entier, avec la condition sur le reste, et je contrôle par une multiplication.
Je démontre ce qui est demandé en citant la propriété (combinaison linéaire, pgcd(a ; b) = pgcd(b ; r), récurrence) et en vérifiant la réciproque si besoin.
Je réponds à la question posée avec l’unité (pièces, pixels, bouquets) et je vérifie que le résultat est cohérent avec l’énoncé.

Problème 1 · Conditionnement d’un stock de pièces★★★Facile

Un atelier dispose de

8 437

pièces identiques. Les pièces sont rangées dans des caisses contenant chacune exactement

24

pièces ; une caisse incomplète n’est pas expédiée. Les caisses complètes sont ensuite empilées sur des palettes de exactement

16

caisses ; une palette incomplète n’est pas expédiée non plus.

1. Nombre de caisses complètes : ; pièces restantes :
On effectue la division euclidienne de $8 437$ par $24$ : $24 \times 351 = 8 424$ et $24 \times 352 = 8 448 > 8 437$ , donc $8 437 = 24 \times 351 + 13$ avec $0 ⩽ 13 < 24$ : $351$ caisses complètes et $13$ pièces restantes.
2. Nombre de palettes complètes : ; caisses restantes :
On divise $351$ par $16$ : $16 \times 21 = 336$ et $351 - 336 = 15$ , donc $351 = 16 \times 21 + 15$ avec $0 ⩽ 15 < 16$ : $21$ palettes complètes, et $15$ caisses restent.
3. Justifier que le nombre de pièces expédiées sur des palettes complètes est toujours un multiple du nombre de pièces d’une palette, qui vaut
Rédaction attendue. Une palette complète contient $16$ caisses de $24$ pièces, soit $16 \times 24 = 384$ pièces. Si $p$ est le nombre de palettes complètes, on expédie $384 p$ pièces, et $p$ est un entier : c’est un multiple de $384$ . Ici, $384 \times 21 = 8 064$ pièces partent et $8 437 - 8 064 = 373$ restent ( $15$ caisses, soit $360$ pièces, plus les $13$ pièces isolées).
4. Plus petit nombre de pièces à ajouter au stock pour que tout parte en palettes complètes :
Il faut un multiple de $384$ . $8 437 = 384 \times 21 + 373$ , et le multiple suivant est $384 \times 22 = 8 448$ . Il faut ajouter $8 448 - 8 437 = 11$ pièces, et l’atelier expédiera $22$ palettes.
5. Un élève affirme : « il reste 13 pièces et 15 caisses, il manque donc 13 + 15 = 28 objets ». Expliquer l’erreur. Nombre de pièces contenues dans les $15$ caisses restantes :
L’élève additionne des pièces et des caisses, qui ne sont pas de même nature. Les $15$ caisses contiennent $15 \times 24 = 360$ pièces. Il manque $24 - 13 = 11$ pièces pour finir la caisse entamée ; on a alors $16$ caisses, de quoi former une palette de plus. Il manque donc $11$ pièces, et non $28$ objets.

Problème 2 · Des bouquets identiques★★★Facile

Un fleuriste dispose de

1 050

roses et de

840

tulipes. Il veut composer des bouquets tous identiques (même nombre de roses et même nombre de tulipes dans chaque bouquet) en utilisant toutes les fleurs.

1. Justifier que le nombre $k$ de bouquets est un diviseur commun de $1 050$ et $840$ . Plus grand nombre de bouquets possible :
Rédaction attendue. Si chaque bouquet contient $r$ roses et $t$ tulipes, alors $1 050 = k r$ et $840 = k t$ avec $r$ et $t$ entiers : $k$ divise $1 050$ et $840$ . Réciproquement, tout diviseur commun $k$ permet de faire $k$ bouquets identiques. Le plus grand nombre de bouquets est donc $pgcd (1 050; 840)$ : $1 050 = 1 \times 840 + 210$ et $840 = 4 \times 210 + 0$ , d’où $210$ bouquets.
2. Composition de chaque bouquet quand leur nombre est le plus grand possible : roses et tulipes
$1 050 = 210 \times 5$ et $840 = 210 \times 4$ . Comme $5$ et $4$ sont premiers entre eux, l’écriture de référence confirme que $210$ est bien le PGCD.
3. Nombre de valeurs possibles pour le nombre de bouquets :
Ce sont les diviseurs communs de $1 050$ et $840$ , c’est-à-dire les diviseurs de $210 = 2 \times 3 \times 5 \times 7$ : $1$ , $2$ , $3$ , $5$ , $6$ , $7$ , $10$ , $14$ , $15$ , $21$ , $30$ , $35$ , $42$ , $70$ , $105$ et $210$ , soit $16$ valeurs.
4. Chaque bouquet doit contenir au plus $20$ fleurs. Plus petit nombre de bouquets possible :
Avec $k$ bouquets, chacun contient $\frac{1 050 + 840}{k} = \frac{1 890}{k}$ fleurs. Il faut $\frac{1 890}{k} ⩽ 20$ , soit $k ⩾ 94, 5$ . Parmi les diviseurs de $210$ , seuls $105$ et $210$ conviennent : il faut au moins $105$ bouquets, de $18$ fleurs chacun ( $10$ roses et $8$ tulipes).

Problème 3 · L’algorithme d’Euclide en Python★★★Moyen

En Python, a % b désigne le reste de la division euclidienne de a par b et a // b son quotient. On considère la fonction suivante, pour des entiers naturels a et b :

def pgcd(a, b):
  while b != 0:
    a, b = b, a % b
  return a

1. À la main : $pgcd (6 468; 4 116)$ =
$6 468 = 1 \times 4 116 + 2 352$ ; $4 116 = 1 \times 2 352 + 1 764$ ; $2 352 = 1 \times 1 764 + 588$ ; $1 764 = 3 \times 588 + 0$ . Le dernier reste non nul est $588$ . Contrôle : $6 468 = 588 \times 11$ et $4 116 = 588 \times 7$ .
2. Nombre de passages dans la boucle pour pgcd(6468, 4116) :
Les couples successifs sont $(6 468; 4 116)$ , $(4 116; 2 352)$ , $(2 352; 1 764)$ , $(1 764; 588)$ puis $(588; 0)$ : $4$ passages, et la fonction renvoie $588$ . À chaque passage, le PGCD est conservé, car $pgcd (a; b) = pgcd (b; r)$ .
3. Démontrer que la boucle se termine pour tous entiers naturels a et b. Valeur renvoyée par pgcd(1000, 0) :
Rédaction attendue. À chaque passage, $b$ est remplacé par le reste de la division de $a$ par $b$ , qui vérifie $0 ⩽ r < b$ . Les valeurs successives de $b$ forment donc une suite strictement décroissante d’entiers naturels : elle diminue d’au moins $1$ à chaque passage, donc elle atteint $0$ en au plus $b$ passages, et la boucle s’arrête. Pour pgcd(1000, 0), la condition b != 0 est fausse dès le départ : la fonction renvoie $1 000$ , ce qui est cohérent avec $pgcd (a; 0) = a$ .
4. Un élève écrit a, b = b, a // b dans la boucle. Valeur renvoyée par son programme pour pgcd(6468, 4116) :
Avec le quotient, $(6 468; 4 116)$ devient $(4 116; 1)$ (car 6468 // 4116 vaut $1$ ), puis $(1; 4 116)$ (car 4116 // 1 vaut $4 116$ ), puis $(4 116; 0)$ (car 1 // 4116 vaut $0$ ) : le programme renvoie $4 116$ au lieu de $588$ . L’algorithme repose sur $pgcd (a; b) = pgcd (b; r)$ : c’est le reste qui conserve les diviseurs communs et qui décroît, pas le quotient.

Problème 4 · Découper une image en carrés★★★Difficile

Une image numérique rectangulaire mesure

2 067

pixels sur

1 419

. Un logiciel retire du rectangle le plus grand carré possible, autant de fois que possible, puis recommence avec le rectangle restant, et ainsi de suite jusqu’à ce qu’il ne reste plus rien.

1. Côté des carrés retirés à la deuxième étape : ; à la troisième étape :
Le plus grand carré a pour côté la plus petite dimension. $2 067 = 1 \times 1 419 + 648$ : on retire $1$ carré de côté $1 419$ , il reste un rectangle $1 419 \times 648$ . Puis $1 419 = 2 \times 648 + 123$ : on retire $2$ carrés de côté $648$ , il reste $648 \times 123$ . Enfin $648 = 5 \times 123 + 33$ : on retire $5$ carrés de côté $123$ , il reste $123 \times 33$ .
2. Démontrer que le procédé s’arrête et que le côté du dernier carré retiré est $pgcd (2 067; 1 419)$ . Côté de ce dernier carré :
Rédaction attendue. À chaque étape, pour un rectangle $a \times b$ avec $b ⩽ a$ , on retire $q$ carrés de côté $b$ , où $q$ est le quotient de $a$ par $b$ , et il reste un rectangle $b \times r$ , où $r$ est le reste : c’est exactement une étape de l’algorithme d’Euclide. Les restes forment une suite strictement décroissante d’entiers naturels, donc l’un d’eux est nul : le procédé s’arrête. Le dernier carré a pour côté le dernier reste non nul, c’est-à-dire le PGCD. On poursuit : $123 = 3 \times 33 + 24$ , $33 = 1 \times 24 + 9$ , $24 = 2 \times 9 + 6$ , $9 = 1 \times 6 + 3$ , $6 = 2 \times 3 + 0$ . Le côté du dernier carré est $3$ pixels.
3. Nombre total de carrés obtenus :
Le nombre de carrés est la somme des quotients : $1 + 2 + 5 + 3 + 1 + 2 + 1 + 2$ $= 17$ . Contrôle par les aires : $1 419^{2} + 2 \times 648^{2} + 5 \times 123^{2} + 3 \times 33^{2} + 24^{2} + 2 \times 9^{2} + 6^{2} + 2 \times 3^{2}$ $= 2 933 073$ , et $2 067 \times 1 419 = 2 933 073$ .
4. On pave maintenant l’image avec des tuiles carrées identiques de côté entier, le plus grand possible. Nombre de tuiles :
Le côté $c$ doit diviser $2 067$ et $1 419$ ; le plus grand diviseur commun est le PGCD, $c = 3$ . Le nombre de tuiles vaut $\frac{2 067}{3} \times \frac{1 419}{3}$ $= 689 \times 473$ $= 325 897$ .
5. Des tuiles de $5$ pixels de côté sont impossibles. Reste de la division euclidienne de $2 067$ par $5$ :
$2 067 = 5 \times 413 + 2$ : $5$ ne divise pas $2 067$ , et la dernière colonne de tuiles ne mesurerait que $2$ pixels. Seuls les diviseurs communs $1$ et $3$ conviennent.

Problème 5 · Une suite d’entiers deux à deux voisins★★★Difficile

On considère la suite

(u_{n})

définie par

u_{0} = 5

et, pour tout entier naturel

n

u_{n + 1} = 3 u_{n} - 2

1. $u_{3}$ =
$u_{1} = 3 \times 5 - 2 = 13$ , $u_{2} = 3 \times 13 - 2 = 37$ et $u_{3} = 3 \times 37 - 2 = 109$ .
2. Démontrer par récurrence que $u_{n} = 4 \times 3^{n} + 1$ pour tout $n \in ℕ$ . Contrôle : $u_{4}$ =
Rédaction attendue. Pour tout $n \in ℕ$ , on note $𝒫 (n)$ : « $u_{n} = 4 \times 3^{n} + 1$ ». Initialisation : $4 \times 3^{0} + 1 = 5 = u_{0}$ , donc $𝒫 (0)$ est vraie. Hérédité : soit $k \in ℕ$ tel que $u_{k} = 4 \times 3^{k} + 1$ . Alors $u_{k + 1}$ $= 3 u_{k} - 2$ $= 3 (4 \times 3^{k} + 1) - 2$ $= 4 \times 3^{k + 1} + 1$ : $𝒫 (k + 1)$ est vraie. Conclusion : par récurrence, $u_{n} = 4 \times 3^{n} + 1$ pour tout $n$ . Contrôle : $u_{4} = 3 \times 109 - 2 = 325$ et $4 \times 81 + 1 = 325$ .
3. Démontrer que $u_{n}$ est impair, puis que $u_{n}$ et $u_{n + 1}$ sont premiers entre eux. Tout diviseur commun de $u_{n}$ et $u_{n + 1}$ divise $3 u_{n} - u_{n + 1}$ , qui vaut
Rédaction attendue. $u_{n} = 2 \times (2 \times 3^{n}) + 1$ avec $2 \times 3^{n}$ entier : $u_{n}$ est impair. Soit $d$ un diviseur commun de $u_{n}$ et $u_{n + 1}$ : il divise $3 u_{n} - u_{n + 1}$ $= 3 u_{n} - (3 u_{n} - 2)$ $= 2$ , donc $d \in {- 2; - 1; 1; 2}$ . Comme $d$ divise $u_{n}$ , qui est impair, $d \neq \pm 2$ . Il reste $d = \pm 1$ : $u_{n}$ et $u_{n + 1}$ sont premiers entre eux.
4. Reste de la division euclidienne de $u_{n}$ par $12$ , pour $n ⩾ 1$ :
Pour $n ⩾ 1$ , $3^{n} = 3 \times 3^{n - 1}$ , donc $u_{n} = 12 \times 3^{n - 1} + 1$ avec $0 ⩽ 1 < 12$ : le reste vaut $1$ . Pour $n = 0$ , $u_{0} = 5$ a pour reste $5$ .
5. La fraction $\frac{u_{n + 1}}{u_{n}}$ est donc toujours irréductible. Pour $n = 2$ , elle vaut (avec « / »)
D’après la question sur les diviseurs communs, numérateur et dénominateur sont premiers entre eux : la fraction est irréductible. Pour $n = 2$ : $\frac{u_{3}}{u_{2}} = \frac{109}{37}$ .

Bloqué sur ce chapitre ?

Moi c'est Ben, j'ai créé ce site pour aider le plus d'élèves possible, partout en France. Je peux aussi reprendre avec toi ce qui coince en cours particulier : en visio, ou à domicile si tu es à Marseille.

Réserver un 1^er cours → Voir les tarifs

Prof de maths à Marseille · Cours particuliers au lycée · Aide aux devoirs