¿Por qué no podemos tener un $y$ tal que $xy\equiv 1\; (mod\; n)$ al $n$ no es primo?

Question

Estoy leyendo Avner del Intrépido Simetría:

Aquí dice que solo podemos tener la cancelación de la ley si el módulo es el primer:

Me picó la curiosidad con la declaración y luego seguí leyendo el capítulo:

Luego he comprobado la definición e hizo dos tablas, tratando de ver si podía encontrar realmente el $y$ tal que $xy \equiv 1 \; (mod \;n)$, $n$ no de una prima. Mi pequeño experimento rendimientos:

Estoy muy curioso en dos puntos:

• ¿Por qué no podemos tener un $y$ tal que $xy\equiv 1\; (mod\; n)$ al $n$ no es primo? La respuesta puede ser trivial, pero no lo encuentro.
• Más adelante en el libro (ver abajo), él le dice que es posible tener un campo con un número compuesto de elementos, en este caso supongo que la declaración hecha en la última pregunta no tiene. Así, teniendo en cuenta la necesidad de la existencia de una $y$ tal que $xy\equiv 1\; (mod\; n)$ al $n$ no es primo, ¿cómo es posible tener un número compuesto de elementos?

Answer 1

No puede ser, ciertamente, algunos $x$ para los que hay un $y$$xy \equiv 1 \,(\textrm{mod } n)$, incluso si $n$ no es primo. De hecho, se puede demostrar que para arbitrario $n$ $$ \text{Hay un $y$} xy \equiv 1 \,(\textrm{mod } p) \quad\Leftrightarrow\quad \textrm{mcd}(x,n) = 1 \text{.} $$

Sin embargo, si $n$ no es primo, entonces siempre hay algunos $x < n$, $x \geq 1$ con $\textrm{gcd}(x,n) \neq 1$ (elija sólo uno de los factores de $n$$x$), y por lo que nunca tiene que para todos los $x \neq 0$ hay un $y$$xy \equiv 1 \,(\textrm{mod }n)$. Pero podemos también encontrar siempre $x$ que $\textrm{gcd}(x,n) = 1$ incluso $n$ no es primo, tomemos, por ejemplo,$x = n-1$. (Esto viene a decir que $(-1)^2 \equiv 1 \,(\textrm{mod }n)$ todos los $n$).

Si, por otro lado, $n$ es primo, entonces $\textrm{gcd }(x,n) = 1$ para todos los $x < n$, $x \geq $, por lo tanto, en este caso, realmente tenemos que para todos los $x \neq 0$ hay un $y$$xy \equiv 1 \,(\textrm{mod }n)$.

Answer 2

Primera pregunta: supongamos que el $n=pq$ donde $p$ $q$ son mayores de $1$. Entonces, si $x$ es un múltiplo de $p$, $x=kp$, cada múltiplo de $x$ será un múltiplo de $p$. Por lo tanto, $xy$ será un múltiplo de $p$ $xy-1$ no puede ser un múltiplo de $n$. Por supuesto no puede ser de algunos números de $x$ que tiene una inversa mod $n$, pero estas cifras deben ser relativamente primos con $n$.

Segunda pregunta: finito campos puede tener un compuesto cardenal porque ellos no tienen que ser cíclica (es decir, la secuencia de $1, 1+1, 1+1+1, \ldots$ no tienen que contener todos los elementos del campo). Tomemos, por ejemplo, el campo de $\Bbb F_4=\{0,1,x,x+1\}$ donde$1+1=x+x=0$$x^2=1$. El anterior argumento no funciona aquí, ya $x$ no es un "normal", ni un resto de una división. Es un resumen de "cosa" como $i$, la unidad imaginaria.

Estos argumentos son bastante intuitivo, porque sentí que usted está pidiendo este tipo de argumentos. Espero que sean útiles para usted.