Une trouvaille: l'inverse modulaire revisité

Hello,

Je ne sais pas si j'ai raté un chapitre mais avec $a = 1$ et $b = 2$. N'aurait-on-pas :

$U_0 = 3$
$U_1 = 3 - 0 - 1 = 2$
$U_2 = 2 - 0 - 0 = 2$
$U_3 = 2 - 0 - 0 = 2$
...

J'espère que je me trompe.

D'ailleurs pour $a = 2$ et $b = 4$ :

$U_0 = 9$
$U_1 = 9 - 1 - 1 = 7$
$U_2 = 7 - 1 - 3 = 3$
$U_3 = 3 - 1 - 3 = -1$
$U_4 = -1 + 1 + 1 = 1$
$U_5 = 1 - 1 - 1 = -1$
...

@nodgim
Pourrais-je avoir son nom et sa complexité ?

La complexité c'est le "temps" dont on a besoin pour l'exécuter, par exemple celui d'Al-Kashi est de l'ordre de $O(m)$ car la plus longue opération dépend de $m$, ici c'est une somme d'élément calculable avec un nombre constant d'opération (disons 3, l'arrondissement de la division, la division et la multiplication), on a donc $O(m) * O(3) $ qui appartient à $O(m)$. Le mieux serait évidement de la déterminer en fonction de $a$ et de $b$ mais je n'ai pas essayé.

Et non je ne peux déterminer la complexité d'un algorithme à partir d'un seul exemple, mais ce n'est pas très important c'était juste pas curiosité.

Effectivement, il faut mettre la complexité de côté. Et mettre $a\N + b\N$ sur la sellette.

[color=#000000]
> a := 10^7 + 1 ;              
> b := 10^7 - 1 ;
> time Modinv(a,b) ;  <-- magma
5000000
Time: 0.000
> time a1,b1 := Inverses(a,b) ;  <-- Al-Kashi
Time: 20.600
> a1 ;
5000000
[/color]

Of course, ci-dessous, inutile de solliciter Inverses

[color=#000000]
> a := 10^50 + 1 ;             
> b := 10^50 - 1 ;
> time Modinv(a,b) ;
50000000000000000000000000000000000000000000000000
Time: 0.000
[/color]

J'ai une demi-réponse pour cette question, c'est une prolongation de ma réponse à la question précédente. Comme tu avais indiqué ne pas l'avoir comprise en entier, ça va être compliqué de m'expliquer.....

Je reprends quelques extraits de la description précédente :

La sous-suite x0, x2, x4 est donc une suite arithmétique de raison r [ a ]. Elle aboutit à 0 puisque b premier avec a, donc r premier avec a.
........
En partant du couple (r, b-r) on aboutit à 0 par une chaine unique qui contient toutes les valeurs x modulo a et toutes les valeurs y modulo b > b-a.

Or r = a - b [a] = -b[a] En suivant les x successifs, on arrivera bien à x = 1. Quand on arrivera à cette valeur, on aura l'égalité k * r = 1 soit k * ( -b[a] ) = 1

Si k est l'inverse [a] de -b, alors -k est l'inverse de b, et -k c'est a-k, c'est à dire le reste des valeurs de " a " entre 1 et 0.

Or il se trouve que, pour b [a] [U(k+1)/b] = [Uk/b] - 1. En prenant la soustraction de 2 Uk successifs, on obtient 1. Or, dans la chaine que j'avais décrite, les r [a] apparaissent un fois sur 2.
" -k " représente donc exactement la valeur de la suite proposée.

Pour la suite des Uk / a, avec a < b , je n'ai aucune idée de la raison pour laquelle ça marche également.

Original en tout cas !

Après, au gré des modes et des influences sur les publications.....

@Al-Kashi
Pareil que Mel d'une part. D'autre part, pourquoi vouloir mettre en avant cette histoire de rapidité ? Je ne suis pas convaincu qu'il faille le présenter ainsi.

Autre chose. A force de ``cacher un peu tes affaires'' (par exemple donner des ``exercices'' dont tu as la solution via quelque chose de structurel), ce n'est pas toujours facile d'échanger. Je prends un exemple concret sur l'autre fil (flemme de pointer) mais qui présente des analogies avec ce fil (et pour cause).

Contexte : $a, b \in \N^*$ premiers entre eux. Je note $b^{-1}$ un inverse de $b$ modulo $a$, $a^{-1}$ un inverse de $a$ modulo $b$, $n_a$ le reste de $n$ dans la division par $a$. Idem pour $n_b$. Et enfin $\{ x \} = x - \lfloor x\rfloor$ (la partie fractionnaire je crois que cela s'appelle comme cela). Cette histoire d'invariance de $\#\{(x,y) \in \N \times \N \mid ax + by = n\}$ par $n \mapsto n - n_a - n_b$, tu étais le seul à la connaître. J'ai gratté dans mon coin et j'ai fini par trouver (pas de manière super limpide à vrai dire) ``un certain pot aux roses''. Mais ce n'était pas ton invariance ! Et quand j'ai voulu vérifier des choses en tenant compte de la formule de Popoviciu, je me suis rendu compte que cela me conduisait à l'identité :
$$
\left\{ {b^{-1} (n - n_a - n_b) \over a} \right\} = \left\{ {a^{-1} n \over b} \right\} - {n_b \over ab}
$$
J'ai bien essayé de montrer cette égalité de manière directe mais je n'y suis pas arrivé (à vrai dire, je n'ai pas trop insisté). Est ce qu'elle te dit quelque chose ?