Producto de $x$ con $x$ y $x+1$ siendo coprima de $n$

Question

Para un entero positivo impar $n \gt 1$ , dejemos que $S$ sea el conjunto de enteros $x$ , $1 \le x \le n$ , de tal manera que ambos $x$ y $x+1$ son relativamente primos a $n$ . Demostrar que $$\prod_{x\in S} x \equiv 1 \pmod n$$

Sé que ya hay una solución en este sitio aquí pero no entiendo del todo la solución y el hilo fue creado hace más de 3 años por lo que he decidido crear un nuevo hilo. ¿Alguien puede traducir la solución presentada en el hilo enlazado? En mi planteamiento he pensado en utilizar $CRT$ pero no he podido resolver el problema usándolo, así que si conoces la solución que implica $CRT$ por favor, publíquelo.

Se agradece cualquier ayuda.

Answer 1

Lema $ $ Si $\,S\,$ es un subconjunto de $\,\Bbb Z_n\,$ cerrado bajo inversiones entonces el producto de sus elementos es igual al producto del conjunto de raíces de $\,x^2-1\,$ acostado en $\,S$ .

Prueba $\ S$ particiones en pares $\,(x,x^{-1})$ con $\,x\not\equiv x^{-1}$ y los solteros $(x)$ con $\,x^{-1}\equiv x.\,$ Las parejas contribuyen $\,1\,$ al producto, por lo que se reduce al producto de los singletons = raíces de $\,x^2\equiv 1$ .

---

Su $S\,$ es cerrado bajo inversos, es decir $\,(n,x(x\!+\!1))=1\Rightarrow\,(n,x^{-1}(x^{-1}\!+\!1))=1,\,$ desde $\,x^2\, x^{-1}(x^{-1}\!+\!1) = 1+x\,$ es coprima de $\,n\,$ por lo que también lo son sus factores $\,x^{-1},\ x^{-1}\!+\!1.$

Si $\,x\in S\:\!$ y $\,x^2\!-1\equiv (x\!-\!1)(x\!+\!1)\equiv 0\, $ entonces $\,x\!-1\equiv 0,\,$ por $\,x\!+\!1\,$ es cancelable, siendo coprima a $\,n.\,$ Por tanto, el conjunto de raíces de $\,x^2\!-1\,$ en $\,S\,$ es $\{1\},\,$ con el producto $1 = \prod S\,$ a través de Lemma.

Nota: $ $ Esto está estrechamente relacionado con esta prueba elemental de una generalización del teorema de Wilson a $\,\Bbb Z_n,\,$ basado en una simetría de reflexión (involución) similar afianzada por la inversión.

Answer 2

Desde $x$ es relativamente primo con $n$ existe algún $y$ s.t. $xy \equiv 1 \mod {n}$ . Supongamos ahora que $x \ne y \mod{n}$ . Entonces observe que $y+1 \equiv \frac {1}{x} +1 \equiv \frac {1+x}{x}\mod {n}$ . Dado que ambos $x+1$ y $x$ son relativamente primos con $n$ tienen inversos muliplicativos respectivos a modulo $n$ . Así, a partir de la igualdad anterior, $y+1$ tiene necesariamente un inverso multiplicativo. Pero esto implica que $ y+1 $ y $n$ son relativamente primos. Además $ y $ y $n$ son relativamente primos (ya que $x$ es la inversa multiplicativa de $y$ Por lo tanto $y \in S$ . Si $x = y$ entonces $x^2 \equiv 1 \mod{n}$ lo que implica $(x-1)(x+1) \equiv 0 \mod{n}$ . Pero como $x+1$ es relativamente primo con $n$ tiene una inversa y esto implica que $x\equiv 1 \mod {n}$ . Por lo tanto, si $x \in S $ y x no es igual a su inverso multiplicativo $y$ en el módulo $n$ , $y \in S$ ,si no $x\equiv 1 \mod {n}$ .