Quiero hacer una pregunta sobre aritmética modular. Sé que la inversa multiplicativa modular sólo existe si el módulo y el entero son relativamente primos. Quiero saber, ¿hay alguna forma de división en aritmética modular, si módulo y entero no son relativamente primos? Intenté encontrar información al respecto, pero no lo conseguí.
Respuestas
¿Demasiados anuncios?
A continuación explico cómo ver la división modular a través de (posiblemente de valores múltiples ) fracciones modulares.
Considere $\,x\equiv A/B\pmod{\!M},\,$ es decir, el solución s de $\ B\, x \equiv A\pmod{\!M}.\, $ Sea $\,d=\gcd(B,M).\,$ Entonces $\, d\mid B,\,\ d\mid M\mid B\,x\!-\!A\,\Rightarrow\, d\mid A\ $ es un necesario condición para existencia de soluciones.
Si es así, que $\ m, a, b \, =\, M/d,\, A/d,\, B/d.\ $ Entonces cancelando $\,d\,$ a lo largo de los rendimientos
$$ x\equiv \dfrac{A}B\!\!\!\pmod{\!M}\iff M\mid B\,x\!-\!A\!\! \overset{\large {\ \ \color{#c00}{{\rm cancel}\ d}}}\iff m\mid b\,x\! -\! a \iff x\equiv \dfrac{a}b\!\!\!\pmod{\!m}$$
donde la fracción $\ x\equiv a/b\pmod{\! m}\,$ indica todos soluciones de $\,ax\equiv b\pmod{\! m},\, $ y análogamente para $\, $ el $\, $ fracción $\ x\equiv A/B\pmod{\!M}.\ $
El argumento anterior implica que si existen soluciones, entonces podemos calcular el conjunto completo de soluciones mediante $\color{#c00}{{\rm cancelling}\ d} = (B,M)\,$ del numerador $\,A,\,$ el denominador $\,B\,$ $\rm\color{#c00}{and}$ el módulo $\,M,\,$ es decir
$$ \bbox[8px,border:1px solid #c00]{x\equiv \dfrac{a\color{#c00}d}{b\color{#c00}d}\!\!\!\pmod{\!m\color{#c00}d}\iff x\equiv \dfrac{a}b\!\!\!\pmod{\! m}}\qquad$$
Si $\, d>1\, $ entonces $\, x\equiv A/B\pmod{\!M}\,$ es de valores múltiples, teniendo $\,d\,$ soluciones en AP, a saber
$$\quad\ \begin{align} x \equiv a/b\!\!\pmod{\! m}\, &\equiv\, \{\, a/b + k\,m\}_{\,\large 0\le k<d}\!\!\pmod{\!M},\ \ M = md\\ &\equiv\, \{a/b,\,\ a/b\! +\! m,\,\ldots,\, a/b\! +\! (d\!-\!1)m\}\!\!\pmod{\! M} \end{align}$$
lo cual es cierto porque $\ km\bmod dm =\, (\color{#c00}{k\bmod d})\, m\ $ por el mod Ley Distributiva , $ $ y el RHS toma exactamente $\,d\,$ a saber $\,\color{#c00}0m,\, \color{#c00}1m,\, \color{#c00}2m, \ldots, (\color{#c00}{d\!-\!1})m,\, $ así que ídem para sus turnos por $\,a/b$ .
$ {\rm e.g.} \overbrace{\dfrac{6}3\pmod{\!12}}^{{\rm\large cancel}\ \ \Large (3,12)\,=\,\color{#c00}3}\!\!\!\!\equiv \dfrac{2}{1}\!\pmod{\!4}\equiv \!\!\!\!\!\!\!\!\!\!\!\!\!\!\overbrace{\{2,6,10\}}^{\qquad\ \ \,\Large\{ 2\ +\ 4k\}_{\ \Large 0\le k< 3}}\!\!\!\!\!\!\!\!\!\!\!\!\!\pmod{\!12},\ $ en efecto $\ 3\{2,6,10\}\equiv \{6\}$
Obsérvese, en particular, que una "fracción" modular puede denotar cero, una o varias soluciones.
Observación $ $ Una buena aplicación de las fracciones modulares es la fraccionario algoritmo euclidiano ampliado descrito en el Observación. Allí encontrarás ejemplos explícitos de la intersección de conjuntos de soluciones de fracciones modulares con valores múltiples.
Per Hornshøj-Schierbeck
Puntos
4610
Se puede cancelar un factor común a ambos lados de una congruencia Y el módulo. La justificación de esto es que para cualquier entero distinto de cero $d$ tenemos $dm\mid (da-db)$ sólo si $m\mid (a-b)$ . Escrito como congruencias se lee $$da\equiv db\pmod{dm}\Longleftrightarrow a\equiv b\pmod m.$$
Así, por ejemplo, la congruencia $$6x\equiv 8\pmod {10}$$ es equivalente a la congruencia $$3x\equiv4\pmod5.$$ Esta vez terminaste con una congruencia lineal donde la condición de coprimidad $\gcd(3,5)=1$ se mantiene, y se puede proceder a resolver esta congruencia con los métodos habituales.
Obsérvese también que a menudo es fácil demostrar que una congruencia lineal no tiene soluciones cuando falla la condición gcd. Consideremos $$6x\equiv 7\pmod{10}.$$ Aquí $6x$ es siempre par, al igual que $10$ pero $7$ no lo es. Por lo tanto esta congruencia no puede tener ninguna solución en $\Bbb{Z}$ .
