How to show that $\gcd(n! + 1, (n + 1)! + 1) \mid n$?

Question

Let $n$ be a positive integer, $n!$ denotes the factorial of $n$. Let $d = \gcd(n! + 1, (n + 1)! + 1)$. Show that $d$ divides $n$. (Hint: notice that $(n+1)(n!+1) = (n+1)!+n+1$)

Answer 1

HINT: Use the definition of GCD and the fact that $$(n+1)!+1 = n! \times (n+1) +1 = n! \cdot n + (n!+1)$$ We know that $d \mid (n!+1)$ since $d$ is the GCD

Answer 2

The given hint shows that $\rm\ n\ $ is an integral linear combination of $\rm\ n!+1\ $ and $\rm\ (n+1)! + 1\:,\: $ so $\rm\ n\ $ is divisible by all common divisors, including the GCD. In fact we can go further and show that the GCD = 1. Namely, since the GCD divides the coprime numbers $\rm\:n\:$ and $\rm\ n!+1\ $ it must be 1. Below is an alternate derivation using explicit gcd laws, along with an explicit Bezout linear representation of the GCD.

Putting $\rm\ k = n!+1\ $ below shows that the GCD equals $\rm\ gcd(n!+1,n) = 1$.

$\rm\quad\quad\ \ gcd(k,(n+1)k-n)\ =\ gcd(k,n)\ \ $ via $\rm\ \ n = (n+1)k - ((n+1)k-n)$

$\quad\quad$ recalling $\rm\quad\quad\ \ gcd(k,m)\ =\ gcd(k,\:jk\pm m)\ $

$\quad\quad$ since if $\rm\ \ d|k\ $ then $\rm\ \: d|m\ \ \iff\ \: d\ |\ jk\pm m\quad\ \ $ Above $\rm \ j = n+1 $

In fact we can unwind the above to obtain an explicit Bezout linear representation of the GCD:

$\quad\quad\quad\quad\quad \rm n\ =\ n!\ ((n+1)!+1) + (n-(n+1)!)\ (n!+1) $

Dividing the above through by $\rm\:n\:$ shows that the gcd is 1! $\ $ But, alas, I fear I've exclaimed too much ...

Answer 3

As $(n+1)(n!+1)=(n+1)!+n+1$, so $n=(n+1)(n!+1)-((n+1)!+1)$, let $d=\text{gcd}(n!+1,(n+1)!+1)$, then $d\mid(n!+1)$ and $d\mid((n+1)!+1)$, so $d\mid n$, this means that $\text{gcd}(n!+1,(n+1)!+1)\mid n$