Demostrar que: set $\{1, 2, 3, ..., n - 1\}$ es grupo bajo multiplicación módulo $n$ ?

Question

Demuéstralo:

El conjunto $\{1, 2, 3, ..., n - 1\}$ es un grupo bajo multiplicación modulo $n$ sólo si $n$ es un número primo sin utilizar la función phi de Euler.

Answer 1

EDIT: Parece que la pregunta ha cambiado. Creo recordar que preguntaba por qué, en el conjunto $ \{ 1, 2, 3, ... n-1 \} $ equipado con multiplicación módulo $n$ existen inversos si y sólo si $n$ es un número primo. De cualquier manera, lo siguiente sólo responde por qué existen los inversos (esto hace la mayor parte del trabajo en mostrar que es un grupo, de todos modos):

Ambas direcciones se desprenden de Lemma de Bézout (que a su vez se deduce de Algoritmo de Euclides ): Sea $a, b, c $ sean números naturales. Entonces existen enteros $u ,v $ tal que $ au + bv = c $ sólo si $ \mbox{hcf}(a,b) | c $ .

Esto demuestra fácilmente su dirección "si": si $n$ es primo, entonces $\mbox{hcf}(k,n) = 1 $ para todos $k$ en $ \{ 1,2,3, ... n-1 \}$ . Por tanto, existen enteros $u, v$ tal que $ ku + nv = 1 $ es decir $ ku = 1 \ (\mbox{mod } n)$

Para demostrar el sentido "sólo si", obsérvese que cada $k$ en $ \{1, 2, 3, ... n-1\} $ que tiene un inverso multiplicativo implica la existencia de enteros $u,v$ tal que $ ku + nv = 1 $ . Así que $\mbox{hcf}(k,n) | 1 $ para todos $k$ es decir $ \mbox{hcf}(k,n) = 1 $ para todos $k$ . ¿Puedes ver por qué esto significa $n$ ¿es primo?

Answer 2

Tenga en cuenta que si $ab\equiv 1 \pmod{n}$ entonces $\gcd(n,a)=\gcd(n,b)=1$ . Entonces, ¿qué elementos podrían tener inversos multiplicativos?

Answer 3

Supongamos que $H=\{1,2,3,...n-1\}$ es un grupo. Supongamos que $n$ no es un primo.

Entonces $n$ es compuesto, es decir $n=pq$ para $1<p,q<n-1$ . Esto implica que $pq \equiv0(mod n)$ pero $0$ no está en H. Contradicción, por tanto $n$ debe ser primo.

A la inversa, supongamos $n$ es un primo, entonces $gcd(a,n)=1$ para cada a en H. Por lo tanto, $ax=1-ny$ , $x,y \in H$ . Así que.., $ax\equiv1(modn)$ . Es decir, cada elemento de H tiene un inverso. Esto concluye que H debe ser un grupo ya que la identidad está en H y H es asociativo.

Answer 4

CONSEJO $\rm\quad a^{-1}\:$ existe $\rm\: mod\ n\ \iff\ \exists\ b,c\!\!:\ a\:b + c\:n = 1\ \iff\ \gcd(a,n) = 1$

Así que todos naturales $\rm < n\:$ son invertibles $\rm\:mod\ n\:$ si $\rm\:n\:$ es coprimo a todos los naturales menores si $\rm\:n\:$ es primo.

Answer 5

Escribí esta respuesta a lo que es casi la misma pregunta. Si $n$ es primo y $x$ no es múltiplo de $n$ (así que en mod- $n$ , $x$ no es $0$ ), ¿cómo encontrar la inversa multiplicativa de $x$ ? (Otros aspectos para demostrar que la cosa es un grupo son fáciles).

(Un problema más difícil es demostrar que ese grupo multiplicativo es un cíclico grupo).

La otra dirección---que si $n$ no es primo entonces esta cosa no es un grupo, es más fácil.