Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
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
4  
Please write the question in the question and not in the title. –  Asaf Karagila Oct 9 '10 at 18:33
1  
@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 3

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|improve this answer
2  
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

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

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

Your Answer

 
discard

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.