Le théorème de Lamé : Fibonacci, le PGCD, et la naissance de la complexité algorithmique

Le théorème de Lamé fait partie de ces résultats que je conseille volontiers à mes élèves quand ils cherchent un angle solide pour leur grand oral autour de Fibonacci. Il rassemble dans une même démonstration trois choses qu’on n’a pas l’habitude de voir ensemble : l’algorithme d’Euclide, la suite de Fibonacci, et l’idée même de complexité algorithmique. Le tout dans deux pages et demie publiées en 1844, soit plus d’un siècle avant que la complexité algorithmique ne devienne formellement une discipline.

J’ai écrit cet article pour que tu puisses t’en emparer entièrement. La problématique : combien d’étapes peut prendre l’algorithme d’Euclide dans le pire cas, et pour quelles paires d’entiers ce pire cas est-il atteint ? C’est une vraie question mathématique, et la réponse est un théorème publié par Gabriel Lamé dans une note à l’Académie des Sciences. La démonstration tient en quelques lignes, elle est accessible au lycée, et la conclusion fait apparaître la suite de Fibonacci là où on ne l’attendait pas.

L’algorithme d’Euclide

Si tu n’as jamais vraiment manipulé l’algorithme d’Euclide, voici l’idée. Tu cherches le PGCD (plus grand commun diviseur) de deux entiers $a$ et $b$ avec $a > b > 0$ . Au lieu de chercher tous les diviseurs des deux nombres et de prendre le plus grand, on s’appuie sur une propriété très simple :

Autrement dit, on remplace le couple $(a, b)$ par le couple $(b, r)$ où $r$ est le reste de la division euclidienne de $a$ par $b$ , et le PGCD ne change pas. Comme $r < b$ , les nombres deviennent plus petits à chaque étape, l’algorithme s’arrête forcément, et le dernier diviseur non nul donne le PGCD recherché.

Prenons un exemple concret avec $\text{pgcd}(48, 18)$ :

\displaystyle 48 = 2 \cdot 18 + 12, \quad 18 = 1 \cdot 12 + 6, \quad 12 = 2 \cdot 6 + 0.

Trois divisions, le reste devient nul, on s’arrête. $\text{pgcd}(48, 18) = 6$ . La mécanique est toujours la même : à chaque étape, une division euclidienne, et le couple devient strictement plus petit.

Pour t’approprier l’algorithme avec tes propres entiers, le composant ci-dessous te permet de saisir n’importe quelle paire $(a, b)$ et de voir la trace complète des divisions, étape par étape :

a = b =

Tester :

Saisis deux entiers et clique sur « Calculer le PGCD », ou choisis une paire prédéfinie ci-dessus.

L'algorithme d'Euclide remplace le couple (a, b) par (b, r) à chaque étape, où r est le reste de la division euclidienne. L'algorithme s'arrête quand le reste devient nul. Le PGCD est alors le diviseur de la dernière division.

Tu peux jouer avec : essaie par exemple $\text{pgcd}(120, 35)$ , $\text{pgcd}(1000, 7)$ , et puis compare $\text{pgcd}(89, 100)$ avec $\text{pgcd}(89, 55)$ . Le premier prend trois étapes, le second en prend neuf. Ce qui surprend, c’est que la paire la plus lente n’est pas la plus grande : $89$ et $55$ sont tous les deux plus petits que $100$ , et pourtant l’algorithme rame trois fois plus longtemps. Le nombre d’étapes ne dépend pas seulement de la taille des entrées, mais aussi de leur structure. C’est cette observation qui conduit Lamé à sa question.

La question de la rapidité

L’algorithme d’Euclide est rapide. Pour des entiers de taille raisonnable, on parle de quelques étapes, pas de dizaines. Mais à quel point exactement ? Existe-t-il une borne précise sur le nombre d’étapes en fonction de la taille des entrées ?

Si tu regardes la trace d’un algorithme d’Euclide générique, tu remarques que le second entier décroît rapidement à chaque étape. On peut même montrer que le second entier est divisé par au moins $\sqrt{2}$ toutes les deux étapes, ce qui ressemble à une décroissance géométrique. Cela suggère que le nombre d’étapes croît comme le logarithme de l’entrée : pour des entrées de plus en plus grandes, le nombre d’étapes augmente, mais beaucoup plus lentement que l’entrée elle-même.

Le nombre maximal d’étapes croît comme le logarithme de

b

. Passer de

b = 10

b = 100

multiplie l’entrée par dix mais n’ajoute que cinq étapes ; passer de

b = 100

b = 1000

multiplie encore par dix et n’ajoute encore que quatre ou cinq étapes.

Cette intuition logarithmique ne suffit pas pour faire de la mathématique propre. Il faut une borne précise, démontrée rigoureusement, et il faut savoir quelle paire $(a, b)$ atteint le pire cas pour une taille donnée. C’est exactement la question que Gabriel Lamé se pose en 1844.

1844 : Gabriel Lamé entre en scène

Gabriel Lamé est l’un de ces mathématiciens français du dix-neuvième siècle qu’on connaît surtout par les morceaux de mathématiques qui portent son nom : la fonction de Lamé, les coefficients de Lamé en élasticité, et bien sûr le théorème dont on parle ici. Né en 1795 à Tours, il sort de l’École polytechnique en 1817, fait l’École des Mines, puis passe une douzaine d’années à enseigner à l’Institut des voies de communication de Saint-Pétersbourg avec son collègue Émile Clapeyron, avant de revenir à Paris en 1832 où il succède à César Despretz sur la chaire de physique de Polytechnique. Ses travaux couvrent l’élasticité, la théorie de la chaleur, la théorie des nombres, et il sera élu à l’Académie des sciences en 1843. La chaire de physique mathématique de la Sorbonne, il l’obtiendra plus tard, en 1851.

C’est dans ce dernier domaine qu’il publie en 1844 sa célèbre note. Il s’agit d’une simple communication aux Comptes Rendus de l’Académie des Sciences, deux pages et demie de raisonnement par récurrence, qui va passer étonnamment inaperçue pendant un siècle avant d’être reconnue comme le tout premier théorème de complexité algorithmique.

Pour situer le moment historique : 1844, c’est l’année où Samuel Morse envoie son premier télégramme entre Washington et Baltimore. La théorie des algorithmes telle qu’on la connaît aujourd’hui n’existe pas. Le mot “algorithme” est encore réservé, dans le vocabulaire académique, à l’algorithme d’Euclide lui-même et à quelques procédés arithmétiques élémentaires. Personne ne parle de “complexité” ni de “borne supérieure du nombre d’opérations”. Lamé démontre pourtant un résultat qui aujourd’hui se classerait directement dans la théorie de la complexité moderne.

Le théorème de Lamé

Voici l’énoncé que Lamé démontre, formulé dans le langage moderne.

Théorème (Lamé, 1844). Soient $a > b \geq 1$ deux entiers. Si l’algorithme d’Euclide appliqué au couple $(a, b)$ termine en exactement $k$ étapes, alors $b \geq F_{k+1}$ , où $F_k$ désigne le $k$ -ième nombre de Fibonacci.

L’énoncé est simple en apparence, mais il dit quelque chose de très fort. Il borne le nombre d’étapes par une fonction du second entier $b$ uniquement, et cette fonction est l’inverse de Fibonacci. Comme la suite de Fibonacci croît géométriquement avec ratio $\varphi \approx 1{,}618$ , l’inégalité $b \geq F_{k+1}$ se réécrit, en passant au logarithme :

\displaystyle k \leq \log_\varphi(b) + \text{constante} \approx 4{,}785 \cdot \log_{10}(b) + \text{constante}.

Le nombre d’étapes est donc au pire proportionnel au nombre de chiffres de $b$ . Pour un entier $b$ de cent chiffres, l’algorithme d’Euclide termine en moins de cinq cents étapes, et pour un entier de mille chiffres, en moins de cinq mille. Cette borne logarithmique, c’est exactement ce qu’on cherche en complexité algorithmique : un coût qui croît raisonnablement même quand l’entrée explose.

Le plus remarquable dans le théorème, c’est la précision de cette borne. Lamé ne dit pas seulement “il existe une constante $c$ telle que…” : il dit exactement quels sont les pires cas, et pour quelles valeurs de $k$ ils sont atteints. Les pires cas sont les paires de Fibonacci consécutifs. La borne est donc atteinte par une famille explicite d’entrées, ce qui en fait un résultat à la fois théorique et constructif.

La démonstration par récurrence

La démonstration tient en quelques lignes par récurrence sur le nombre d’étapes $k$ . Voici deux manières de la présenter, qui aboutissent au même résultat mais regardent l’algorithme dans des sens opposés. La première lit le couple $(a, b)$ comme un objet qu’on déforme à chaque division. La seconde suit la suite des restes successifs et raisonne directement sur leur trace.

Démonstration par invariant double

Le truc de cette première démonstration, c’est qu’il faut démontrer un peu plus que l’énoncé brut : on prouve par récurrence un invariant double, qui se propage de manière propre.

Démontrer le couple d’inégalités est plus solide que la seule inégalité sur $b$ , et c’est précisément ce double énoncé qui permet à la récurrence de fonctionner.

Initialisation ( $k = 1$ ). Si l’algorithme termine en une seule étape, alors la première division donne $a = q \cdot b + 0$ . La condition $a > b$ force $q \geq 2$ , sinon on aurait $q = 1$ et donc $a = b$ , ce qui contredit l’hypothèse. Donc $a \geq 2b \geq 2 = F_3$ , et $b \geq 1 = F_2$ . L’invariant double est vrai au rang $k = 1$ .

Hérédité. Suppose l’invariant vrai pour tout couple qui termine en $k - 1$ étapes. Considère un couple $(a, b)$ qui termine en $k$ étapes. La première division donne $a = q \cdot b + r$ avec $r \geq 1$ (sinon l’algorithme se serait arrêté en une seule étape) et $r < b$ . Le couple $(b, r)$ subit alors les $k - 1$ étapes restantes, et par hypothèse de récurrence appliquée à ce couple, on a à la fois $b \geq F_{k+1}$ et $r \geq F_k$ . Comme $q \geq 1$ , on en déduit $a = q \cdot b + r \geq b + r \geq F_{k+1} + F_k = F_{k+2}$ , en utilisant la définition même de la suite de Fibonacci. L’invariant est démontré au rang $k$ .

C’est la démonstration la plus compacte des deux. Tu peux la décrire à l’oral en deux ou trois minutes, et c’est probablement celle que tu utiliseras pour ton grand oral.

Démonstration par les restes successifs

L’autre angle consiste à raisonner directement sur la suite des restes produite par l’algorithme. C’est une lecture plus algorithmique, qui colle de près à ce qu’un programme calcule étape par étape.

Notons $r_0 = a$ , $r_1 = b$ , et plus généralement $r_{i+1} = r_{i-1} \bmod r_i$ pour $i \geq 1$ . La suite $(r_i)$ est strictement décroissante, et l’algorithme termine lorsqu’un reste devient nul. Si l’algorithme prend $k$ étapes, alors $r_{k+1} = 0$ et $r_k = \text{pgcd}(a, b) \geq 1$ .

L’objectif est de démontrer par récurrence descendante, de l’indice $i = k$ vers $i = 0$ , l’inégalité

\displaystyle r_i \geq F_{k - i + 2}.

Quand on appliquera cette inégalité à $i = 1$ et $i = 0$ , on retrouvera exactement l’énoncé du théorème : $b = r_1 \geq F_{k+1}$ et $a = r_0 \geq F_{k+2}$ .

Initialisation. Pour $i = k$ , le reste $r_k$ est le PGCD de $a$ et $b$ , donc $r_k \geq 1 = F_2 = F_{k - k + 2}$ . Pour $i = k - 1$ , la dernière division s’écrit $r_{k-1} = q_k \cdot r_k + r_{k+1} = q_k \cdot r_k$ puisque $r_{k+1} = 0$ . La décroissance stricte $r_{k-1} > r_k$ impose $q_k \geq 2$ , donc $r_{k-1} \geq 2 \cdot r_k \geq 2 = F_3 = F_{k - (k-1) + 2}$ . L’inégalité est donc vraie aux deux premiers rangs de la récurrence.

Hérédité. Suppose démontré $r_{i+1} \geq F_{k - i + 1}$ et $r_i \geq F_{k - i + 2}$ . La division $r_{i-1} = q_i \cdot r_i + r_{i+1}$ avec $q_i \geq 1$ donne

\displaystyle r_{i-1} \geq r_i + r_{i+1} \geq F_{k - i + 2} + F_{k - i + 1} = F_{k - i + 3}.

C’est exactement l’inégalité voulue à l’indice $i - 1$ .

À la fin de la récurrence, pour $i = 1$ , on obtient $r_1 = b \geq F_{k+1}$ . Et pour $i = 0$ , on obtient $r_0 = a \geq F_{k+2}$ . C’est l’énoncé du théorème.

L’avantage pédagogique de cette présentation, c’est qu’elle correspond à ce que tu vois quand tu déroules l’algorithme à la main. Chaque reste successif est obligé de “dépasser” un Fibonacci de plus en plus grand à mesure qu’on remonte la trace. Pour la paire pgcd(89, 55), tu peux vérifier : les restes sont $89, 55, 34, 21, 13, 8, 5, 3, 2, 1, 0$ , et c’est exactement la suite de Fibonacci à l’envers. La borne du théorème est saturée, parce que chaque inégalité de la récurrence est ici une égalité.

L’argument, dans les deux versions, est court, élégant, et entièrement à portée d’un élève de Terminale. Tu peux le décrire à l’oral pendant ta présentation, ou le détailler sur ton brouillon de préparation pour t’en servir comme appui.

Pourquoi Fibonacci ? L’intuition géométrique

À ce stade, tu sais que Fibonacci est le pire cas et tu sais le démontrer. Reste une question d’un autre ordre, plus profonde : pourquoi intuitivement Fibonacci, et pas une autre suite ? Pourquoi sont-ce précisément ces nombres qui ralentissent l’algorithme au maximum ?

L’intuition est géométrique. Elle vient de la version originelle de l’algorithme d’Euclide, ce qu’on appelle l’anthyphérèse chez les Grecs, c’est-à-dire la “soustraction réciproque”. L’algorithme d’Euclide se voit alors comme une opération géométrique sur des rectangles, et c’est cette interprétation qui révèle pourquoi Fibonacci occupe une place si particulière.

Place un rectangle de dimensions $a \times b$ avec $a > b$ . Découpe le plus grand carré possible à l’intérieur, soit un carré $b \times b$ . Il reste un rectangle de dimensions $b \times r$ où $r = a \bmod b$ . Recommence avec ce rectangle restant : tu découpes le plus grand carré possible et tu itères, jusqu’à ce que le rectangle restant soit lui-même un carré. Le côté de ce dernier carré, c’est exactement le PGCD de $a$ et $b$ .

Cette construction est le pendant géométrique exact de l’algorithme d’Euclide. Chaque carré découpé correspond à une division euclidienne avec quotient $1$ , et quand le quotient vaut $q > 1$ , on découpe $q$ carrés du même côté en une seule étape. La question intéressante devient alors la suivante : pour quelle paire $(a, b)$ obtient-on le plus grand nombre d’étapes différentes ? La réponse tient en une phrase : c’est la paire qui ne consomme qu’un seul carré à chaque étape, autrement dit celle dont tous les quotients de la division euclidienne valent $1$ .

Or si tous les quotients valent $1$ , l’algorithme d’Euclide s’écrit $a = b + r$ , $b = r + r'$ , $r = r' + r''$ , et ainsi de suite. À chaque étape, le terme courant est la somme des deux termes suivants, ce qui se réécrit, en remontant la suite, comme la récurrence de Fibonacci. La paire qui maximise le nombre d’étapes est donc précisément celle où les côtés successifs des rectangles forment la suite de Fibonacci à l’envers. Pour deux Fibonacci consécutifs $F_{n+1}$ et $F_n$ , l’algorithme effectue $n - 1$ étapes différentes avant de terminer. Pour toute autre paire, on ne fait pas mieux : il y aura forcément au moins une division avec quotient $\geq 2$ , qui consomme plusieurs carrés en une seule étape.

C’est précisément ce que tu vois dans le composant ci-dessous, qui te permet de tester la construction géométrique pour différentes paires d’entiers et de comparer visuellement le nombre d’étapes :

Étapes révélées 9 / 9

Rectangle: 89 × 55
Étapes Euclide: 9
Carrés total: 10
PGCD: 1

Paire de Fibonacci consécutifs : tous les quotients valent 1, sauf le dernier. La spirale qui apparaît est la signature du pire cas de l'algorithme.

À chaque étape, on découpe le plus grand carré possible dans le rectangle restant. Pour les paires de Fibonacci consécutifs, chaque étape ne consomme qu'un seul carré, ce qui maximise le nombre d'étapes. Pour les autres paires, certaines étapes consomment plusieurs carrés d'un coup, et le total est plus court. C'est cette différence qui fait que Fibonacci est le pire cas.

Joue avec les presets. Pour la paire $(89, 55)$ , la disposition des carrés découpés forme la spirale de Fibonacci classique, celle qu’on retrouve dans tous les manuels et qu’on associe au nombre d’or. Cette spirale n’est pas une décoration : c’est exactement le pire cas géométrique de l’algorithme d’Euclide. La paire $(100, 63)$ , au contraire, ne donne que sept étapes différentes malgré des entiers plus grands, parce que l’algorithme tombe sur des quotients supérieurs à $1$ qui accélèrent la convergence. La spirale de Fibonacci, qu’on présente d’habitude comme une curiosité contemplative, est aussi la signature géométrique du résultat de Lamé.

L’héritage : Lamé et la complexité moderne

Le théorème de Lamé est isolé dans son siècle. Il faut attendre les années 1960 pour qu’on prenne conscience qu’il s’agit du premier résultat de complexité algorithmique formellement démontré. Pendant plus d’un siècle, il reste un résultat connu mais peu cité, classé en théorie élémentaire des nombres plutôt qu’en algorithmique. C’est Donald Knuth qui le réhabilite explicitement dans le second volume de The Art of Computer Programming, et qui dit en substance : Lamé a fait, en 1844, ce que nous croyons avoir inventé.

Du théorème de Lamé à la complexité moderne

graph LR
  A["Gabriel Lamé
1844"] --> B["Donald Knuth
1962"]
  B --> C["Cobham, Edmonds
1965"]
  C --> D["Stephen Cook
1971"]

Knuth fait le pont entre les mathématiques anciennes et l’informatique moderne. Cobham et Edmonds posent la même année les fondations de la théorie de la complexité, en définissant les classes de problèmes en temps polynomial. Cook, en 1971, introduit la notion de NP-complétude et complète l’édifice. C’est précisément à ce moment-là, plus de cent ans après Lamé, que la complexité algorithmique devient une discipline mature, et qu’on peut enfin replacer le théorème de Lamé dans son contexte théorique.

Ce double caractère, précurseur méconnu et résultat qui se classe directement dans la théorie moderne, distingue le théorème de Lamé. Il fait aussi de cet angle un sujet de grand oral particulièrement riche : tu peux y articuler à la fois de l’histoire des sciences, de la théorie des nombres, et de la culture algorithmique moderne.

De Lamé à RSA : un lien direct avec la cryptographie

L’algorithme d’Euclide ne sert pas seulement à calculer des PGCD pour le plaisir. Il est au cœur de l’arithmétique moderne, et il est utilisé tous les jours, des milliards de fois par seconde, dans les protocoles qui sécurisent Internet.

L’algorithme d’Euclide étendu, variante du précédent, permet de calculer non seulement le PGCD de $a$ et $b$ , mais aussi des coefficients $u$ et $v$ tels que $au + bv = \text{pgcd}(a, b)$ . C’est l’identité de Bézout, et elle a une conséquence directe : quand $\text{pgcd}(a, n) = 1$ , l’algorithme te donne immédiatement l’inverse modulaire de $a$ modulo $n$ , c’est-à-dire l’entier $u$ tel que $au \equiv 1 \pmod{n}$ .

Or l’inverse modulaire est précisément ce dont RSA a besoin pour générer ses clés. Quand on génère une clé RSA, on choisit deux grands nombres premiers $p$ et $q$ , on calcule $\varphi(n) = (p-1)(q-1)$ , et on choisit un exposant $e$ premier avec $\varphi(n)$ . La clé privée $d$ est alors l’inverse modulaire de $e$ modulo $\varphi(n)$ , calculé par l’algorithme d’Euclide étendu. Sans Euclide, pas de RSA. Et sans la borne logarithmique de Lamé, pas de garantie que ce calcul soit faisable en temps raisonnable, même pour des entiers de mille bits comme on en utilise en pratique.

L'héritage algorithmique de Lamé

graph TD
  A["Algorithme d'Euclide
(Euclide, ~300 av. JC)"]
  A --> B["Théorème de Lamé
(1844)
Borne en O(log b)"]
  A --> C["Algorithme d'Euclide étendu
Identité de Bézout"]
  B --> D["Garantie de complexité
Euclide en temps polynomial"]
  C --> E["Inverse modulaire
au ≡ 1 (mod n)"]
  D --> F["RSA
Génération de clés faisable"]
  E --> F
  F --> G["Sécurité TLS, paiements,
signatures numériques"]
  style A fill:#f5ead8,stroke:#8E6F3E,color:#1A1A1A
  style B fill:#e8f5e8,stroke:#27AE60,color:#1A1A1A
  style F fill:#f8e8e8,stroke:#C0392B,color:#1A1A1A
  style G fill:#f8e8e8,stroke:#C0392B,color:#1A1A1A

Quand tu mentionnes ce lien dans ton oral, tu rattaches Fibonacci à un sujet d’actualité (la cybersécurité) et tu ouvres vers d’autres angles que le jury connaît bien. Si tu veux creuser RSA en détail, l’article RSA et l’arithmétique qui protège Internet du blog explore ce sujet à fond.

Ton plan Grand oral, minute par minute

L’épreuve du Grand oral se déroule en deux temps de 10 minutes : un exposé en monologue, puis un échange avec le jury. Voici un plan détaillé pour la phase d’exposé. Ne dépasse pas les temps indiqués : un jury habitué pénalise les candidats qui s’éternisent sur l’introduction.

Exposé : 10 minutes

0:00 – 1:30 · Accroche

Compare le calcul de pgcd(89, 100) en trois étapes avec celui de pgcd(89, 55) en neuf étapes. Pose la question : pourquoi des entiers plus petits ralentissent-ils plus l'algorithme ?

1:30 – 3:00 · L'algorithme d'Euclide

Rappelle brièvement la mécanique de l'algorithme et le lemme central pgcd(a, b) = pgcd(b, a mod b). Quatre-vingt-dix secondes maximum, c'est juste pour fixer le contexte technique.

3:00 – 5:30 · L'énoncé et la démonstration

Énonce le théorème de Lamé : si l'algorithme prend k étapes, le second entier est minoré par le (k+1)-ième nombre de Fibonacci. Esquisse la démonstration par récurrence avec invariant double sur le couple. Le passage clé tient en une ligne : a ≥ b + r, et la somme de deux Fibonacci consécutifs donne le suivant.

5:30 – 7:00 · L'intuition géométrique

Décris à l'oral le découpage du rectangle a × b en carrés successifs. Explique que la paire qui découpe le plus de carrés différents est celle où tous les quotients valent 1, ce qui force la récurrence de Fibonacci. C'est l'image qui marque le jury.

7:00 – 9:00 · La portée moderne

Lamé en 1844 démontre, sans le savoir, le premier théorème de complexité algorithmique. Knuth le redécouvre dans les années soixante. L'algorithme d'Euclide étendu est au cœur de RSA, et la borne logarithmique garantit que la génération de clés est faisable en pratique.

9:00 – 10:00 · Ouverture

Ce qui te frappe dans ce résultat : qu'un théorème de 1844 anticipe une discipline qui naîtra plus d'un siècle plus tard. Lien éventuel avec ton parcours, ta spécialité NSI, ta curiosité pour l'histoire des sciences.

Ta checklist avant l’oral

Avant ton passage, vérifie que...

Tu sais énoncer l'algorithme d'Euclide et démontrer le lemme pgcd(a, b) = pgcd(b, a mod b)
Tu sais énoncer précisément le théorème de Lamé : si l'algorithme prend k étapes, le second entier est minoré par le (k+1)-ième Fibonacci
Tu sais dérouler la démonstration par récurrence avec invariant double, sans tes notes
Tu peux décrire à l'oral l'intuition géométrique du découpage en carrés successifs
Tu sais expliquer pourquoi la paire (89, 55) prend exactement 9 étapes en utilisant les Fibonacci consécutifs
Tu connais la chronologie : Lamé 1844, Knuth 1962, Cobham et Edmonds 1965, Cook 1971
Tu sais expliquer le lien avec RSA via l'algorithme d'Euclide étendu et l'inverse modulaire
Tu peux répondre à au moins trois questions imprévues sur la complexité, la rigueur, ou la portée historique
Tu sais ce que tu admets (la formule logarithmique précise, les détails de RSA) et tu l'assumes

Pour conclure

Le théorème de Lamé n’est pas un sujet de grand oral facile. C’est un sujet qui tient la route mathématiquement, avec une vraie démonstration, un vrai théorème, et un vrai pont vers l’histoire des sciences et l’algorithmique moderne.

Si tu maîtrises la démonstration par récurrence avec son invariant double, que tu sais raconter l’intuition géométrique avec la spirale de Fibonacci, et que tu fais le lien avec la cryptographie moderne en restant honnête sur ce que tu admets, tu as un grand oral solide. Pas brillant par sa forme, mais solide par son fond. C’est exactement ce qu’un jury attend.

Sources

Lamé, G. (1844). Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers. Comptes Rendus de l’Académie des Sciences, tome 19, séance du 13 mai 1844, pp. 867-870.
Knuth, D. E. (1969, 1973, 1981, 1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms, section 4.5.3 “Analysis of Euclid’s Algorithm”. Addison-Wesley.
Shallit, J. (1994). Origins of the analysis of the Euclidean algorithm. Historia Mathematica, 21(4), pp. 401-419.
Cobham, A. (1965). The intrinsic computational difficulty of functions. Proceedings of the 1964 International Congress for Logic, Methodology, and Philosophy of Science, pp. 24-30.
Edmonds, J. (1965). Paths, trees and flowers. Canadian Journal of Mathematics, 17, pp. 449-467.
Wikipedia : Algorithme d’Euclide, Théorème de Lamé, Gabriel Lamé.