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

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

I Décimales des rationnels

Algorithme d'Euclide → I Décimales des rationnels

Voici le développement décimal de quelques rationnels :

= 000 ...

= 000 ...

= 000 ...


La première remarque est que ces développements semblent périodiques à partir d'un certain rang (cliquer sur l'étoile pour en voir d'autres).

I-1 Périodicité


Voici maintenant quelques développements à dénominateur fixé.
=
=
=
=
=
=
=
=
=
=
=

Que pouvez-vous conjecturer ? Comment prévoir la taille des décalages ?

I-2 Dénominateur fixé


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

I-3 Calculer un chiffre quelconque

Algorithme d'Euclide → I Décimales des rationnels

I-1 Périodicité

Théorème

Le développement décimal d'un rationnel (positif) est périodique à partir d'un certain rang. Plus précisément, écrivons le rationnel
comme une fraction irréductible avec p et q des entiers positifs et q premier à 10p. Soit n0 = max(a, b) et soit P l'ordre de 10 modulo q, c'est-à-dire le plus petit entier strictement positif tel que
Alors, le développement décimal de x est de la forme bm ... b0,a1 ... an ... avec pour n > n0.

Exercice


Développement périodique mixte
Périodicité et ordre de 10

I-2 Dénominateur fixé

Algorithme d'EuclideI Décimales des rationnels → I-2 Dénominateur fixé

Pouvez-vous prévoir de combien est le décalage quand il y en a un ? Pourquoi pour certains dénominateurs, le motif en vert se retrouve-t-il sur chaque ligne alors que pour d'autres dénominateurs cela n'est pas le cas ? Dans le tableau de droite, on a calculé les valeurs des puissances de 10 modulo . Cela peut peut-être vous aider à répondre.

Résultat

Soit r le reste de la division euclidienne de 10i par b. Le développement décimal de est obtenu en décalant la virgule (ou le point ici !) de i positions vers la droite dans le développement de et en prenant la partie fractionnaire du nombre obtenu.

Démonstration
On écrit 10i = 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 ...
Fin de la démonstration

Remarque

Supposons le dénominateur b premier à 10. Si P est l'ordre de 10 modulo b, le nombre de valeurs différentes que prend 10i modulo b pour i entier est égale à P.
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.

Algorithme d'EuclideI Décimales des rationnels → I-2 Dénominateur fixé

I-3 Calculer un chiffre quelconque

Algorithme d'EuclideI Décimales des rationnels → I-3 Calculer un chiffre quelconque

Objectif

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 ?

Résultat

  • pour amener ce chiffre en première position après la virgule, on multiplie par .
    Par exemple, 107 times 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
Algorithme d'EuclideI Décimales des rationnels → I-3 Calculer un chiffre quelconque

II Application de l'algorithme de Bezout

Algorithme d'Euclide → II Application de l'algorithme de Bezout
Algorithme d'Euclide → II Application de l'algorithme de Bezout

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

Algorithme d'EuclideII Application de l'algorithme de Bezout → II-1 Retrouver une fraction à partir de son développement décimal

Objectif

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.

Analyse

Soit N = 10k. 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
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
vérifiant certaines inégalités.

Résultat

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

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

Algorithme d'EuclideII 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

Algorithme d'EuclideII Application de l'algorithme de Bezout → II-2 Un exemple à partir d'un rationnel

Exemple

Dans l'exemple ci-dessous que vous pouvez changer,
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 2 < 10-2.1474836 × 109 ? Vous pouvez augmenter ou diminuer la précision.
Algorithme d'EuclideII Application de l'algorithme de Bezout → 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,10756. 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-4 Un théorème pour pouvoir répondre

Algorithme d'EuclideII Application de l'algorithme de Bezout → II-4 Un théorème pour pouvoir répondre
Algorithme d'EuclideII Application de l'algorithme de Bezout → II-4 Un théorème pour pouvoir répondre

II-4-1 L'algorithme de Bezout

Soient a et b des entiers positifs avec . Définissons
  • les entiers r0, ... , et q1, ... , qm avec de la manière suivante : a = r0, b = r1, ... , avec et ; les qi sont strictement positifs.
  • les entiers s0, s1, ... , et t0, t1, ... , par s0 = 1, t0 = 0, s1 = 0, t1 = 1 et
Alors
  1. ri = si a + ti b pour tout i = 0 ... m+1 ;
  2. ;
  3. pgcd(si,ti) = 1 pour tout i = 0 ... m+1 ;
  4. et pour tout i = 0 ... m ; et pour tout i = 1 ... m
  5. et pour tout i = 1 ... m+1.

On peut disposer les calculs précédents de la manière suivante :
q3 est par exemple le quotient de r2 par r3 et où la ligne L4 est obtenue comme la ligne L2 - q3 fois la ligne L3.
Démonstration
On peut supposer . On définit et comme précédemment, ainsi que les suites définies par récurrence :
  • t0 = 0, t1 = 1, , .
  • s0 = 1, s1 = 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
et
  
  

(Rappelons que ri est strictement décroissante avec rm = pgcd (a, b) et .)
Les ti sont de signe alterné, ce qui se voit en comparant les matrices égales
On a donc . Comme qi > 0, nécessairement . On fait de même pour les si.
Fin de la démonstration

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

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


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
[ ti est alors non nul]. On pose

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.
Démonstration
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 ri, sont positifs), ce qui est impossible. Donc

  • Si m et n sont de signe contraire, nécessairement puisque ti et sont de signe différent et que . Donc
    et

    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 ri t - r ti = 0. Le vecteur v est combinaison linéaire de vi et de . Comme v et vi appartiennent à un plan qui ne contient pas e, ils sont colinéaires.

Ce qui termine la démonstration.
Fin de la démonstration

Exercice

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.
Démonstration

On se donne donc une puissance de 10, N = 10n. 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 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 .
Fin de la démonstration

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


Objectif

On a codé un entier x en calculant ses classes résiduelles modulo des entiers N1, ... , Nr premiers entre eux deux à deux : c(x) = (x1, ... , xr). 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 (x1, ... , xr) sont faux. Retrouver cependant x.

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 N1, ... , Nr (par exemple, le produit des L plus grands). On suppose