Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How does one show that two general numbers $n! + 1$ and $(n+1)! + 1$ are relatively prime?

I don't mind if someone uses a different example, I want to learn how to prove this class of problems.

My professor seems to really emphasize that you can use the division algorithm, or find the greatest common divisor using the division algorithm rather, in order to assess the nature of relative-prime-ness and I am kind of confused as to how to apply it.

share|cite|improve this question
up vote 30 down vote accepted

Suppose that $d$ divides both. Then $d$ divides $(n+1)(n!+1)$ and $(n+1)!+1$, so it divides their difference, which is $n$.

But if $d$ divides $n!+1$ and $n$, then $d$ divides $n!+1$ and $n!$, so $d$ divides $1$.

share|cite|improve this answer
André tu m'aides avec mes preuves mathematique depuis trois ans, merci encore une fois! (English: Andre you have assisted me with mathematical proofs for the last three years, thanks again!) – Arthur Collé Feb 27 '14 at 0:45
Il n'y a pas de quoi. – André Nicolas Feb 27 '14 at 0:52
"then d divides n! + 1 and n!" – Arthur Collé Feb 27 '14 at 1:05
Because $n$ divides $n!$. – André Nicolas Feb 27 '14 at 1:06

I'll use $\big(a,b\big)$ to denote the gcd of $a$ and $b$. The basic idea of division algorithm is that $(a,b) = (a - kb,b)$ for any integer $k$.

\begin{align*} \Big((n+1)! + 1 \; , \; n! + 1\Big) &= \Big([(n+1)! + 1] - (n+1)[n! + 1] \; , \; n! + 1 \Big) \\ &= \Big((n+1)(n!) - (n+1)(n!) + 1 - (n+1) \; , \; n! + 1 \Big) \\ &= \Big(-n , \; n! + 1 \Big) \\ &= \Big(n , \; n! + 1 \Big) \\ &= \Big(n , \; n! + 1 - (n-1)!(n) \Big) \\ &= \Big(n , \; 1 \Big) \\ &= 1 \\ \end{align*}

share|cite|improve this answer

The key identity is $$\gcd (a,b) = \gcd (a-kb ,b).$$

So, the task is to choose the $k$ such that the expression gets simpler.

In this particular case, it is the plus 1 which is blocking the nice multiplicative structure, so you can choose $k=1$ to eliminate it which gives

$$\gcd ((n+1)!+1,n!+1) = \gcd (n\cdot n! ,n!+1).$$

But this is clearly 1 because every factor of $n\cdot n!$ is relatively prime to $n!+1$.

(Note that the other answers choose $k=n+1$ to eliminate the factorial instead of the 1, so you have usually more than one good option to choose $k$.)

share|cite|improve this answer

Hint $\ $ Let $\, k = n!\,$ below

$$(k\!+\!1,(n\!+\!1)k\!+\!1) = (\color{#c00}{k\!+\!1},(n\!+\!1)(\color{#c00}{k\!+\!1})\!-\!n) = (\color{}{k\!+\!1},-n)\,\ \ \left(\,= 1\ \ {\rm if}\ \ n\mid k\,\right)$$

share|cite|improve this answer

Hint: $$(n+1)!+1\ =\ (n+1)\,n!\,+1 = (n+1)\,(n!+1)\ -\ (n+1)\ +1$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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