Forum de mathématiques - Bibm@th.net

Bonjour,

Je me permets d'intervenir pour proposer une synthèse. Je n'ai pas lu la discussion dans tous ses détails, mais voilà les points importants qui en ressortent selon moi. Je ne discute que du cas appelé P1 par Omhaf, correspondant à l'exemple de la divisibilité de 33333 par 41.

Omhaf propose un algorithme pour décider si un nombre entier donné dont le chiffre des unités est 1 divise un autre nombre entier donné.

Comme mentionné par d'autres lecteurs, il est vrai que la lecture des justifications et des algorithmes proposés est rendue difficile par un manque de rigueur et d'habitude des conventions de l'écriture mathématique. Mais c'est tout à l'honneur d'Omhaf de rechercher de l'aide sur les forums pour que nous puissions justement l'aider à exprimer ses idées pour qu'elles soient lues par d'autres.

Après lecture des diapositives d'Omhaf, concernant le cas P1, je propose d'épurer son algorithme de la façon suivante. Le code ci-dessous est exécutable en Python.

La fonction P1 a pour paramètres:
    p: un entier naturel dont le chiffre des unités est 1
    n: un entier naturel
Elle renvoie vrai si p divise n, faux sinon.

Ensuite, il serait important de démontrer que cet algorithme est correct, c'est à dire qu'il termine lorsque qu'il est éxécuté avec des arguments respectant les contraintes imposées et qu'il donne la bonne réponse.

Une partie de la justification reposerait sur le "Théorème" proposé par Omhaf, qu'il convient de reformuler, car il est effectivement écrit de façon incorrect, comme expliqué par d'autres lecteurs. Voici une reformulation que je pense correcte et fidèle à l'idée d'Omhaf. Je ne considère que des entiers naturels, car la divisibilité entre entiers relatifs se ramène à celle entre entiers naturels en considérant les valeurs absolues des nombres en jeu.

Lemme. Pour tous entiers naturels [tex]u,a,b[/tex] avec [tex]0\leq b\leq 9[/tex] :  [tex](10u+1)[/tex] divise [tex](10a+b)[/tex] si et seulement si [tex](10u+1)[/tex] divise [tex](a-ub)[/tex].

Il faut avoir à l'esprit que c'est un résultat évident d'arithmétique élémentaire qui se vérifie en quelques lignes. La preuve que l'algorithme P1 ci-dessus est correcte est également très simple.

Ce qui ne veut pas dire que le travail d'Omhaf n'est pas digne d'intérêt, mais il faut montrer en quoi il est intéressant. Est-il nouveau? (J'en doute fort, car l'algorithme est essentiellement une division par la droite, et de nombreux algorithmes de divisions ont été proposés depuis des millénaires). Est-il rapide? Par exemple, est-il essentiellement plus rapide que l'algorithme d'Euclide?

Bonne continuation!