# GCD and Prime Numbers Proof

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.

• And the reason is that otherwise p would not be a prime? – Tomas Smith Nov 2 '15 at 18:19
• Well, it should scream at you like a hammer on an ingrown thumbnail, that if it is true and p is prime, then exactly one of the gcd(n + k,p) = p and the rest of the gcd(n+k, p) = 1 otherwise p isn't prime. – fleablood Nov 2 '15 at 18:51
• gcd(x, p) = 1 or p because gcd(x,p) | p and only 1 and p divide p. So gcd(x,p) = p if p|x and gcd(x,p) = 1 if p does not divide x. – fleablood Nov 2 '15 at 18:54

## 2 Answers

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

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\}$$