Algorithme d'Euclide

nabil5 · September 2006

Dans le livre de Borde p19, pour l'algorithme d'Euclide il pose b=r1 dans la plupart des livres b est différent de r1 on le voit aussi dans la disposition pratique ou on fait apparaître a, b, r1, q1 ...
Quel est l'intérêt de poser b=r1. Désolé si ma question est bête (j'ai acheté le livre et je le trouve très bien).

thecrazy · September 2006

Ce que tu veux dire c'est que quand il écrit la première égalité, il pose
$a=b q_1 + r_1$ avec $r_1=b $, c'est bien ça ?

nabil5 · September 2006

Non, il pose r0 = a , r1 = b et il écrit a = bq1 + r2 (0 =< r2 < b)

GERARD · September 2006

Salut Nabil.

Je ne connais pas le livre de Borde, mais à vue de nez, il veut une suite de restes qui contient a et b comme premiers termes (sans doute pour recalculer a et b à partir de la suite et des derniers termes, le pgcd et 0.

Cordialement.

borde · September 2006

Bonjour Nabil,
Et merci, à toi aussi, pour ton intérêt pour ce travail...

Tu fais sans doute référence au passage de la page 19, non ? Gérard a bien répondu, en fournissant une (grande) partie de la réponse. Je pourrais compléter son propos en te disant que, lorsque j'ai écrit ce passage, j'avais en tête les exercices 2.2 et 3.22 : l'algorithme d'Euclide est utilisé ici pour démontrer le lemme de Thue (lui-même servant pour obtenir une décomposition d'un nombre premier $p \equiv 1 \pmod 4$ en somme de deux carrés). Dans ces exercices, deux suites supplémentaires (notées $s_n$ et $t_n$) font leur apparition, enrichissant l'algo d'Euclide usuel (puisqu'on y trouve, en particulier, une écriture du reste $r_k$ comme combinaison linéaire de $a$ et $b$, et ce, à chaque étape $k$ de l'algo d'Euclide). Pour faire coïncider tous les indices, j'ai fait démarrer la suite des restes à $r_0 = a$, puis, "logiquement", $r_1$ est dévolu à $b$ (qui, rappelons-le, est supposé tel que $1 \leqslant b < a$).

Cette explication te convient-elle ?
Borde.

nabil5 · September 2006

Merci à tous pour vos réponses, merci Borde pour ta réactivité, ton explication me convient parfaitement, ton livre est super je l'utilise pour préparer l'agrégation interne.

bs1 · September 2006

bonjour

toujours page 19, concernant le théorème de Gabriel Lamé, le théorème que je connaissais est:

" le nombre de divisions nécessaires pour calculer le pgcd dans l'algorithme d'Euclide est inférieur ou égal à 5 fois le nombre de chiffres du plus petit nombre ; de plus , 5 est la meilleure valeur possible."

En effet,5 est atteint avec 8 et 13 (qui sont deux nombres successifs de la suite de Fibonacci.

Ref: Joyaux Mathématiques de R. Honsberger (CEDIC) p71

Borde , je suppose que ce résultat est identique au tien; mais quel est l'énoncé historique de G.Lamé ?

Eh oui, je possède aussi ton livre depuis quelques heures.. Présent sur l'étagère de Gibert Marseille (avec deux autres exemplaires),alors qu'il ne s'y trouvait pas en juillet.J'ai commencé à le lire dans le métro entre Gibert et la BU, puis un petit peu aux feux rouges en voiture en rentrant, et maintenant à la maison.

Norbert Verdier0 · September 2006

Pour tous mais pour Bernard et Olivier, plus particulièrement.

Ce qu'écrit Olivier autour de l'algorithme d'Euclide avait retenu mon attention. Voici ce que j'en dis dans une note de lecture à paraître d'ici peu dans le bulletin de l'AMQ (Association Mathématique du Québec) :

"Une première promenade aura pour fil directeur le théorème de la division euclidienne. Comment trouver le pgcd de deux nombres – le "plus grand codiviseur" disait Lucas - ? Facile! Avec l'algorithme d'Euclide! L'arithméticien a envie d'aller plus loin et de "mesurer" cet algorithme. Est-il performant ? Qu'est-ce qu'il peut apporter ? Le tout jeune académicien Lamé a démontré en 1844, à l'Académie des sciences, que « Le nombre de divisions à effectuer, pour trouver le plus grand commun diviseur entre deux entiers A, et B < A, est toujours moindre que cinq fois le nombre des chiffres de B » (Cf. Note 1). Son résultat avait été pressentie par Léger dans la Correspondance de Quételet (t.IX, p. 483) [Cf. Note 1] et par Finck dans les Nouvelles Annales [Cf. Note 2]. La preuve de Lamé repose sur l'emploi des nombres de Fibonacci. Olivier Bordellès, avec les mots d'aujourd'hui, l'expédie en quelques lignes (pp. 18-20). Sous forme d'exercice (2.2), il revisite l'algorithme d'Euclide via le lemme de Thue. L'exercice permet de démontrer un bel algorithme (Exercice 3.22), l'algorithme de Serret (intitulé initialement , "Sur un théorème relatif aux nombres entiers" paru dans le journal de Liouville en 1848, pp. 12-14) qui consiste à montrer que "si p est premier tel que p1[4] est la somme de deux carrés" (Serret écrivait que "Tout nombre premier 4k+1 est la somme de deux carrés"). Et le lecteur de se demander ? Que se passe-t-il si p ne répond pas aux contraintes ? Et l'auteur de répondre dans l'annexe A – le "Guide du raisonnement arithmétique" (pp.215) en invoquant la notion de "valuation" (permettant de savoir sous quelle condition un premier est décomposable en somme de carrés) et des résultats connexes liés aux inévitables Gauss et Lagrange."

Note 1 : Gabriel Lamé, « Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers », CRAS, Tome XIX, 1844, pp. 867-870. (Disponible sur Gallica en version numérisée). Le théorème de Lamé est le « premier » théorème s’intéressant à l’efficacité de l’algorithme d’Euclide. Plus tard Edouard Lucas (1842-1891) montrera le caractère optimal du théorème de Lamé. Cf. Lucas, Edouard, Théorie des nombres, 1891, pp. 333-339.
Note 2 : publié en 1833.
Note 3 : Nouvelles Annales de Mathématiques, T.I, 1842, pp. 354.

Cet aspect n'est évidemment qu'un des aspects des multiples richesses du livre d'Olivier. Mais c'était l'occasion d'évoquer Lamé. Encore un à qui il faudra rendre hommage en bonne et due forme, en mai ou en juillet!

Amitié, bonne soirée, à bientôt, etc. Norbert.

borde · September 2006

Je n'ai pas la compétence de Norbert pour parler de l'historique du théorème de Lamé, donc je renverrai les intervenants vers lui et les références qu'il donne.
De mon côté, j'ai simplement voulu attirer l'attention sur le lien entre le nombre de divisions successives dans l'algo d'Euclide et le nombre d'or, la démonstration devant faire apparaître ce lien de manière la plus claire possible.

Il est vrai que l'on nomme "théorème de Lamé" plusieurs résultats peut-être pas complètement identiques. Pour ceux qui s'intéressent à Lamé, l'IREM de Clermont-Ferrand, dont Bruno a été un des présidents, a conçu un énoncé très intéressant dessus, à l'usage des terminales S spécialité. Ce document a été mis en ligne sur le forum par Longjing, lui aussi très actif à l'IREM (n'est-ce pas, Jean-Jacques ?).

En tout cas, pour l'auteur que je suis devenu, toutes ces réactions font plaisir à lire.
Nabil : je te souhaite un plein succès pour ton agreg !
Borde.

Longjing · September 2006

Bonsoir
Entre deux messages pertinents d'Olivier (Borde), je me permets de rappeler une référence (moins culturelle et historique que celle fournie par M. Norbert Verdier)
http://wwwmaths.univ-bpclermont.fr/irem/lycee/arithmetique/ du théorème de Lamé.

Actif, Actif, c'est un bien grand mot ; disons que je vais essayer d'être moins passif à l'IREM avec une étude de calcul formel en classe de seconde...
...D'ici 2010...

bs1 · September 2006

bonjour

joli problème longjing: me suis toujours demandé si effectivement pour b ayant 2 chiffres, le nombre de 10 divisions pouvait être atteint; (idem pour 3 et 15);merci

le résultat figurant dans le livre d'Olivier est plus précis; par exemple: pour b=102, on obtient respectivement un maximum de 5x3=15 divisions nécessaires , alors que le max devient 10 divisions selon la relation du livre.Maintenant, 10 peut-il être atteint ?