Adloun

Minimal n'est pas minimum, et l'on peut les compter

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 9 — Ordres bien fondés et induction structurelle

Énoncé

Dans l'ensemble ordonné par la divisibilité :

Corrigé

1. Les minimaux sont exactement les nombres premiers de , et il y en a dix, énumérés par le calcul :

Preuve. est minimal s'il n'a aucun diviseur strict dans . Ses diviseurs autres que lui-même sont — hors de — et ses diviseurs propres . Il est donc minimal si et seulement si il n'a pas de diviseur propre , c'est-à-dire s'il est premier.

2. Aucun minimum. Un minimum devrait diviser tous les éléments de , donc diviser à la fois et : ce serait , qui n'est pas dans . On a donc dix éléments minimaux et aucun minimum — l'illustration exacte de la mise en garde du cours, et cette fois avec un compte.

3. Les maximaux sont les éléments de dont aucun multiple propre n'est dans . Le plus petit multiple propre de est : est donc maximal si et seulement si , c'est-à-dire . Il y en a quinze — calcul vérifié : . Noter que , et ne le sont pas, malgré leur taille : , et sont dans .

Il n'y a pas de maximum : il devrait être multiple de et de , donc valoir au moins .

Le dessin qui aide. L'ordre de divisibilité sur se lit comme le graphe orienté acyclique du cours : un arc de vers quand divise immédiatement. Les minimaux sont les sommets sans arc sortant — les dix premiers —, les maximaux ceux sans arc entrant. Un minimum serait un sommet atteint depuis tous les autres : il n'y en a pas, et le graphe le montre d'un coup d'œil.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.