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

Question

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.

Answer 1

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

Answer 2

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*}

Answer 3

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

Answer 4

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)$$

Answer 5

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