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

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

share|cite|improve this question
Please write the question in the question and not in the title. – Asaf Karagila Oct 9 '10 at 18:33
Hmm, what does the question have to do with linear algebra? – Rasmus Oct 10 '10 at 13:32
@Rasmus: There is innate linearity in that a set of common multiples is closed under integral linear combinations - which is the key to this problem. This leads to the notion of an ideal (R-module) in a ring as a generalization of a set of common multiples. Because of this, linear algebra (module theory) plays a big role in number theory. – Bill Dubuque Oct 10 '10 at 14:35
@Bill: Interesting, thanks! – Rasmus Oct 10 '10 at 14:54

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

share|cite|improve this answer
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

share|cite|improve this answer
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$

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.