1. Deux questions du programme
Ce que l’on sait faire à la main, et ce que l’on ne sait plus faire.
Le programme de seconde pose deux questions sur les entiers :
Les deux algorithmes
1. Un entier naturel \(a\) est-il un multiple d’un entier naturel \(b\) ?
2. Quel est le plus grand multiple de \(a\) inférieur ou égal à \(b\) ?
À la main, la division euclidienne répond aux deux : \(b=aq+r\) avec \(0\leqslant r\lt a\) ; \(b\) est un multiple de \(a\) si et seulement si \(r=0\), et le plus grand multiple cherché est \(aq\). Mais qui poserait de tête la division de \(123\,456\,789\) par \(37\) ? Ce parcours construit une méthode, la teste sur un cas connu, puis la confie à une machine.
On pose la division euclidienne : \(535=12\times 44+7\), avec \(0\leqslant 7\lt 12\). Le plus grand multiple de \(12\) inférieur ou égal à \(535\) est \(12\times 44=528\) ; le suivant, \(540\), dépasse \(535\).
2. Euclide : retrancher tant que l’on peut
Alexandrie, vers 300 avant notre ère.
Dans le livre VII des Éléments, Euclide ne divise pas : il mesure. Un nombre en mesure un autre quand, retranché de lui autant de fois qu’on le peut, il l’épuise exactement. Sa définition 5 dit en substance : le plus grand nombre est un multiple du plus petit quand il est mesuré par le plus petit. Et ses premières propositions procèdent ainsi : « le plus petit étant retranché du plus grand, de manière continuelle… ».
Retranchons \(7\) de \(47\), tant que c’est possible :
Ce qui diffère du cours
Euclide n’écrit ni \(a=bq+r\) ni aucune lettre : il décrit des longueurs et des opérations en phrases. Mais le nombre de soustractions est notre quotient, et ce qui reste est notre reste.
\(47-6\times 7=5\), et \(5\lt 7\) : on ne peut plus retrancher. Le nombre de soustractions est le quotient, ce qui reste est le reste : \(47=7\times 6+5\). Comme il reste \(5\), \(7\) ne « mesure » pas \(47\).
3. La méthode d’Euclide en Python
Ajouter \(a\) tant que l’on ne dépasse pas \(b\) : c’est la même idée, à l’envers.
Le programme ci-dessous part de \(m=0\) et ajoute \(a\) tant que \(m+a\) ne dépasse pas \(b\) : à la fin, \(m\) est le plus grand multiple de \(a\) inférieur ou égal à \(b\). La seconde fonction s’en sert pour savoir si \(a\) est un multiple de \(b\). On le valide d’abord sur un cas connu : \(50=7\times 7+1\), donc la réponse doit être \(49\).
Si la console ne se charge pas, le même programme s’exécute sur https://sciency.co/console (nouvel onglet).
Lire le résultat
Le programme affiche \(49\), puis True False : \(49\) est un multiple de \(7\), \(50\) n’en est pas un. La méthode est validée sur le cas connu. Modifiez la dernière ligne pour essayer d’autres nombres.
plus_grand_multiple(8, 75) ?La boucle ajoute \(8\) tant que l'on ne dépasse pas \(75\) : \(m\) vaut \(0\), \(8\), \(16\), …, \(72\). Elle fait \(9\) tours (le quotient) et renvoie \(72\). Vous pouvez le vérifier dans la console.
4. Plus court : le quotient et le reste
Python sait faire la division euclidienne en une instruction.
En Python, b // a donne le quotient et b % a le reste de la division euclidienne de \(b\) par \(a\). Les deux fonctions s’écrivent alors en une ligne chacune : remplacez-les dans la console, et vérifiez que les résultats ne changent pas.
Dans est_multiple(a, b), on demande si le premier nombre est un multiple du second : ici est_multiple(1001, 13), qui calcule 1001 % 13 (le reste, ici \(0\)) et le compare à \(0\). Le quotient 1001 // 13 n'est jamais nul ici.
5. Hors de portée de la main
Le cas que personne ne poserait de tête.
Écrivez dans la console print(plus_grand_multiple(271, 1000000007)), puis print(1000000007 % 271). Avec la version du quatrième écran, la réponse est immédiate ; avec celle du troisième, la boucle tourne des millions de fois (essayez : quelques secondes d’attente).
Le reste est ce qui sépare \(1\,000\,000\,007\) de son plus grand multiple de \(271\) : \(1\,000\,000\,007-999\,999\,756=251\). Il n'est pas nul : \(1\,000\,000\,007\) n'est pas un multiple de \(271\). La première version aurait fait \(3\,690\,036\) tours de boucle ; la seconde fait une seule division.
6. Un nombre qui en cache trois
\(1001\), et les nombres qui se répètent.
Essayez print(est_multiple(615615, 11)) : la console répond True. Plus surprenant, elle répond True pour tous les nombres de six chiffres de la forme « abcabc », et aussi avec \(7\), \(11\) ou \(13\) à la place de \(11\). Une boucle peut les tester tous :
La machine vérifie les \(900\) cas sans trouver d’exception. Mais vérifier n’est pas démontrer : la question ci-dessous donne la raison.
\(615615=615\times 1000+615=615\times 1001\), et \(1001=7\times 11\times 13\). Donc \(615615=615\times 91\times 11\) : c'est un multiple de \(11\) (et de \(7\), \(11\), \(13\)), alors que \(615\) n'en est pas un (\(615=11\times 55+10\)).
7. Ce qu’il faut retenir
Une idée vieille de vingt-trois siècles, trois lignes de Python.
Les deux algorithmes
Le plus grand multiple de \(a\) inférieur ou égal à \(b\) est \(a\times q\), où \(q\) est le quotient de \(b\) par \(a\) : a * (b // a). Le nombre \(a\) est un multiple de \(b\) si et seulement si le reste est nul : a % b == 0.
Retrancher (ou ajouter) tant que l’on peut, comme Euclide, donne les mêmes résultats, mais en autant d’étapes que le quotient : c’est trop lent pour les grands nombres.
Votre parcours
Vous avez répondu à 0 question(s) sur 6 du premier coup.