Multiplicativa grupo de los enteros modulo n definición de problemas

Question

Es fácil comprobar que el conjunto de $(\mathbb{Z}/n\mathbb{Z})^\times$ es cerrado bajo la multiplicación en el sentido de que $a, b ∈ (\mathbb{Z}/n\mathbb{Z})^\times$ implica $ab ∈ (\mathbb{Z}/n\mathbb{Z})^\times$, y es cerrado bajo la recíproca, en el sentido de que $a ∈ (\mathbb{Z}/n\mathbb{Z})^\times$ implica $a^{-1} ∈ (\mathbb{Z}/n\mathbb{Z})^\times$.

La pregunta es la siguiente:

En primer lugar, se $a$ $b$ se refieren a cada clase de equivalencia de los enteros modulo $n$?

En segundo lugar, por $a^{-1}$, lo que se esta refiriendo? Si $a$ es la equivalencia de la clase, no puedo ver (o no estoy seguro) ¿cómo puedo hacer inverso conjunto.

Answer 1

A la primera pregunta, citando su introducción, "$a,b\in(\mathbb{Z}/n\mathbb{Z})^{\times}$". Así que si $\mathbb{Z}/n\mathbb{Z}$ es un conjunto de clases de equivalencia, entonces sí, $a$ $b$ son clases de equivalencia.

A la segunda pregunta, $a^{-1}$ es una clase de equivalencia tal que $aa^{-1}$ es la clase de equivalencia de a $1$. En general, no hay ninguna fórmula para encontrar un elemento de $a^{-1}$$a$. En su lugar, ya que un representante de $A$ $a$ $n$ son relativamente primos, el algoritmo de Euclides ofrece soluciones a la ecuación $$AB + nt = 1$$ Then mod $n$, $AB\equiv 1$. So the Euclidean algorithm will lead you to a representative of $^{-1}$.

Ahora, a vender un poco, en realidad no es más bien una fórmula simple para que un representante de $a^{-1}$, dado un representante de $A$$a$. Tome $B=A^{\varphi(n)-1}$ donde $\varphi$ es de Euler totient función. A continuación,$AB=A^{\varphi(n)}\equiv1\mod{n}$. El problema con este "sencillo" la fórmula es que no es computacionalmente eficiente. Por ejemplo, si $n=97$, el algoritmo de Euclides rápidamente nos dice que $2^{-1}=49$. Pero esta fórmula nos daría $2^{96}$, lo cual es molesto para calcular incluso si reducimos en cada multiplicación.

Answer 2

La notación $a \in (\mathbb{Z} / n \mathbb{Z})^\times$ significa que la variable $a$ se utiliza para referirse a un elemento de $(\mathbb{Z} / n \mathbb{Z})^\times$.

Si usted representa a los elementos de $(\mathbb{Z} / n \mathbb{Z})^\times$ como clases de equivalencia, a continuación,$a$, siendo un elemento de $(\mathbb{Z} / n \mathbb{Z})^\times$, tiene una representación como una clase de equivalencia.

La estructura de $(\mathbb{Z} / n \mathbb{Z})^\times$ es un grupo abelian. Tiene un grupo de operación, una relación inversa, y un elemento neutro. Como estamos escribiendo este grupo con la notación multiplicativa, adoptamos el valor predeterminado de la notación ${}^{-1}$ para la operación inversa de la del grupo.

Como un aparte, creo que concentrarse en un objeto de "ser" una clase de equivalencia en realidad oculta la simplicidad de lo que está pasando. Clases de equivalencia son con frecuencia sólo un conjunto técnico-teórico truco.

Una bastante buena de la notación para los elementos del anillo de $\mathbb{Z} / n \mathbb{Z}$ es que los elementos son representados por números enteros. No sólo los números enteros en el rango de $\{ 0, 1, \cdots, n-1\}$, pero cualquier número entero. El mismo elemento que tiene muchas anotaciones; por ejemplo, '3' y '10' hay dos notaciones para el mismo elemento de $\mathbb{Z} / 7 \mathbb{Z}$.

Esto puede ayudar a añadir una decoración para ayudar a mantener un registro de cuando se utiliza '3' para referirse a un elemento de $\mathbb{Z}$ y cuando se utiliza para denotar un elemento de $\mathbb{Z} / 7 \mathbb{Z}$: opciones comunes son $\overline{3}$ $[3]$ o, a veces,$[3]_7$.

Si se representan los elementos de la $\mathbb{Z} / n \mathbb{Z}$ como clases de equivalencia, a continuación, el elemento $[3]$ es la notación para el elemento representado por la clase de equivalencia de 3. A pesar de que el hecho de que, normalmente, no debería estar pensando "$[3]$ es una clase de equivalencia": usted debe estar pensando "$[3]$ es el elemento de la $\mathbb{Z} / n \mathbb{Z}$ que viene desde el entero 3".

Answer 3

Primero: sí, $a$ $b$ representan las clases de equivalencia módulo $n$.

Segundo: Bien, $a^{-1}$ es no a la inversa como un número racional. Más bien, es la única clase de equivalencia módulo $n$ (si existe) de forma tal que $aa^{-1}$ es congruente con 1 módulo $n$. Y para la existencia, este inversa existe si y sólo si $a$ es coprime a $n$.

Answer 4

Bien $2\cdot 3\equiv 1\; \text{mod}\ 5$, lo $2$ $3$ son inversos multiplicativos $\text{ mod } 5$.

Cómo encontrar el inverso de un número de módulo de un número primo fue el tema de una de mis respuestas anteriores. Módulo de un número compuesto, la recíproca no siempre existen.

Ver el Cálculo de la estructura Modular del Inverso Multiplicativo sin todos los símbolos de extraño aspecto por el camino para encontrar la inversa de a $322$ mod $701$. Resulta ser $455$

Answer 5

En primer lugar, sí.

En segundo lugar, por $a^{-1}$ nos referimos a la única clase de equivalencia tal que la multiplicación de (la clase de equivalencia) $a$ $a^{-1}$ da (la clase de equivalencia) $1.$

Por ejemplo, en $(\mathbb Z/4\mathbb Z)^\times=\{1,3\}$ tenemos $1\cdot 1\equiv 1$ $1^{-1}=1$ $3\cdot 3=9\equiv 1$ $3^{-1}=3.$