Calculando con inversos en $\mathbb Z_7$

Question

Quiero calcular $\frac{\overline{2}}{\overline{3}}$, $\frac{\overline{1}}{\overline{9}}$, $\frac{\overline{32}}{\overline{9}}$ en $\mathbb{Z}_7$.

Sobre el primer ejemplo, mi libro dice: $\overline{3}*\overline{5}=\overline{15}=\overline{1}$, entonces $\frac{\overline{1}}{\overline{3}}=\overline{5}$; y finalmente $\frac{\overline{2}}{\overline{3}}=\overline{10}=\overline{3}$. Es bastante claro, ¿excepto el primer paso? ¿De dónde salieron 5 y 3?

Saludos

Answer 1

Ampliando el comentario de Arturo Magidin, hay un algoritmo que encuentra el inverso de un elemento $\overline{a} \in \mathbb{Z}_n$ (que no implica revisar todos los elementos), asumiendo que dicho inverso existe. De hecho, el inverso de $\overline{a}$ existe si y solo si $a$ y $n$ son coprimos, y por lo tanto, dado que $\gcd(a, n) = 1$, la Identidad de Bézout implica que $\exists \ \alpha, \ \beta \in \mathbb{Z}$ tal que $\alpha a + \beta n = 1$. $\alpha$ y $\beta$ pueden determinarse con el Algoritmo de Euclides Extendido. Ahora, tienes: $$\alpha a = 1- \beta n \equiv 1 \ \left(\text{mod} \ n \right) \Rightarrow \overline{\alpha} = \overline{a}^{-1} \ \text{en} \ \mathbb{Z}_n $$ por lo que el inverso de $\overline{a}$ ha sido determinado. Si deseas calcular $\frac{\overline{b}}{\overline{a}}$, simplemente multiplica $\overline{b}$ por $\overline{\alpha}$.
Como se señala en los comentarios, si estás tratando con $n$ pequeños, como $7$, revisar todos los demás elementos de $\mathbb{Z}_n$ probablemente sea más rápido que determinar los coeficientes de la Identidad de Bézout; sin embargo, para $n$ grandes el Algoritmo de Euclides Extendido es más eficiente que una revisión exhaustiva: el primero tiene complejidad temporal $O(\log^2(n))$ mientras que el segundo $O(n)$ (ver Buchmann - una Introducción a la Criptografía).