Prueba de GCD y números primos

Question

Me preguntaba cómo probar la siguiente afirmación: Para un número primo $p$ y enteros $n$ , demuestre que $$p = \prod_{k=0}^{p-1} \gcd(n+k,p).$$

Creo que sólo se trata de mostrar que uno de los $\gcd$ es $p$ pero no estoy seguro de cómo procedería tal prueba.

Answer 1

Exactamente uno de $n,n+1,n+2,\ldots,n+(p-1)$ es divisible por $p$ . Por lo tanto, exactamente uno de $\gcd(n,p),\gcd(n+1,p),\gcd(n+2,p),\ldots,\gcd(n+(p-1),p)$ es igual a $p$ y todos los demás son iguales a $1$ .

De forma más general, exactamente uno de $n,n+1,n+2,\ldots,n+(k-1)$ es divisible por $k$ , lo que se debe a que claramente $$\{n\bmod k,n+1\bmod k,\ldots,n+(k-1)\bmod k\}=\{0,1,2,\ldots,k-1\}$$

Answer 2

$\gcd(x, y) \mid y$ . Así que si $p$ es primo entonces $\gcd(x, p) \mid p$ . Así que $\gcd(x, p) = 1$ o $p$ . Así que $\gcd(x, p) = p$ si $p \mid x$ . Y $\gcd(x, p) = 1$ si $p$ no divide $x$ .

Dejemos que $n = mp - i$ ; $0 \leq i < p$ . Entonces $p \mid n + i$ pero $p$ no divide ningún $n + k$ donde $k$ no es igual a $i$ y $0 \leq k < p$ .

Así que $$\prod_{k = 0}^{p - 1} \gcd(n + k, p) = \prod_{k = 0}^{p - 1} \{p \textrm{ if } k = i; 1 \textrm{ if } k \ne i \} = 1.1.1 \ldots p \ldots 1.1.1 = p.$$