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

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

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

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

Solution 4:

Hint $\ $ Put $\, k = n!\,$ in the following Euclidean gcd reduction

$$(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]$$

Generally $\ (k\!+\!1,f(k)) = (k\!+\!1,f(-1))\,\ $ [$=1\,$ if $\,f(-1)\mid k\,$] where the first equality employs gcd modular reduction combined with the polynomial remainder theorem, i.e. $\bmod k\!+\!1\!:\ \,\color{#c00}{k\equiv -1}\Rightarrow f(\color{#c00}k)\equiv f(\color{#c00}{-1}),\,$ for any polynomial $\,f(x)\,$ with integer coefficients. Above we have $\,f(x) = (n\!+\!1)x+1\,$ so $\,f(-1) = -n$