Dividiendo y multiplicando por el inverso

Question

Yo estaba trabajando en un problema que resultó en el cálculo: $20 \equiv 10x \pmod{11}$.

Tengo la respuesta $x \equiv 2 \pmod{11}$ con el proceso de pensamiento: Desde $10$ es un factor de $20$ me puede reescribir $20 \pmod{11}$$10x \pmod{11}$$x=2$. Pero no es esto básicamente el mismo que usando la división, que no estamos supuestos a hacer en espacios modulares?

Si puedo resolver multiplicando $20$ por el inverso multiplicativo de a$10 \pmod{11}$$10$, I se $200 \pmod{11}$, con lo cual se simplifica a $2 \pmod{11}$, de todos modos. ¿Estos números acaba de pasar a ser el mismo o es mi método original válido?

Answer 1

Su método original funciona sólo porque $10$ tiene una inversa modulo $11$. Escribió $20 \equiv 10x \pmod{11}$ $$ 10(2) \equiv 10x \pmod{11}. $ $ ahora, usando el hecho de que $10^{-1}$ existe, podemos multiplicamos por él a la conclusión de $2 \equiv x \pmod{11}$. Si $10$ no invertible, no podríamos concluir esto. Por ejemplo, $2(2) \equiv 2(3) \pmod{2}$, $2\not\equiv 3 \pmod{2}$.

Answer 2

Invertible elementos siempre son rescindibles: $\,a^{-1}$ veces $\,ab\equiv ac\,\Rightarrow\,b\equiv c,\,$ es decir $\,x\mapsto ax\,$ es $1$-$1$. Además: $\ a\,$ es invertible mod $m\iff a\,$ es coprime a $m\iff x\mapsto ax\,$ a, ver

Teorema $\ $ Los siguientes son equivalentes para los números enteros $\rm\:a,\, m.$

$(1)\rm\ \ \ gcd(a,m) = 1$
$(2)\rm\ \ \ a\:$ es invertible $\rm\,(mod\ m)$
$(3)\rm\ \ \ x\to ax\:$ es $\:1$-$1\:$ $\rm\,(mod\ m)$
$(4)\rm\ \ \ x\to ax\:$ es a $\rm\,(mod\ m)$

Prueba de $\ (1\Rightarrow 2)\ $ Por Bezout $\rm\, gcd(a,m)\! =\! 1\Rightarrow ja\!+\!km =\! 1\,$ $\rm\,j,k\in\Bbb Z\,$ $\rm\Rightarrow ja\equiv 1\!\pmod{\! m}$
$(2\Rightarrow 3)\ \ \ \rm ax \equiv ay\,\Rightarrow\,a(x\!-\!y)\equiv 0\,\Rightarrow\,x\!-\!y\equiv 0\,$ multiplicando por $\rm\,a^{-1}$
$(3\Rightarrow 4)\ \ $ Cada $1$-$1$ función de un conjunto finito es en (palomar).
$(4\Rightarrow 1)\ \ \ \rm x\to ax\,$ a, lo $\rm\,aj\equiv 1,\,$ $\rm\,j,\,$ es decir $\,aj\!+\!km = 1,\,$ $\rm\,k,\,$ $\rm\gcd(a,m)=1$

Ver aquí para una conceptuales prueba de dicho identidad de Bezout para el mcd.

Answer 3

Deje $m$ ser cualquier número entero para el que puede definir la equivalencia modulo $m$ en la forma habitual. Si $a = by$ ordinario de la aritmética más enteros $a,$ $b,$ y $y,$ y si $x \equiv y \pmod m,$ a continuación, $a \equiv bx \pmod m.$

Su método de solución de $20 \equiv 10x \pmod {11}$ básicamente se reduce a la observación de que $y = 2$ es una solución para la ecuación de $20 = 10y.$ Eso es suficiente para concluir que el $x \equiv 2 \pmod {11}$ es una solución de $20 \equiv 10x \pmod {11}.$

Aviso de la cuidadosa redacción: "una solución" en lugar de "lasolución". (En un poco más formal del lenguaje, "un miembro de la solución" en lugar de "el uno y el único miembro de la solución.")

Por ejemplo, si aplicamos este método para el problema $4 \equiv 2x \pmod6,$ va correctamente nos dicen que $x\equiv2 \pmod6$ es una solución; pero $x\equiv5 \pmod6$ también es una solución, aunque este método nunca se nos informe acerca de esa solución.

El hecho de que $10$ tiene una inversa modulo $11$ es lo que hace que su solución la solución en lugar de sólo una solución.