1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ And the reason is that otherwise p would not be a prime? $\endgroup$ – Tomas Smith Nov 2 '15 at 18:19
  • $\begingroup$ 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. $\endgroup$ – fleablood Nov 2 '15 at 18:51
  • $\begingroup$ 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. $\endgroup$ – fleablood Nov 2 '15 at 18:54
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.