L'inverse modulaire revisité (3)
dans Arithmétique
Arithméticiens
J'avais proposé il y a peu de temps deux formules sous formes de sommes permettant de déterminer un inverse modulaire (voir Acte1 et Acte2). Je vous propose ici une autre formule cette fois sous la forme d'un produit sous l'hypothèse $b$ premier.
Soit $1<a<b$.
On note $(i)_j$ le reste de la division euclidienne de $i$ par $j$.
On note $\tilde{a}_b$ l'inverse de $a$ modulo $b$.
On considère la suite $v_k$ où $k$ varie de $1$ à $m$ définie par $v_1=a$, $v_{k+1}=\Big(-v_k\Big\lfloor\dfrac{b}{v_{k}}\Big\rfloor\Big)_b$ et $v_m=1$. Démontrer que : $$
\tilde{a}_b=\Big(\prod_{k=1}^{k=m-1}-\Big\lfloor\dfrac{b}{v_k}\Big\rfloor\Big)_b.
$$ Al-Kashi
J'avais proposé il y a peu de temps deux formules sous formes de sommes permettant de déterminer un inverse modulaire (voir Acte1 et Acte2). Je vous propose ici une autre formule cette fois sous la forme d'un produit sous l'hypothèse $b$ premier.
Soit $1<a<b$.
On note $(i)_j$ le reste de la division euclidienne de $i$ par $j$.
On note $\tilde{a}_b$ l'inverse de $a$ modulo $b$.
On considère la suite $v_k$ où $k$ varie de $1$ à $m$ définie par $v_1=a$, $v_{k+1}=\Big(-v_k\Big\lfloor\dfrac{b}{v_{k}}\Big\rfloor\Big)_b$ et $v_m=1$. Démontrer que : $$
\tilde{a}_b=\Big(\prod_{k=1}^{k=m-1}-\Big\lfloor\dfrac{b}{v_k}\Big\rfloor\Big)_b.
$$ Al-Kashi
Réponses
-
Bonjour
Avant que le sujet ne se dirige vers les archives, voici un exemple d'application.
On cherche l'inverse de $27 \mod(43)$. On écrit les divisions euclidiennes successives ayant pour dividende $43$:
$43=1*27+16=2*16+11=3*11+10=4*10+3=14*3+1$ et on trouve alors $27^{-1}\equiv(-1)^5*1*2*3*4*14 \mod(43)$ soit $27^{-1}=8 \mod (43)$.
Al-Kashi -
Marrant ça.
43 = 3 *14 + 1 d'où 3 = -1/14 [43]
43 = 4 *10 + 3 d'où 10 = -3/4 = 1 / (4*14) [43]
etc.... -
Bonjour,
@Al-Kashi
Ta jolie formule ne fonctionnerait-elle pas même si $b$ est seulement primaire?
Exemples:
$16^{-1} [27]$=?
$01,02,05,13$
$16,11,05,02,01$
on vérifie que
$16*(-1)^4*(1*2*5*13)=16*5*26=-80=1 [27]$
$16^{-1} [25]$=?
$01,02,03,06$
$16,09,07,04,01$
on vérifie que
$16*(-1)^4*(1*2*3*6)=16*11=176=1 [25]$
en revanche elle est fausse (en général, toujours?) si $b$ n'est pas primaire:
Exemple:
$11^{-1} [18]$=?
$01,02,04,09$
$11,07,04,02,00$
Amicalement
Paul -
Bonjour,
@Nodgim: j'ai aussi trouvé cela amusant.
@Depasse: dans la preuve j'ai dû utiliser le fait que le dividende est toujours premier avec le reste dans les divisions consécutives pour atteindre l'unité. La formule peut donc fonctionner dans différents cas mais de manière générale, il me semble que l'hypothèse $b$ premier est nécessaire.
Edit: correction
Al-Kashi -
On peut aussi l'utiliser par exemple si $a$ est premier en calculant par exemple $\tilde{b}_a$.On peut alors écrire une formule dans le cas général à condition d'utiliser la décomposition en facteurs premiers du nombre $a$.
Al-Kashi
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 8 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
Qui est en ligne 10
+5 Invités