Un entero $a \pmod m$ tiene inversa si y sólo si $\gcd(a,m)=1$?

Question

Un entero $a \pmod m$ tiene inversa si y sólo si $\gcd(a,m)=1$?

¿Por qué es esto? Traté de comprensión de mis notas pero no lo entiendo.

Una explicación detallada sería muy bienvenida.

Gracias por todas las respuestas hasta el momento. Creo que mi mayor problema es entender el porqué de la $\gcd(a,m)\neq1 \Longrightarrow \not\exists a^{-1}$.

Answer 1

Si $\gcd(a,m)=1$, entonces podemos encontrar una $x$ $y$ tal que $ax+my=1$ a través del algoritmo de Euclides. Por lo tanto $ax =1-my \equiv 1 \pmod{m}$. Por lo tanto $a$ tiene una inversa.

Por el contrario, si $a \pmod{m}$ tiene una inversa entonces existe un $x$ tal que $ax \equiv 1 \mod{m}$, lo que es lo mismo que decir que existe un $y$ tal que $ax = 1+my$ o $ax-my=1$, lo que implica, por el algoritmo de Euclides, que $\gcd(a,m)=1$

Answer 2

Todo se basa en el teorema de Bézout: $$\gcd(a,m)=1\iff \exists\, u,v\in\mathbf Z\enspace \text{such that}\enspace ua+vm=1$$ Este teorema muestra que, si $\gcd(a,m)=1$,$vm\equiv 1\mod a$.

Por el contrario, si $\,vm\equiv 1\mod a$, significa que existe $u\in\mathbf Z$ tal que $vm=1+ua$, de donde $-ua+vm=1$, por lo que el $\gcd(a,m)=1$.

Answer 3

$\exists x \in \mathbb{Z}$ s.t. $ ax \equiv 1$ mod $m \iff \exists n \in \mathbb{Z}$ s.t. $ax - nm = 1$.

Luego, si nos vamos a $d = gcd(a,m)$:

$d$ $| a$ y $d$ $| m$ así $d$ $|(ax-nm)$ y así $d$ $|1$ y por lo $d = 1$

Por el contrario si $ d = 1$, ser de Bézout del Lema, podemos encontrar $n,x \in \mathbb{Z}$ s.t. $ax - mn = 1$ como se requiere.

Answer 4

Podemos utilizar la computación modulo $10$ como un ejemplo.

Los números de $a$ que no son de primer a $10$ son los números, y los múltiplos de $5$. Una inversa de a $a$ modulo $10$ es cualquier número $a'$ tal que $a a' \equiv 1 \pmod{10}$ o, $aa'$ termina con el dígito $1$.

Ahora, ¿por qué para un número $a$, es imposible encontrar a $a'$ tal que $aa'$ termina con $1$ ? Y para $a$ varios de $5$ ?

Esto generaliza bien a una prueba de: si $d=\gcd(a,m) \neq 1$, $a$ no es invertible modulo $m$; es decir, para cualquier $a'$, $d$ divide tanto a a$aa'$$m$, y por lo tanto, para cualquier $a'$ y $t$, $aa' - t m$. Esto implica que $aa' - t m$ siempre va a ser $\neq 1$; o que $aa' \not \equiv 1 \pmod{m}$.

De lo contrario la dirección, es un poco menos obvio, pero no más difícil. Es decir, que ya deberían saber la identidad de Bézout: es decir, si $d = \gcd (a,m)$, entonces no existe $a', m'$ tal que $aa' + mm' = d$. Si $d = 1$, a continuación, inmediatamente, esto significa que $aa' \equiv 1 \pmod{m}$.

Answer 5

si $a$ tiene una inversa llama$x$,$ax=1\mod m$, por lo que no es combinación lineal de $a$ $m$ que es igual a 1. otro lado:si tenemos una combinación lineal de $m$ $a$ que es igual a 1 ,la inversa de a $a$ es exactamente el coeficiente de $a$.