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$)
How to show that $\gcd(n! + 1, (n + 1)! + 1) \mid n$?
-
4Please write the question in the question and not in the title. – 2010-10-09
-
0Hmm, what does the question have to do with linear algebra? – 2010-10-10
-
0@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. – 2010-10-10
-
0@Bill: Interesting, thanks! – 2010-10-10
-
0See also [Proof that (n!+1,(n+1)!+1)=1](http://math.stackexchange.com/q/25688). – 2016-10-22
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 ...
-
0Thank you! It's very helpful. – 2010-10-09
-
0How would you show that n and n!+1 are coprime? – 2010-10-09
-
0@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. – 2010-10-09
-
0Thank you once again! Think I got it now :) – 2010-10-09
-
0@Maths student: See my revised answer which is a bit simpler and clearer. – 2010-10-09
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
-
2You've merely restated the hint. – 2010-10-09
-
0@Bill: BILL, I think i have put it in a form where the answer can is more tangible. – 2010-10-09
-
0@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. – 2010-10-09
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$