GCD and Prime Numbers Proof

Question

I was wondering how to prove the following statement: For a prime number $p$ and integer $n$, prove that $$p = \prod_{k=0}^{p-1} \gcd(n+k,p).$$

I think it just comes done to showing that one of the $\gcd$s is $p$ but I am not sure how such a proof would proceed.

Answer 1

$\gcd(x, y) \mid y$. So if $p$ is prime then $\gcd(x, p) \mid p$. So $\gcd(x, p) = 1$ or $p$. So $\gcd(x, p) = p$ if $p \mid x$. And $\gcd(x, p) = 1$ if $p$ does not divide $x$.

Let $n = mp - i$; $0 \leq i < p$. Then $p \mid n + i$ but $p$ does not divide any $n + k$ where $k$ does not equal $i$ and $0 \leq k < p$.

So $$\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.$$

Answer 2

Exactly one of $n,n+1,n+2,\ldots,n+(p-1)$ is divisible by $p$. Therefore exactly one of $\gcd(n,p),\gcd(n+1,p),\gcd(n+2,p),\ldots,\gcd(n+(p-1),p)$ is equal to $p$ and all the others are equal to $1$.

More generally, exactly one of $n,n+1,n+2,\ldots,n+(k-1)$ is divisible by $k$, which is because clearly $$\{n\bmod k,n+1\bmod k,\ldots,n+(k-1)\bmod k\}=\{0,1,2,\ldots,k-1\}$$