On prend comme premier diviseur 46368, on peut alors faire 23 divisions.
D'où sort le 46368? Ben si on écrit sous forme décimale 75025/46368, on obtient 1,6180339889579... et là, miracle! on se souvient que le nombre d'or (sqrt(5)+1)/2 vaut environ 1,6180339887499... ( ben oui, on s'en souvient! ) et alors on se dit que ce serait sympa d'écrire 75025/46368 en fractions continues, ce qui donne :
75025/46368=1+1/(1+1/(1+1/(1+1/(....+1/1)...))) avec 23 traits de fraction.
Pour mémoire, le nombre d'or se développe en fractions continues avec une infinité de 1. A mon avis, si on remplace 75025 par N, en appelant phi le nombre d'or, le premier diviseur doit être parmi {E(N/phi), E(N/phi)+1)}. Si ça marche si bien avec 75025, c'est que justement 75025/46368 est la 23eme réduite du développement de phi (là je m'avance peut-être).

Une autre manière de voir la même chose est la suivante : On considère la suite de Fibonacci : u(0) = 0 , u(1) = 1, et, pour tout entier naturel n, u(n+2) = u(n+1) + u(n). Alors u(25) = 75025 et u(24)=46368.
Les 23 divisions s'écrivent donc : u(25) = u(24) + u(23), u(24) = u(23) + u(22), ..., u(4) = u(3) + u(2) soit 3 = 2 + 1 et enfin 2 = 2*1 + 0
Si l'on pose phi=(sqrt(5)+1)/2, alors on a aussi u(n) = sqrt(5)/5 * (phi^n - (-1/phi)^n) puisque -1/phi = -0,618, la limite de (-1/phi)^n lorsque n tend vers + l' infini est 0 et u(n+1)/u(n) tend vers phi..

Régis donne une solution en 23 divisions. Mais il n'était pas prouvé, comme demandé, que ce nombre était bien le maximum : ne pouvait-on faire plus de 23 divisions ?
Or, on peut prouver le résultat suivant : ( * )
Soit n le nombre de divisions nécessaires pour calculer le pgcd de deux entiers strictement positifs a et b, avec a > b, à l'aide de l'algorithme d'Euclide (c'est précisément ce que l'on fait avec les divisions). Soit d'autre part f la suite de Fibonacci définie de la manière suivante : f(0) =1 , f(1) = 2, et, pour tout entier naturel n, f(n+2)=f(n+1)+f(n).

Alors a >= f(n).

Application au problème posé : puisque 75025 = f(23), le nombre n de divisions est tel que f(n) <=f(23) ; et puisque la suite f est manifestement croissante, n <= 23. Donc, on ne peut faire plus de 23 divisions. Et j'ajoute, en plus, que prendre b=46368 est le seul moyen d'obtenir ces 23 divisions (étant entendu que le premier diviseur est compris entre 1 et 75025).

===

( * ) Voici la démonstration du théorème énoncé ci-dessus, auquel j'ajoute même un résultat supplémentaire concernant b. Je note (F_n ) la suite de Fibonacci également définie ci-dessus.

Th : Si on fait au moins n divisions, on a : a >= F_n et b>= F_n-1 .

Démo : L' algorithme d'Euclide appliqué à la division de a par b construit une suite décroissante de restes Rn tels que :
R₀ = a
R₁ = b ( a >=b )
R_i-1 = R_iQ_i + R_i+1

Or, Q_i >= 1, donc R_i-1 >= R_i + R_i+1. Mais on a aussi R_n+1 = 0, R_n >= F₀ et R_n-1 >= F₁ ( puisque F₀ = 0 et F₁ = 1 ). On montre donc de proche en proche que R₁ >= F_n-1 et R₀ >= F_n.