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

I Décimales des rationnels
II Application de l'algorithme de Bezout
III Fractions rationnelles
IV L'algorithme d'Euclide : son coût
Index

I Décimales des rationnels

II Application de l'algorithme de Bezout

III Fractions rationnelles

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

I Décimales des rationnels

Algorithme d'Euclide → I Décimales des rationnels

I Décimales des rationnels
II Application de l'algorithme de Bezout
III Fractions rationnelles
IV L'algorithme d'Euclide : son coût
Index

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

= 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é.

$\frac{1}{13}$	=
$\frac{2}{13}$	=
$\frac{3}{13}$	=
$\frac{4}{13}$	=
$\frac{5}{13}$	=
$\frac{6}{13}$	=
$\frac{7}{13}$	=
$\frac{8}{13}$	=
$\frac{9}{13}$	=
$\frac{10}{13}$	=
$\frac{11}{13}$	=
$\frac{12}{13}$	=

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é

Algorithme d'Euclide → I Décimales des rationnels → I-1 Périodicité

I Décimales des rationnels
II Application de l'algorithme de Bezout
III Fractions rationnelles
IV L'algorithme d'Euclide : son coût
Index

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

x = \frac{p}{2^{a} \times 5^{b} \times q}

comme une fraction irréductible avec

p

q

des entiers positifs et

q

premier à

10 p

. Soit

n_{0} = \max (a, b)

et soit

P

l'ordre de

10

modulo

q

, c'est-à-dire le plus petit entier strictement positif tel que

10^{P} \equiv 1 mod q .

Alors, le développement décimal de

x

est de la forme

b_{m} . . . b_{0}, a_{1} . . . a_{n} . . .

avec

a_{n + P} = a_{n}

pour

n > n_{0}

Exercice

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

Algorithme d'Euclide → I Décimales des rationnels → I-1 Périodicité

I-2 Dénominateur fixé

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

I Décimales des rationnels
II Application de l'algorithme de Bezout
III Fractions rationnelles
IV L'algorithme d'Euclide : son coût
Index

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

10^{i}

par

b

. Le développement décimal de

\frac{r}{b}

est obtenu en décalant la virgule (ou le point ici !) de

i

positions vers la droite dans le développement de

\frac{1}{b}

et en prenant la partie fractionnaire du nombre obtenu.

Démonstration

On écrit

10^{i} = r + q b

avec

r

un entier positif strictement inférieur à

b

. Donc,

\frac{r}{b} = \frac{10^{i}}{b} - q

La partie fractionnaire du développement décimal de

\frac{10^{i}}{b}

est égale au développement décimal de

\frac{r}{b}

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

10^{i}

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'Euclide → I Décimales des rationnels → I-2 Dénominateur fixé

I-3 Calculer un chiffre quelconque

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

I Décimales des rationnels
II Application de l'algorithme de Bezout
III Fractions rationnelles
IV L'algorithme d'Euclide : son coût
Index

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 $10^{n - 1}$ .
Par exemple, $10^{5}$ 0.098795181 =9879.5181
On écrit $10^{n - 1} = r + q b$ avec $r$ un entier positif strictement inférieur à $b$ . Donc,
$\frac{10^{n - 1}}{b} = \frac{r}{b} + q$
Le premier chiffre après la "virgule" de $\frac{10^{i}}{b}$ est donc égal au premier chiffre après la virgule de $\frac{r}{b}$ . Il suffit donc de calculer le premier chiffre (sur la gauche) du quotient de $10 r$ par $b$ .

Exercice

Arithmétique du développement
Arithmétique du développement, suite
Calculer le développement

Algorithme d'Euclide → I 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

I Décimales des rationnels
II Application de l'algorithme de Bezout
III Fractions rationnelles
IV L'algorithme d'Euclide : son coût
Index

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-4 Un théorème pour pouvoir répondre

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

II-6 Un exemple

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

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

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

I Décimales des rationnels
II Application de l'algorithme de Bezout
III Fractions rationnelles
IV L'algorithme d'Euclide : son coût
Index

Objectif

On connaît un nombre rationnel positif

x = \frac{s}{t} < 1

par son développement décimal à

10^{- k}

près. On sait d'autre part que son dénominateur est borné par

T

. Calculer

x

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

\frac{b}{N} < \frac{s}{t} < \frac{b + 1}{N}

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

b

. Soit

r_{i}

le premier reste inférieur ou égal à

T

. On obtient une équation

r_{i} = s_{i} N + t_{i} b .

r_{i} < ∣ t_{i} ∣ \leq T

, alors

\frac{- s_{i}}{t_{i}}

a bien les propriétés voulues pour

x

Algorithme d'Euclide → 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

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

I Décimales des rationnels
II Application de l'algorithme de Bezout
III Fractions rationnelles
IV L'algorithme d'Euclide : son coût
Index

Exemple

Dans l'exemple ci-dessous que vous pouvez changer,
le nombre rationnel choisi à l'avance est et son développement décimal à

10^{- 4}

près est

0,

Voyez-vous le rationnel ?
A-t-on la majoration $2^{2} < 10^{4}$ ? Vous pouvez augmenter ou diminuer la précision.

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

II-3 Est-ce un rationnel ?

Algorithme d'Euclide → II Application de l'algorithme de Bezout → II-3 Est-ce un rationnel ?

I Décimales des rationnels
II Application de l'algorithme de Bezout
III Fractions rationnelles
IV L'algorithme d'Euclide : son coût
Index

Exemple

Vous pouvez ici vous donner

Vous cherchez un rationnel dont le développement décimal est donné à

10^{- 7}

près par

0,430 5023

. 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

\sqrt{\frac{1}{2} \times 10^{7}} = 1

? Voyez-vous le rationnel ? Existe-t-il ?

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

Exercice

Recherche d'un rationnel

Algorithme d'Euclide → II Application de l'algorithme de Bezout → II-3 Est-ce un rationnel ?

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

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

I Décimales des rationnels
II Application de l'algorithme de Bezout
III Fractions rationnelles
IV L'algorithme d'Euclide : son coût
Index

II-4-1 L'algorithme de Bezout

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

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

II-4-1 L'algorithme de Bezout

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

I Décimales des rationnels
II Application de l'algorithme de Bezout
III Fractions rationnelles
IV L'algorithme d'Euclide : son coût
Index

Soient

a

b

des entiers positifs avec

a \geq b

. Définissons

les entiers $r_{0}$ , ... , $r_{m + 1}$ et $q_{1}$ , ... , $q_{m}$ avec $m \geq 0$ de la manière suivante : $a = r_{0}$ , $b = r_{1}$ , ... , $r_{i - 1} = r_{i} q_{i} + r_{i + 1}$ avec $0 \leq r_{i + 1} < r_{i}$ et $r_{m + 1} = 0$ ; les $q_{i}$ sont strictement positifs.
les entiers $s_{0}$ , $s_{1}$ , ... , $s_{m + 1}$ et $t_{0}$ , $t_{1}$ , ... , $t_{m + 1}$ par $s_{0} = 1$ , $t_{0} = 0$ , $s_{1} = 0$ , $t_{1} = 1$ et
$s_{i + 1} = s_{i - 1} - s_{i} q_{i}, t_{i + 1} = t_{i - 1} - t_{i} q_{i} .$

Alors

$r_{i} = s_{i} a + t_{i} b$ pour tout $i = 0$ ... $m + 1$ ;
$s_{i} t_{i + 1} - t_{i} s_{i + 1} = (- 1)^{i}$ ;
$pgcd (s_{i}, t_{i}) = 1$ pour tout $i = 0$ ... $m + 1$ ;
$t_{i} t_{i + 1} \leq 0$ et $∣ t_{i} ∣ \leq ∣ t_{i + 1} ∣$ pour tout $i = 0$ ... $m$ ; $s_{i} s_{i + 1} \leq 0$ et $∣ s_{i} ∣ \leq ∣ s_{i + 1} ∣$ pour tout $i = 1$ ... $m$
$r_{i - 1} ∣ t_{i} ∣ \leq ∣ a ∣$ et $r_{i - 1} ∣ s_{i} ∣ \leq ∣ b ∣$ pour tout $i = 1$ ... $m + 1$ .

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

\begin{matrix} a & = & 1 & \times & a & + & 0 & \times & b \\ q_{1} ∣ & b & = & 0 & \times & a & + & 1 & \times & b \\ q_{2} ∣ & r_{2} & = & s_{2} & \times & a & + & t_{2} & \times & b \\ q_{3} ∣ & r_{3} & = & s_{3} & \times & a & + & t_{3} & \times & b \\ q_{4} ∣ & r_{4} & = & s_{4} & \times & a & + & t_{4} & \times & b \end{matrix}

où

q_{3}

est par exemple le quotient de

r_{2}

par

r_{3}

et où la ligne

L_{4}

est obtenue comme la ligne

L_{2}

q_{3}

fois la ligne

L_{3}

.
Démonstration

On peut supposer

a \geq b > 0

. On définit

(r_{i})_{0 \leq i \leq m + 1}

(q_{i})_{1 \leq i \leq m}

comme précédemment, ainsi que les suites définies par récurrence :

$t_{0} = 0$ , $t_{1} = 1$ , $t_{i + 1} = t_{i - 1} - q_{i} t_{i}$ , $1 \leq i \leq m$ .
$s_{0} = 1$ , $s_{1} = 1$ , $s_{i + 1} = s_{i - 1} - q_{i} s_{i}$ , $1 \leq i \leq m$ .

Alors pour tout

0 \leq i \leq m

(\begin{matrix} s_{i} & t_{i} \\ s_{i + 1} & t_{i + 1} \end{matrix}) (\begin{matrix} a Unknown character 4305023 \end{matrix}) = (\begin{matrix} r_{i} \\ r_{i + 1} \end{matrix}) .

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

0 \leq i \leq m

, on a

(\begin{matrix} s_{i} & t_{i} \\ s_{i + 1} & t_{i + 1} \end{matrix}) = (\begin{matrix} 0 & 1 \\ 1 & - q_{i} \end{matrix}) \dots (\begin{matrix} 0 & 1 \\ 1 & - q_{1} \end{matrix}) (\begin{matrix} s_{0} & t_{0} \\ s_{1} & t_{1} \end{matrix}),

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

\det (\begin{matrix} s_{i} & t_{i} \\ s_{i + 1} & t_{i + 1} \end{matrix}) = (- 1)^{i}

et donc

(\begin{matrix} a \\ b \end{matrix}) = {(\begin{matrix} s_{i} & t_{i} \\ s_{i + 1} & t_{i + 1} \end{matrix})}^{- 1} (\begin{matrix} r_{i} \\ r_{i + 1} \end{matrix}) = (- 1)^{i} (\begin{matrix} t_{i + 1} & - t_{i} \\ - s_{i + 1} & s_{i} \end{matrix}) (\begin{matrix} r_{i} \\ r_{i + 1} \end{matrix})

Mais cet inverse est aussi le produit des

{(\begin{matrix} 0 & 1 \\ 1 & - q_{j} \end{matrix})}^{- 1} = (\begin{matrix} q_{j} & 1 \\ 1 & 0 \end{matrix})

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

(\begin{matrix} a \\ b \end{matrix}) = (\begin{matrix} ∣ t_{i + 1} ∣ & ∣ t_{i} ∣ \\ ∣ s_{i + 1} ∣ & ∣ s_{i} ∣ \end{matrix}) (\begin{matrix} r_{i} \\ r_{i + 1} \end{matrix}) .

Donc

∣ t_{i + 1} ∣ r_{i} + ∣ t_{i} ∣ r_{i + 1} = a

∣ s_{i + 1} ∣ r_{i} + ∣ s_{i} ∣ r_{i + 1} = b

et en particulier

$r_{i + 1} ∣ t_{i} ∣ \leq$	$a$
$r_{i + 1} ∣ s_{i} ∣ \leq$	$b$

$∣ t_{i} ∣ \leq$	$a / r_{i + 1} \leq a / (a, b) \leq a$
$∣ s_{i} ∣ \leq$	$b / r_{i + 1} \leq b / (a, b) \leq b$

(Rappelons que

r_{i}

est strictement décroissante avec

r_{m} = pgcd (a, b)

r_{m + 1} = 0

.)
Les

t_{i}

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

(\begin{matrix} ∣ t_{i + 1} ∣ & ∣ t_{i} ∣ \\ ∣ s_{i + 1} ∣ & ∣ s_{i} ∣ \end{matrix}) = (- 1)^{i} (\begin{matrix} t_{i + 1} & - t_{i} \\ - s_{i + 1} & s_{i} \end{matrix}) (\begin{matrix} r_{i} \\ r_{i + 1} \end{matrix})

On a donc

∣ t_{i + 1} ∣ = ∣ t_{i - 1} ∣ + q_{i} ∣ t_{i} ∣

. Comme

q_{i} > 0

, nécessairement

∣ t_{i} ∣ < ∣ t_{i + 1} ∣

. On fait de même pour les

s_{i}

Fin de la démonstration

On démontre que le coût est en

O ((\ln N)^{2})

pour

a

b

inférieurs à

N

Algorithme d'Euclide → II Application de l'algorithme de Bezout → 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

Algorithme d'Euclide → II Application de l'algorithme de Bezout → II-4 Un théorème pour pouvoir répondre → II-4-2 Le théorème en vue

I Décimales des rationnels
II Application de l'algorithme de Bezout
III Fractions rationnelles
IV L'algorithme d'Euclide : son coût
Index

Soient

R

T

N

b

des entiers strictement positifs tels que

b < N, 2 R T \leq N

. On fait tourner l'algorithme d'Euclide étendu avec comme entrées

a = N

b

. Soit l'unique indice

i

compris entre 1 et

m + 1

tel que

r_{i} \leq R < r_{i - 1}

[

t_{i}

est alors non nul]. On pose

r' = r_{i}, s' = s_{i}, t' = t_{i} .

Théorème

Soient

R

T

N

b

des entiers strictement positifs tels que

2 R T \leq N, b < N .

Soient trois entiers

r

s

t

tels que

r = sN + tb

∣ r ∣ \leq R

0 \leq t \leq T

. 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

r' < ∣ t' ∣

et que

∣ t' ∣

est inférieur à

T

. Par contre, si

(r', s', t')

ne fournit pas une solution sous les conditions de l'énoncé

2 RT \leq N

, c'est qu'il n'y en a pas.
Démonstration

Soient

r

s

t

trois entiers relatifs vérifiant

r = sN + t b, ∣ r ∣ \leq R, 0 \leq t \leq T .

Les trois vecteurs

v = (\begin{matrix} r \\ s \\ t \end{matrix})

v_{i} = (\begin{matrix} r_{i} \\ s_{i} \\ t_{i} \end{matrix})

v_{i + 1} = (\begin{matrix} r_{i - 1} \\ s_{i - 1} \\ t_{i - 1} \end{matrix})

appartiennent au plan d'équation

x = N y + b z

. On a donc

(\begin{matrix} r \\ s \\ t \end{matrix}) = m (\begin{matrix} r_{i} \\ s_{i} \\ t_{i} \end{matrix}) + n (\begin{matrix} r_{i - 1} \\ s_{i - 1} \\ t_{i - 1} \end{matrix})

Comme

s_{i} t_{i - 1} - s_{i - 1} t_{i} = \pm 1

, les coefficients

m

n

sont entiers.

Supposons $m$ et $n$ de même signe (ou nuls). Si $n$ est non nul, $R \geq ∣ r ∣ \geq r_{i - 1} > R$ , (car $r_{i}$ , $r_{i - 1}$ sont positifs), ce qui est impossible. Donc
$(\begin{matrix} r \\ s \\ t \end{matrix}) = m (\begin{matrix} r_{i} \\ s_{i} \\ t_{i} \end{matrix}) = m (\begin{matrix} r' \\ s' \\ t' \end{matrix})$
Si $m$ et $n$ sont de signe contraire, nécessairement $∣ t_{i} ∣ \leq t$ puisque $t_{i}$ et $t_{i + 1}$ sont de signe différent et que $∣ t_{i - 1} ∣ \leq ∣ t_{i} ∣$ . Donc
$0 \leq ∣ r t_{i} ∣ < R ∣ t ∣ < N / 2$

$0 \leq r_{i} t < R T < N / 2$
et
$- N / 2 < r_{i} t - r t_{i} < N$

Les trois vecteurs colonne de la matrice $(\begin{matrix} r & r_{i} & N \\ s & s_{i} & 1 \\ t & t_{i} & 0 \end{matrix})$ sont liés, leur déterminant est nul et le déterminant de $(\begin{matrix} r & r_{i} & 0 \\ s & s_{i} & 1 \\ t & t_{i} & 0 \end{matrix})$ est congru à 0 modulo $N$ :
$r_{i} t - r t_{i} \equiv 0 mod N$
Finalement $r_{i} t - r t_{i} = 0$ . Le vecteur $v$ est combinaison linéaire de $v_{i}$ et de $e = (\begin{matrix} 0 \\ 1 \\ 0 \end{matrix})$ . Comme $v$ et $v_{i}$ 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

O ((\ln N)^{2})

. Il est donc au pire quadratique en la taille de

N

.
Démonstration

On se donne donc une puissance de 10,

N = 10^{n}

. 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

2 T^{2} \leq N

. Si le rationnel existe, il s'agit de

- \frac{s_{i}}{t_{i}}

avec

r_{i} < T < r_{i - 1}

. Mais il faut vérifier que

r_{i} < ∣ t_{i} ∣ < T

. 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

\sqrt{10^{n} / 2}

Fin de la démonstration

Algorithme d'Euclide → II Application de l'algorithme de Bezout → II-4 Un théorème pour pouvoir répondre → 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

Algorithme d'Euclide → II Application de l'algorithme de Bezout → II-5 Autour du lemme chinois

I Décimales des rationnels
II Application de l'algorithme de Bezout
III Fractions rationnelles
IV L'algorithme d'Euclide : son coût
Index

Objectif

On a codé un entier

x

en calculant ses classes résiduelles modulo des entiers

N_{1}

, ... ,

N_{r}

premiers entre eux deux à deux :

c (x) = (x_{1}, . . ., x_{r})

. L'entier

N = \prod_{i} N_{i}

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_{1}, . . ., x_{r})

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

N_{1}

, ... ,

N_{r}

(par exemple, le produit des

L

plus grands). On suppose que

N > 4 P^{2} Z

.
Soit

c_{1} (x) = (y_{1}, . . ., y_{r})

les classes transmises effectivement. Par le lemme chinois, il existe un entier

y

vérifiant

y \equiv y_{1} mod N_{i}

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

t'

divise

r'

z = \frac{r'}{t'}

est une solution possible.

On démontre que le coût est en

O ((\ln N)^{2})

.
Démonstration

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

r \leq Z P .

D'autre part

r \equiv t y mod N .

En effet,

r

ty

sont tous deux congrus à 0 modulo

N_{i}

N_{i}

est mauvais, (dans ce cas,

N_{i}

divise

t

) ; pour

N_{i}

bon, comme

x \equiv y mod N_{i}

r = tx

ty

sont bien congrus modulo

N_{i}

. Soit

s

l'entier tel que

r = ty + sN

Comme

0 \leq r \leq ZP

t \leq P

ZP \times P \leq N / 2

, on peut appliquer le théorème :

(r, s, t)

est un multiple entier de

(r', s', t')

z = r / t = r' / t' .

t'

divise

r'

, l'entier

\frac{r'}{t'}

est la solution cherchée. Sinon, c'est qu'il y a d'autres fautes dans la transmission du message.

Fin de la démonstration

Exercice

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

Algorithme d'Euclide → II Application de l'algorithme de Bezout → II-5 Autour du lemme chinois

II-6 Un exemple

Algorithme d'Euclide → II Application de l'algorithme de Bezout → II-6 Un exemple

I Décimales des rationnels
II Application de l'algorithme de Bezout
III Fractions rationnelles
IV L'algorithme d'Euclide : son coût
Index

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

mod 3
mod 4
mod 5
mod 11
mod 19
mod 23
mod 29

Par le lemme chinois , on trouve que l'entier transmis est . L'algorithme d'Euclide appliqué à

4 \times 5 \times 23 \times 11 \times 19 \times 29 \times 3 =

et donne

Regardons la première ligne où le reste (colonne de gauche) est strictement inférieur à

NaN =

. Le nombre cherché est

1 = NaN

Algorithme d'Euclide → II Application de l'algorithme de Bezout → II-6 Un exemple

III Fractions rationnelles

Algorithme d'Euclide → III Fractions rationnelles

I Décimales des rationnels
II Application de l'algorithme de Bezout
III Fractions rationnelles
IV L'algorithme d'Euclide : son coût
Index

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

III-1 Approximant de Padé

III-2 Un exemple

III-3 Séries de Laurent

III-4 Les coefficients

Algorithme d'Euclide → III Fractions rationnelles

III-1 Approximant de Padé

Algorithme d'Euclide → III Fractions rationnelles → III-1 Approximant de Padé

I Décimales des rationnels
II Application de l'algorithme de Bezout
III Fractions rationnelles
IV L'algorithme d'Euclide : son coût
Index

Définition

Soit

F

un corps et

f

une série formelle

\sum_{i \geq 0} f_{i} x^{i}

avec

f_{i}

dans

F

. Un

(k, n - k)

-approximant de Padé de

f

est une fraction rationnelle

\frac{r}{t}

telle que

$x$ ne divise pas $t$
$\frac{r}{t} \equiv f mod x^{n}$
$° r < k$ , $° t \leq n - k$

Soit

f

un polynôme de degré strictement inférieur à

n

k

un entier strictement inférieur à

n

. On exécute l'algorithme d'Euclide étendu pour

x^{n}

f

. Soient

r_{i}

les restes successifs obtenus. La suite des

° r_{j}

est strictement décroissante. Soit

j

le plus petit entier tel que

° r_{j} < k

. On pose

r' = r_{j}

s' = s_{j}

t' = t_{j}

avec les notations de l'algorithme :

r' = s' x^{n} + t' f .

Théorème

Avec les notations précédentes, les polynômes

r'

t'

vérifient

$r' \equiv t' f mod x^{n}$
$° r' < k$ , $° t' \leq n - k$ .

Pour tous polynômes

s

t

tels que

r = s x^{n} + t f

avec

° r < k

° t \leq n - k

, on a

(r, s, t) = w (r', s', t')

pour

w

un polynôme.

Ainsi, si

\frac{r'}{t'}

est irréductible, c'est un

(k, n - k)

-approximant de Padé.
Démonstration

Exercice !

Fin de la démonstration

Exercice

Approximant de Padé

Algorithme d'Euclide → III Fractions rationnelles → III-1 Approximant de Padé

III-2 Un exemple

Algorithme d'Euclide → III Fractions rationnelles → III-2 Un exemple

I Décimales des rationnels
II Application de l'algorithme de Bezout
III Fractions rationnelles
IV L'algorithme d'Euclide : son coût
Index

Exemple

Les égalités suivantes permettent de déterminer des approximants de Padé du polynôme de Taylor de

\cos (x)

d'ordre

3

f =

Dans le dessin qui suit, on a représenté sur l'intervalle [-1,1] la différence entre

\cos (x)

et un approximant de Padé

Algorithme d'Euclide → III Fractions rationnelles → III-2 Un exemple

III-3 Séries de Laurent

Algorithme d'Euclide → III Fractions rationnelles → III-3 Séries de Laurent

I Décimales des rationnels
II Application de l'algorithme de Bezout
III Fractions rationnelles
IV L'algorithme d'Euclide : son coût
Index

Définition

Une série formelle à coefficients dans un anneau $R$ est une expression formelle de la forme $f = a_{0} + a_{1} X + . . . a_{n} X^{n} + . . .$ avec les $a_{i} \in R$
Une série de Laurent est une expression formelle de la forme $f = a_{m} X^{m} + a_{m + 1} X^{m + 1} + . . .$ pour un entier relatif $m$ .
Une série de Laurent renversée est une expression formelle de la forme $f = \sum_{i = - ∞}^{m} a_{i} X^{i}$ .

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

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

F ((x^{- 1}))

Remarque

Une série de Laurent renversée

f = \sum_{i = - ∞}^{m} a_{i} X^{i}

avec

a_{m} \neq 0

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,

F ((x^{- 1}))

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.

() / () = (* ()) / (* ())

= * () + . . .

Algorithme d'Euclide → III Fractions rationnelles → III-3 Séries de Laurent

III-4 Les coefficients

Algorithme d'Euclide → III Fractions rationnelles → III-4 Les coefficients

I Décimales des rationnels
II Application de l'algorithme de Bezout
III Fractions rationnelles
IV L'algorithme d'Euclide : son coût
Index

On désire calculer le développement d'une fraction rationnelle

\frac{s}{t}

: par exemple, étant donné

k

un entier positif, on veut calculer le coefficient de

x^{- k}

Résultat

On calcule

h = x^{k - 1} s mod t

avec

° h < ° t

.
Le coefficient de

x^{- k}

est le résidu de

\frac{h}{t}

: si

° h = ° t - 1

, c'est le quotient des coefficients dominants de

h

et de

t

; si

° h < ° t - 1

, c'est

0

Démonstration

Le coefficient cherché est le résidu (c'est-à-dire coefficient de

\frac{1}{x}

) de

x^{k - 1} r / t

. Comme

h = x^{k - 1} r + s t

, on a

x^{k - 1} \frac{r}{t} = - s + \frac{h}{t} .

Fin de la démonstration

Exemple

On a

x^{24} ()

mod .
Le coefficient de

x^{- 25}

dans vu comme élément de est .

Exercice

Trouver un coefficient

Algorithme d'Euclide → III Fractions rationnelles → III-4 Les coefficients

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

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

I Décimales des rationnels
II Application de l'algorithme de Bezout
III Fractions rationnelles
IV L'algorithme d'Euclide : son coût
Index

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

IV-1 Combien ça coûte ?

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

IV-2 Nombres de Fibonacci

IV-3 Analyse de l'algorithme d'Euclide

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

IV-4 Pgcd étendu

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

IV-1 Combien ça coûte ?

Algorithme d'Euclide → IV L'algorithme d'Euclide : son coût → IV-1 Combien ça coûte ?

I Décimales des rationnels
II Application de l'algorithme de Bezout
III Fractions rationnelles
IV L'algorithme d'Euclide : son coût
Index

Pour , on note

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 .
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 .

Algorithme d'Euclide → IV L'algorithme d'Euclide : son coût → IV-1 Combien ça coûte ?

IV-2 Nombres de Fibonacci

Algorithme d'Euclide → IV L'algorithme d'Euclide : son coût → IV-2 Nombres de Fibonacci

I Décimales des rationnels
II Application de l'algorithme de Bezout
III Fractions rationnelles
IV L'algorithme d'Euclide : son coût
Index

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

Les équations

permettent de calculer les nombres de Fibonacci.

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

En choisissant , on obtient C_n = O(n²).
Plus généralement, sous l'hypothèse pour , on obtient

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.

Algorithme d'Euclide → IV L'algorithme d'Euclide : son coût → IV-2 Nombres de Fibonacci

IV-3 Analyse de l'algorithme d'Euclide

Algorithme d'Euclide → IV L'algorithme d'Euclide : son coût → IV-3 Analyse de l'algorithme d'Euclide

I Décimales des rationnels
II Application de l'algorithme de Bezout
III Fractions rationnelles
IV L'algorithme d'Euclide : son coût
Index

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

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

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

Démonstration

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).

Fin de la démonstration

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

Algorithme

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

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.

Démonstration

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.

Fin de la démonstration

Lemme

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

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

Démonstration

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

Fin de la démonstration

Corollaire

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

Démonstration

Si on a n - 1 divisions, on obtient

soit

(puisque ) et

Fin de la démonstration

Corollaire

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

En fait, on peut facilement faire mieux :

Lemme

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

Démonstration

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 .

Fin de la démonstration

Algorithme d'Euclide → IV L'algorithme d'Euclide : son coût → IV-3 Analyse de l'algorithme d'Euclide

IV-4 Pgcd étendu

Algorithme d'Euclide → IV L'algorithme d'Euclide : son coût → IV-4 Pgcd étendu

I Décimales des rationnels
II Application de l'algorithme de Bezout
III Fractions rationnelles
IV L'algorithme d'Euclide : son coût
Index

Algorithme

Étant donnés deux entiers positifs a et b, l'algorithme calcule d = (a,b), et des entiers relatifs s et t tels que a s + b t = d.

Si a = 0, renvoyer d = b, s = 0, t = 1.
On pose x = a, y = b, s_x = 0, t_y = 1.
Tant que
1. trouver q, r réalisant la division euclidienne x = q y + r.
2. remplacer (t_x, t_y) par (t_y, t_x - qt_y).
3. remplacer (x, y) par (y, x - q y)
Renvoyer d = x, , et t = t_x.

Démonstration

(x,y) prennent les mêmes valeurs que dans l'algorithme d'Euclide, donc l'algorithme étendu termine après le même nombre de boucles. La démonstration de l'assertion du (3) est immédiate par récurrence. On en déduit qu'en (4), , donc . Le résultat suit.

Fin de la démonstration

Tout au long de l'algorithme d'Euclide étendu, on a

En particulier les coefficients de l'identité de Bezout sa + tb = d obtenus satisfont et .

Corollaire

Si a et b sont inférieurs à N, le coût d'obtention du pgcd de a et b et des coefficients de Bezout est .

Démonstration

Le coût est dominé par

en majorant , et comme dans la section précédente. On a majoré le coût des soustractions par

Fin de la démonstration

Algorithme d'Euclide → IV L'algorithme d'Euclide : son coût → IV-4 Pgcd étendu

document autour des rationnels et de l'algorithme d'Euclide du point de vue algorithmique.
: arithmetique,nombre rationnel,algorithme d'Euclide, interactive mathematics, interactive math, server side interactivity

Veuillez noter que les pages WIMS sont générées interactivement; elles ne sont pas des fichiers HTML ordinaires. Elles doivent être utilisées interactivement EN LIGNE. Il est inutile pour vous de les ramasser par un programme robot.

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