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

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

-
Motivation? Source? Is this homework? –  Rasmus Oct 9 '10 at 17:02
@Rasmus: I have tagged it as homework! –  anonymous Oct 9 '10 at 17:46
Please write the question in the question and not in the title. –  Asaf Karagila Oct 9 '10 at 18:33
@Chandru1: Why did you tag is at homework? How do you know it's homework? –  Rasmus Oct 9 '10 at 19:30
@Rasmus: This is Further Linear Algebra (university level) homework question. –  Maths student Oct 9 '10 at 20:02

3 Answers

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

-
Thank you! It's very helpful. –  Maths student Oct 9 '10 at 19:47
How would you show that n and n!+1 are coprime? –  Maths student Oct 9 '10 at 20:00
@Maths student: because n!+1 = jn+1, but gcd(n,jn+1) = gcd(n,1) by above. Or explicitly: d|n,jn+1 => d|(jn+1)-jn = 1. Generally its helpful to use the above in the form: gcd(n,k) = gcd(n, k mod n), which is the key reduction step of the Euclidean algorithm. –  Bill Dubuque Oct 9 '10 at 20:07
Thank you once again! Think I got it now :) –  Maths student Oct 9 '10 at 20:18
@Maths student: See my revised answer which is a bit simpler and clearer. –  Bill Dubuque Oct 9 '10 at 21:19

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

-
You've merely restated the hint. –  Bill Dubuque Oct 9 '10 at 18:40
@Bill: BILL, I think i have put it in a form where the answer can is more tangible. –  anonymous Oct 9 '10 at 20:29
@Chandru1: But the given hint already shows that n is an integral linear combination of n!+1 and (n+1)!+1, so we immediately infer that n is divisible by every common divisor, hence by the GCD. Your variant of the hint exhibits n n! (not n) as a linear combination, so it would seem to require more work than the original hint. –  Bill Dubuque Oct 9 '10 at 20:49

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$

-