Algorithme PQa

Cet algorithme dû à Lagrange donne le développement en fraction continue d'un nombre quadratique (u+√D)/v, avec u, v, D entiers, D non carré.

D :     u :     v :          (u=0, v=1 pour résoudre x²-Dy²=±1)
Valeur des réduites     nombre de cycles supplémentaires

Fonctionnement

L'algorithme nécessite v divisant D-u².
Si v ne divise pas D-u², on peut remplacer u par u|v|, D par Dv² et v par v|v| et alors v|v| divise bien Dv²-u²v², tout en représentant le même nombre quadratique.

Posons U0=u, V0=v, a=E[√D], avec la notation E[x]=partie entière de x.
Et les variables suplémentaires X, Y, P    X-1=-u, X0=v     Y-1=1, Y0=0     P-1=0, P0=1

Puis itérons les formules pour i≥0:

    ai=E[(Ui+√D)/Vi]=E[(Ui+a)/Vi]
    Ui+1=aiVi-Ui     Vi+1=(D-Ui+1²)/Vi,
    (X,Y,P)i+1=ai(X,Y,P)i+(X,Y,P)i-1

En s'arrêtant quand la suite Vn devient périodique.
Les ai sont les termes de la fraction continue,   Pi/Yi les réduites   et Xi²-DYi²=(-1)iV0Vi

 

Accueil Arithmétiques Géométrique Divers Thèmes Scripts Jeux Exercices Mail English version Sujet précédent Sujet suivant