Algèbre effective : autour de l'algorithme d'Euclide

On écrit 10ⁱ= r + q b avec r un entier positif strictement inférieur à b. Donc,

La partie fractionnaire du développement décimal de est égale au développement décimal de et il ne reste plus qu'à réfléchir à l'effet de la multiplication par une puissance de 10 sur le développement ...

Supposons le dénominateur b premier à 10. Si P est l'ordre de 10 modulo b, le nombre de valeurs différentes que prend 10ⁱ modulo b pour i entier est égale à P.

Remarque

En utilisant cette remarque et en regardant simplement les développements décimaux à gauche, on peut deviner quel est l'ordre de 10 modulo . Bien sûr, cela se voit aussi avec les valeurs de droite.

{subsection}

Et maintenant, comment calculer un chiffre quelconque du développement décimal :

I-2 Dénominateur fixé

I-3 Calculer un chiffre quelconque

Comment calculer un chiffre quelconque du développement décimal par exemple le n-ième, alors qu'on ne possède qu'une calculette avec peu de chiffres après la virgule ?

Objectif

Résultat

pour amener ce chiffre en première position après la virgule, on multiplie par .
Par exemple, 10⁷ 0.098795181 =987951.81
On écrit avec r un entier positif strictement inférieur à b. Donc,

Le premier chiffre après la "virgule" de est donc égal au premier chiffre après la virgule de . Il suffit donc de calculer le premier chiffre (sur la gauche) du quotient de 10r par b.

Exercice

Arithmétique du développement

Arithmétique du développement, suite

Calculer le développement

I-3 Calculer un chiffre quelconque

II Application de l'algorithme de Bezout

II-1 Retrouver une fraction à partir de son développement décimal

II-2 Un exemple à partir d'un rationnel

II-3 Est-ce un rationnel ?

II-5 Retrouver un entier par ses classes résiduelles, même si certaines sont fausses

II-6 Un exemple

II-1 Retrouver une fraction à partir de son développement décimal

On connaît un nombre rationnel positif par son développement décimal à près. On sait d'autre part que son dénominateur est borné par T. Calculer x.

Objectif

Analyse

Soit N = 10^k. Soit b la partie entière de Nx. Elle est inférieure à N. Disons que l'approximation était donnée par défaut. on a donc

et donc

0 < s N - t b <t

On peut donc écrire s N - t b = r avec r un entier vérifiant 0 < r < t < T. On cherche donc des solutions de l'équation

x = N y + b z

vérifiant certaines inégalités.

Résultat

On fait tourner l'algorithme de Bezout sur N et b. Soit r_i le premier reste inférieur ou égal à T. On obtient une équation

r_i = s_i N + t_i b

Si , alors a bien les propriétés voulues pour x.

II-1 Retrouver une fraction à partir de son développement décimal

II-2 Un exemple à partir d'un rationnel

Dans l'exemple ci-dessous que vous pouvez changer,

Exemple

le nombre rationnel choisi à l'avance est et son développement décimal à près est 0,.

Voyez-vous le rationnel ?
A-t-on la majoration 2 ²< 10³ ? Vous pouvez augmenter ou diminuer la précision.

II-2 Un exemple à partir d'un rationnel

II-3 Est-ce un rationnel ?

Exemple

Vous pouvez ici vous donner

Vous cherchez un rationnel dont le développement décimal est donné à près par 0,32458919. Si vous voulez le trouver à coup sûr ou être sûr qu'il n'existe pas, vous devez imposer que son dénominateur est borné par ? Voyez-vous le rationnel ? Existe-t-il ?

Pour voir la solution théorique, voir ce théorème .

Exercice

Recherche d'un rationnel

II-3 Est-ce un rationnel ?

II-4 Un théorème pour pouvoir répondre

II-4-1 L'algorithme de Bezout

II-4-2 Le théorème en vue

II-4-1 L'algorithme de Bezout

Soient a et b des entiers positifs avec . Définissons

les entiers r₀, ... , et q₁, ... , q_m avec de la manière suivante : a = r₀, b = r₁, ... , avec et . ; les q_i sont strictement positifs.
les entiers s₀, s₁, ... , et t₀, t₁, ... , par s₀ = 1, t₀ = 0, s₁ = 0, t₁ = 1 et

Alors

r_i = s_i a + t_i b pour tout i = 0 ... m+1 ;
;
pgcd(s_i,t_i) = 1 pour tout i = 0 ... m+1 ;
et pour tout i = 0 ... m ; et pour tout i = 1 ... m
et pour tout i = 1 ... m+1.

On peut disposer les calculs précédents de la manière suivante :

où q₃ est par exemple le quotient de r₂ par r₃ et où la ligne L₄ est obtenue comme la ligne L₂ - q₃ fois la ligne L₃.

On peut supposer . On définit et comme précédemment, ainsi que les suites définies par récurrence :

t₀ = 0, t₁ = 1, , .
s₀ = 1, s₁ = 1, , .

Alors pour tout

et on peut voir l'algorithme d'Euclide étendu comme une suite d'opérations élémentaires sur les lignes de ce système; donc, pour tout , on a

où la dernière matrice est l'identité. On en déduit que et donc

Mais cet inverse est aussi le produit des

dont tous les coefficients sont positifs, donc tous ses coefficients sont positifs ! On en déduit

Donc , et en particulier

	a
	b

(Rappelons que r_i est strictement décroissante avec r_m = pgcd (a, b) et .)

Les t_i sont de signe alterné, ce qui se voit en comparant les matrices égales

On a donc . Comme q_i> 0, nécessairement . On fait de même pour les s_i.

On démontre que le coût est en pour a et b inférieurs à N.

II-4-1 L'algorithme de Bezout

II-4-2 Le théorème en vue

[ t_i est alors non nul]. On pose

Soient R, T, N, b des entiers strictement positifs tels que On fait tourner l'algorithme d'Euclide étendu avec comme entrées a = N et b. Soit l'unique indice i compris entre 1 et m + 1 tel que

Théorème

Soient R, T, N, b des entiers strictement positifs tels que Soient trois entiers r, s, t tels que r = sN + tb, , . Alors, avec les notations précédentes, le triplet (r, s, t) est un multiple entier de (r', s', t').

Attention, on n'affirme pas qu'il y a une solution, il faut ensuite vérifier que et que est inférieur à T. Par contre, si (r',s',t') ne fournit pas une solution sous les conditions de l'énoncé , c'est qu'il n'y en a pas.

Soient r, s, t trois entiers relatifs vérifiant

Les trois vecteurs , et appartiennent au plan d'équation x = N y + b z. On a donc

Comme , les coefficients m et n sont entiers.

Supposons m et n de même signe (ou nuls). Si n est non nul, , (car r_i, sont positifs), ce qui est impossible. Donc
Si m et n sont de signe contraire, nécessairement puisque t_i et sont de signe différent et que . Donc

et
-N/2 < r_i t - r t_i < N

Les trois vecteurs colonne de la matrice sont liés, leur déterminant est nul et le déterminant de est congru à 0 modulo N :

Finalement r_i t - r t_i = 0. Le vecteur v est combinaison linéaire de v_i et de . Comme v et v_i appartiennent à un plan qui ne contient pas e, ils sont colinéaires.

Ce qui termine la démonstration.

Montrer que le théorème précédent donne un algorithme pour déterminer un rationnel connaissant une borne pour son dénominateur et le début de son développement décimal sous certaines conditions. Montrer que le coût de cet algorithme de recherche d'un rationnel est en . Il est donc au pire quadratique en la taille de N.

Exercice

On se donne donc une puissance de 10, N = 10ⁿ. On cherche un rationnel inférieur à 1 dont on connaît le développement décimal à l'ordre n (par défaut ou par excès) et dont on sait que son dénominateur est inférieur à T.

On applique le théorème précédent avec R = T. On suppose que . Si le rationnel existe, il s'agit de -s_i/t_i avec . Mais il faut vérifier que . Si cela n'est pas le cas, c'est qu'il n'y a pas de solution.

On a prouvé en particulier qu'il existe au plus un seul rationnel dont le développement décimal à l'ordre n est donné et de dénominateur borné par .

II-4-2 Le théorème en vue

II-5 Retrouver un entier par ses classes résiduelles, même si certaines sont fausses

On a codé un entier x en calculant ses classes résiduelles modulo des entiers N₁, ... , N_r premiers entre eux deux à deux : c(x) = (x₁, ... , x_r). L'entier est supposé plus grand que x. Mais dans la transmission de c(x), des erreurs sont survenues. Pas trop quand même, au plus L des (x₁, ... , x_r) sont faux. Retrouver cependant x.

Objectif

Résultat

On suppose que x est inférieur à un entier Z fixé. Soit P une borne supérieure pour le produit de L parmi les entiers N₁, ... , N_r (par exemple, le produit des L plus grands). On suppose que N > 4P² Z.

Soit c₁(x) = (y₁, ... , y_r) les classes transmises effectivement. Par le lemme chinois, il existe un entier y vérifiant

pour tout i. On applique l'algorithme d'Euclide étendu à l'entier N et à y. Soit i le plus grand entier tel que le reste r_i obtenu par l'algorithme soit inférieur ou égal à Z P. On pose r' = r_i, s' = s_i, t' = t_i.

Théorème

Si t' divise r', z = r'/t' est une solution possible.

On démontre que le coût est en .

Soit t le produit des N_i pour lesquels la transmission de x_i est fausse. On ne connaît bien sûr pas encore t. Par définition de P, t est inférieur ou égal à P.

Posons r = t z où z est l'entier cherché (le vrai message). Par hypothèse, z est inférieur à Z, donc

D'autre part

En effet, r et ty sont tous deux congrus à 0 modulo N_i si N_i est mauvais, (dans ce cas, N_i divise t) ; pour N_i bon, comme r = tx et ty sont bien congrus modulo N_i. Soit s l'entier tel que

r = ty + sN

Comme , et , on peut appliquer le théorème : (r, s, t) est un multiple entier de (r', s', t') et

z = r/t = r'/t'

Si t' divise r', l'entier r'/t' est la solution cherchée. Sinon, c'est qu'il y a d'autres fautes dans la transmission du message.

Erreur dans un message Vous pouvez regarder l'exemple avant.

Exercice

II-5 Autour du lemme chinois

II-6 Un exemple

On sait que le message est inférieur à NaN et qu'il y a au plus une erreur. Les classes résiduelles transmises sont

mod 4
mod 5
mod 7
mod 11
mod 23

Par le lemme chinois , on trouve que l'entier transmis est . L'algorithme d'Euclide appliqué à 11×4×23×5×7 = et donne

Regardons la première ligne où le reste (colonne de gauche) est strictement inférieur à NaN =. Le nombre cherché est / = NaN .

II-6 Un exemple

III Fractions rationnelles

III-1 Approximant de Padé

Maintenant, nous allons voir quelques analogies du côté des fractions rationnelles.

III-2 Un exemple

III-3 Séries de Laurent

III-4 Les coefficients

III-1 Approximant de Padé

Soit F un corps et f une série formelle

Définition

avec f_i dans F. Un (k, n - k)-approximant de Padé de f est une fraction rationnelle telle que

x ne divise pas t
,

Soit f un polynôme de degré strictement inférieur à n et k un entier strictement inférieur à n. On exécute l'algorithme d'Euclide étendu pour xⁿ et f. Soient r_i les restes successifs obtenus. La suite des est strictement décroissante. Soit j le plus petit entier tel que . On pose r' = r_j, s' = s_j, t' = t_j avec les notations de l'algorithme :

r' = s'xⁿ+ t'f

Théorème

Avec les notations précédentes, les polynômes r' et t' vérifient

Pour tous polynômes s et t tels que r = s xⁿ+ t f avec , , on a (r, s, t) = w (r', s', t') pour w un polynôme.

Ainsi, si est irréductible, c'est un (k, n - k)-approximant de Padé.

Exercice !

Exercice

Approximant de Padé

III-1 Approximant de Padé

III-2 Un exemple

Dans le dessin qui suit, on a représenté sur l'intervalle [-2,2] la différence entre (1+3x)^1/3 et un approximant de Padé

Exemple

Les égalités suivantes permettent de déterminer des approximants de Padé du polynôme de Taylor de (1+3x)^1/3 d'ordre 4 :

f =

III-2 Un exemple

III-3 Séries de Laurent

L'ensemble des séries de Laurent renversées forme un anneau appelé anneau des séries de Laurent renversées et noté

Définition

Une série formelle à coefficients dans un anneau R est une expression formelle de la forme f = a₀ + a₁ X + ... a_n Xⁿ+ ... avec les
Une série de Laurent est une expression formelle de la forme pour un entier relatif m.
Une série de Laurent renversée est une expression formelle de la forme .

On peut définir le degré d'une série de Laurent inversée f comme le plus grand entier m tel que a_m soit non nul ; et le coefficient dominant comme a_m ; on peut aussi définir la somme et le produit de deux séries de Laurent renversées

Définition

Remarque

Une série de Laurent renversée avec a un inverse si et seulement si son coefficient dominant a_m est inversible dans l'anneau des coefficients. Autrement dit, si F est un corps, est un corps.

L'analogie avec le développement décimal des réels est clair.

Pour voir une fraction rationnelle comme une série de Laurent renversée lorsque F est un corps, on écrit le numérateur et le dénominateur en mettant en facteur leur terme de plus haut degré, puis on fait le quotient.

= () + ...

III-3 Séries de Laurent

III-4 Les coefficients

On désire calculer le développement d'une fraction rationnelle : par exemple, étant donné k un entier positif, on veut calculer le coefficient de .

Résultat

On calcule avec .

Le coefficient de est le résidu de : Si , c'est le quotient des coefficients dominants de h et de t ; si , c'est 0.

Le coefficient cherché est le résidu (c'est-à-dire coefficient de 1/x) de . Comme , on a

Exemple

On a x²⁸() mod .

Le coefficient de dans vu comme élément de est .

Exercice

Trouver un coefficient

III-4 Les coefficients

IV L'algorithme d'Euclide : son coût

IV-2 Nombres de Fibonacci

Avant de commencer, rappelons quelques notations et coûts des opérations élémentaires

IV-1 Combien ça coûte ?

IV-3 Analyse de l'algorithme d'Euclide

IV-4 Pgcd étendu

IV-1 Combien ça coûte ?

la taille de a. Justification: le nombre de chiffres de a, écrit en base B est , donc la taille est liée au nombre de chiffres, sans pour autant dépendre de la base de numération, ni de la représentation des entiers. On rajoute 1 pour assurer que et donc pouvoir écrire qu'une constante est . Remarquons aussi que implique .

Pour , on note

Si , alors les algorithmes de l'école primaire (en comptant les opérations élémentaires sur les chiffres) montrent que

le calcul de a un coût
le calcul de a un coût
le calcul de (q,r), quotient et reste de la division euclidienne de a par b ( ), a un coût soit .

{subsection}

Les nombres de Fibonacci permettent d'analyser le coût de l'algorithme d'Euclide.

IV-1 Combien ça coûte ?

IV-2 Nombres de Fibonacci

permettent de calculer les nombres de Fibonacci.

Les F_i sont les nombres de Fibonacci définis par la récurrence linéaire

Les équations

Analyse [calcul récursif de F_n.]

Soit C_n une majoration du coût du calcul d'un F_i pour et m_n une majoration de celui nécessaire pour multiplier deux entiers inférieurs à . Les équations précédentes impliquent que

pour tout . Comme , il a O(n) chiffres, et la multiplication naïve donne

m_n = O(n²)

En choisissant , on obtient C_n = O(n²).

Plus généralement, sous l'hypothèse pour , on obtient

C_n = O(m_n)

car n = O(m_n).

Remarque

Si on pose , alors les relations de récurrences ci-dessus montrent que T_n se calcule facilement en fonction de :

Si t_n majore le coût du calcul de , on a (la multiplication par 2 est une addition).

Gros avantage : l'option remember n'est plus nécessaire, puisque aucun résultat n'est calculé plusieurs fois. Le coût en mémoire est bien moindre.

IV-2 Nombres de Fibonacci

IV-3 Analyse de l'algorithme d'Euclide

Étant donnés , l'algorithme calcule leur pgcd (a,b).

Pour , on définit le pgcd (a,b) de a et b comme le générateur positif de l'idéal . En particulier (0,0) = 0.

Algorithme

Fini? . Si b = 0, renvoyer a.
division euclidienne . Poser (dans cet ordre) , a := b, b := r, et revenir à l'étape 1.

Les valeurs successives de b forment une suite décroissante (b_i) dans . Cette suite est strictement décroissante tant que . Il existe donc i tel que b_i = 0 (sinon on aurait une suite strictement décroissante dans ). Donc l'algorithme termine. On vérifie facilement que la valeur de retour est (a,b).

Étant donnés , l'algorithme calcule leur pgcd (a,b).

La formulation récursive est plus élégante, mais bien sûr équivalente:

Algorithme

Si b = 0, renvoyer a.
Renvoyer pgcd .

Théorème

Soit et a, b deux entiers a > b > 0 tels que l'algorithme d'Euclide appliqué à (a,b) nécessite exactement n divisions, et tels que a soit minimal pour ces conditions. Alors

où les F_i sont les nombres de Fibonacci définis par la récurrence linéaire

F₀ = 0, F₁ = 1.

En appliquant Euclide au couple proposé, on obtient successivement

soit exactement n divisions. Réciproquement, soit (a,b) satisfaisant les conditions de l'énoncé et notons , x_n = b, ... , x₀ = 0 la suite des 2 données, suivies des n restes calculés par Euclide. Par récurrence, on a pour tout . Soit le quotient de la division euclidienne de par x_i; on a

On en déduit que pour tout par récurrence. Comme a est minimal, on en déduit , puis que les quotients successifs sont tous égaux à 1. Ainsi x_i = F_i, et en particulier b = F_n.

Soit F_n le n-ème nombre de Fibonacci, défini ci-dessus, et

Lemme

les solutions de l'équation x²= x+1. On a

L'équation caractéristique de la récurrence x²= x + 1 admet pour solution le nombre d'or et son conjugué. Donc, il existe des constantes universelles a et b telles que

En posant F₀ = 0, F₁ = 1, on trouve

Si a > b > 0, le nombre d'étapes d'Euclide appliqué à (a,b) est majoré par

Corollaire

Si on a n - 1 divisions, on obtient

soit

(puisque ) et

Si , le coût du calcul de (a,b) est

Corollaire

En fait, on peut facilement faire mieux :

Lemme

Si , le coût du calcul de (a,b) est

On peut supposer que a > b > 0. Supposons, qu'on ait exactement n divisions; on sait que . On note , x_n = b, , x₀ = 0, la suite des restes successifs, puis pour i=1, ... , n, la suite des quotients successifs correspondants; autrement dit,

pour . Le coût des divisions est dominé par

et on remarque ensuite que

Soit finalement un coût .

{subsection}

L'algorithme du pgcd étendu permet d'obtenir des relations du type Bezout :

s a + t b = (a, b)

IV-3 Analyse de l'algorithme d'Euclide

IV-4 Pgcd étendu