Fractions continues et inverse
dans Arithmétique
Bonsoir @ tous.
Peut être est-ce connu ?
Soit A/B > 0 et irréductible dont l'écriture en fraction continue est (a1, a2,..., an)
Comment trouver 1/A [ B] à partir de l'écriture en fraction continue sans recalculer A/B ?
Peut être est-ce connu ?
Soit A/B > 0 et irréductible dont l'écriture en fraction continue est (a1, a2,..., an)
Comment trouver 1/A [ B] à partir de l'écriture en fraction continue sans recalculer A/B ?
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
peux-tu préciser les notations ou donner un contexte ? A première lecture, j'interprète A et B comme des entiers, mais alors je ne comprends plus le 1/A modulo B, puisque 1/A n'a aucune raison d'être un entier.
Cordialement.
Regarde la formule (3) de ce paragraphe:
https://fr.wikipedia.org/wiki/Fraction_continue#Réduites_d'une_fraction_continue
On a:
\begin{align}\dfrac{43}{30}=1+\dfrac{1}{2+\dfrac{1}{3+\dfrac{1}{4}}}
\end{align} La réduire précédente de $\dfrac{43}{30}$ est :
\begin{align}\dfrac{10}{7}=1+\dfrac{1}{2+\dfrac{1}{3}}
\end{align} On reprend les notations de Wikipedia :
\begin{align}\dfrac{h_3}{k_3}&=\dfrac{43}{30}\\
\dfrac{h_2}{k_2}&=\dfrac{10}{7}
\end{align} On applique la formule (3):
\begin{align}h_2k_3-h_3k_2&=(-1)^3\\
10\times 30-43\times 7&=-1
\end{align} Si on veut l'inverse modulo $43$ de $30$ on utilise l'égalité suivante qui nous montre que:
\begin{align} 10\times 30 \equiv -1\mod{43}
\end{align} Donc, l'inverse cherché modulo $43$ est $-10$.
PS. Ce sont les deux dernières réduites de la fraction continue d'une fraction de nombres premiers entre eux qui nous intéressent.
A/B = (a1, a2, .... an)
Soit :
b1 = 1
b2 = a2
bk = ak * b(k-1) + b(k-2)
Alors b(n-1)=+ 1/A [ B] si n pair et -1/A [ B] si n impair.
À noter que le calcul des termes d'une fraction continue peut être rapidement faux par les arrondis de la machine. Exemple avec 1871/479 = (3,1,9,1,1,1,4,3) donne avec une calculette : (3,1,9,1,1,1,4,3,554078014,5,2,2,...)
Je pense que c'est le contraire.
Exemple :
$1871\div479\simeq3{,}91$ d'où $1871-479\times3=434$ ;
$479\div434\simeq1{,}1$ d'où $479=434\times1+45$ ;
$434\div45\simeq9{,}6$ d'où $434=45\times9+29$ ;
$45\div29\simeq1{,}55$ d'où $45=29\times1+16$, etc. Au bilan : \begin{align*}\frac{1871}{479}&=3+\frac{1}{\frac{479}{434}}=3+\frac{1}{1+\frac{1}{\frac{434}{45}}}=3+\frac{1}{1+\frac{1}{9+\frac{1}{\frac{45}{29}}}}=3+\frac{1}{1+\frac{1}{9+\frac{1}{1+\frac{1}{\frac{29}{16}}}}}=\cdots\end{align*}
Voir:
https://fr.wikipedia.org/wiki/Algorithme_d'Euclide_étendu
Sinon, je ne crois pas m'être trompé dans le signe de 1/A, mais attention, le 1ere terme que j'ai choisi est a1 et non a0.
Quel sens donnes-tu à:
A/B = (a1, a2, .... an) ?
&=[0,3,8,2]
\end{align} Les deux dernières réduites sont dans l'ordre:
\begin{align}
\frac{h_2}{k_2}&=\dfrac{1}{3+\dfrac{1}{8}}\\
&=\dfrac{8}{25}\\
\dfrac{h_3}{k_3}&=\dfrac{17}{53}.
\end{align} Donc,
\begin{align}h_2k_3-h_3k_2&=(-1)^3\\
8\times 53-17\times 25&=-1
\end{align} Donc:
\begin{align}17\times 25\equiv 1\mod{53}
\end{align} PS. Donc, en effet, la parité du nombre [de] termes dans le développement en fraction continue indique si on va coller, ou pas un moins devant le numérateur de l'avant dernière réduite pour obtenir l'inverse modulaire cherché (si pair, pas de moins).
juste une remarque les coefficients $(a_0,a_1,..)$ apparaissant dans le développement en fraction continue de $\frac{a}{b}$ sont exactement les quotients que l'on calcule lorsque on utilise l'algorithme d'Euclide pour déterminer le PGCD de $a$ et $b$.
Cet algorithme permettant également de calculer l'inverse de $a$ modulo $b$, il n'est guère étonnant que le développement en fractions continues de $\frac{a}{b}$ "contienne" l'inverse de $a$ modulo $b$.
Bonne journée
F.