Acte 2 : l'inverse modulaire revisité

Merci Poirot.

Voici un petit exemple numérique:

On cherche l'inverse de $27$ modulo $50$.
La suite des restes est $50-27-23-4-3-1$.

$(27^{-1})_{50}=50\Big(\dfrac{1}{3}+\dfrac{23-50}{27*23*50}+\dfrac{3-23}{3*4*23}\Big)$
$(27^{-1})_{50}=13$


Je vous laisse comparer à l'algorithme d'Euclide étendu.
J'ai l'impression qu'il y a moins de calculs.

Al-Kashi

Je me lance dans un comparatif brut à prendre avec des pincettes car je ne maîtrise pas le domaine.

Premier point commun entre les deux algorithmes: la suite des restes. Nous laissons donc de côté cette partie car elle sera traitée de la même manière par une machine. Celle-ci correspond dans le tableau ci-dessous à la première colonne.

Nombre de variables de stockage : $6$ pour Euclide-étendu contre $4$ pour le mien.

Nombre d'opérations par boucle: pour Euclide-étendu sans compter la première colonne on obtient $6$ opérations élémentaires. Pour le mien ceci correspond au terme sous la somme on obtient $4$ opérations élémentaires.

Bilan:
Algorithme d'Euclide-étendu: En sus des calculs des restes, il faut donc $6m$ opérations.
Algorithme d'Al-Kashi: En sus des calculs des restes, il faut donc au maximum $4(\dfrac{m-2}{2}+1)+2$ soit $2m+2$ opérations.

Une variante pour Euclide-étendu consiste à rajouter une variable pour stocker le calcul du quotient à chaque étape et ramène le nombre d'opérations en sus des calculs de restes à $4m$.

Al-Kashi

@Claude et Melpomene

Sur vos conseils, j'ai envoyé un mail à Quadrature.
Comme je vous l'ai dit étant amateur, et ne sachant pas quels sont les critères attendus (type de fichier, logiciel, police,rédaction,...) et craignant de faire un travail d'écriture inutile j'ai transmis les liens des discussions.

En cas de retour positif, je me plierai ensuite aux différentes contraintes pour construire les documents attendus.

Al-Kashi

Joaopa écrivait:

> Bien cachée sous le tapis, l'arnaque.

De quelle arnaque parles-tu?
Si c'est des formules que je propose alors pourquoi pas appeler tous les nouveaux résultats "arnaques".
Si c'est de la partie algorithmique, j'ai bien précisé " à prendre avec des pincettes" et si tu as constaté une bourde il serait plus constructif de la préciser.

J'ai lu quelques-unes de tes interventions, notamment lorsque j'avais revisité les identités à la Popoviciu ou encore autour des dénumérants et je te trouve très désagréable.


Al-Kashi

Voici la preuve des résultats annoncés:

Dans tout ce qui suit, on considère deux entiers $a$ et $b$ premiers entre eux tels que $1<a<b$.
On note $(i)_j$ le reste de la division euclidienne de $i$ par $j$.
On note $(a^{-1})_b$ l'inverse de $a$ modulo $b$.
On considère la suite $R_k$ où $k$ varie de $1$ à $m+1$ définie par $R_0=b$, $R_1=a$, $R_{k+1}=(R_{k-1})_{R_k}$ et $R_m=1$ soit donc $R_{m+1}=0$.

Lemme 1.
Soit $n\in\N$ .Le nombre de solutions dans $\N^2$ de l'équation $ax+by=n$ est:
$$\dfrac{n-b(nb^{-1})_a-a(na^{-1})_b}{ab}+1$$.
Preuve:
Voir mes travaux antérieurs ici Popoviciu revisité.

Corollaire 1.
L'unique solution dans $\N^2$ de l'équation $ax+by=ab+1$ est $\Big((a^{-1})_b;(b^{-1})_a\Big)$.
Preuve:
Tout d'abord $\dfrac{a(a^{-1})_b+b(b^{-1})_a-1}{ab}$ est un entier. De plus $0<a(a^{-1})_b+b(b^{-1})_a-1<2ab$. En conclusion $a(a^{-1})_b+b(b^{-1})_a-1=ab$ et $\Big((a^{-1})_b;(b^{-1})_a\Big)$ est une solution de l'équation $ax+by=ab+1$.
On en déduit alors en utilisant le Lemme 1 que c'est la seule solution.

Avec ce qui précède, nous pouvons introduire la suite $(x_k;y_k)$ où $0\leq k \leq m-2$ définie par l'unique couple solution de $$R_{k+1}x+R_{k}y=R_{k+1}R_{k}+1.$$
Nous définissons aussi $(x_{m-1};y_{m-1})=(1;1)$ et $(x_{m};y_{m})=(1;1)$.

Lemme 2.

Pour tout $0 \leq k \leq m-2 $ on a : $x_{k}=\dfrac{R_{k+2}-R_{k}}{R_{k+2}R_{k+1}}+\dfrac{R_{k}}{R_{k+2}}x_{k+2}$.
Preuve:
Par définition: $R_{k+1}x_k+R_{k}y_k=R_{k+1}R_{k}+1$ et $R_{k+2}x_{k+1}+R_{k+1}y_{k+1}=R_{k+2}R_{k+1}+1$.
Par définition, sachant que $R_{k+2}\equiv R_{k}$ modulo $R_{k+1}$, on en déduit alors que l'inverse modulaire de $R_{k+2}$ est aussi l'inverse modulaire de $R_{k}$ modulo $R_{k+1}$ .
On a donc $x_{k+1}=y_k$ (*).
En injectant ce résultat dans les deux expressions ci dessus on obtient alors $x_{k}=\dfrac{R_{k+2}-R_{k}}{R_{k+2}R_{k+1}}+\dfrac{R_{k}}{R_{k+2}}y_{k+1}$. En utilisant alors (*) on obtient le résultat annoncé.

Corollaire 2.
Soit $2\leq s\leq m$ un nombre pair. on a : $x_{0}=R_0\Big(\dfrac{x_{s}}{R_{s}}+\sum \limits_{k=0}^{\frac{s-2}{2}}\dfrac{R_{2k+2}-R_{2k}}{R_{2k}R_{2k+1}R_{2k+2}}\Big)$.
Preuve:
Immédiat en utilisant une récurrence et le Lemme 2..

Corollaire 3.
Si $m$ est pair alors $(a^{-1})_b=b\Big(1+\sum \limits_{k=0}^{\frac{m-2}{2}}\dfrac{R_{2k+2}-R_{2k}}{R_{2k}R_{2k+1}R_{2k+2}}\Big)$.
Preuve:
Immédiat en utilisant le Corollaire 2.

Corollaire 4.
Si $m$ est impair alors $(a^{-1})_b=b\Big(\dfrac{1}{R_{m-1}}+\sum \limits_{k=0}^{\frac{m-3}{2}}\dfrac{R_{2k+2}-R_{2k}}{R_{2k}R_{2k+1}R_{2k+2}}\Big).$
Preuve:
Immédiat en utilisant le Corollaire 2 avec le nombre pair $m-1$.

Al-Kashi

Voilà qui me semble plus synthétique et élégant, on peut finalement simplifier les formules en :

Si $m$ est pair : $\quad\displaystyle
(a^{-1})_b=b\Big(1+\sum \limits_{k=0}^{m-1}\dfrac{(-1)^k}{R_{k}R_{k+1}}\Big).
$
Si $m$ est impair : $\quad\displaystyle
(a^{-1})_b=b\Big(\sum \limits_{k=0}^{m-1}\dfrac{(-1)^k}{R_{k}R_{k+1}}\Big).
$

Al-Kashi

Bonjour,

Toujours dans l'attente de réponses à mes questions, j'aimerais savoir si quelqu'un ici serait spécialiste dans le domaine des fractions continues. Je pose cette question car un de mes anciens professeurs, M.Joseph Oesterlé, m'a dit à ce sujet:

" Je pense qu’il doit déjà figurer sous une forme ou une autre dans certains livres sur les fractions continues, même si je ne suis pas capable de vous donner une référence. Vous pouvez le soumettre, par exemple à une revue de professeurs de classes préparatoires, charge au rapporteur s’il pense comme moi de vous trouver un endroit où ce résultat apparaît déjà."

En vous remerciant,

Al-Kashi