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.

I'd like to solve this one similarly to my previous question: Valid proof for (2n+1,3n+1)=1?

I did find a somewhat related post that uses a different method: 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.

So how would I go about this? I can write the above like:

$\exists \ d \ \in \mathbb{Z}$

  1. $n!+1 \equiv 0$ (mod $d$)
  2. $(n+1)!+1 \equiv 0$ (mod $d$)

Not sure what to do next. Any hints?

Thanks!

share|improve this question
    
That's a splendid question. I'm very impressed with how quickly you have learned the basic ideas and quickly applied them to analogous problems. –  Bill Dubuque Mar 8 '11 at 3:32

3 Answers 3

up vote 5 down vote accepted

Here's the purely equational proof. Simply put $\rm\ k = (n-1)!\ $ in

THEOREM $\rm\quad ((n+1)\ n\ k+1,\ n\ k+1)\ =\ 1$

Proof $\ \ $ Working modulo the gcd $\rm\: := d\:$ we have

$(1)\rm\quad\quad (n+1)\ n\ k\ \equiv\: -1\quad\quad$ by $\rm\ d\ |\ (n+1)\ n\ k+1$

$(2)\rm\quad\quad\phantom{(n+1)\ } n\ k\ \equiv\: -1\quad\quad$ by $\rm\ d\ |\ n\ k+1$

$(3)\rm\quad\quad\phantom{(n+1)\ n\ } n\ \equiv\ \ 0\quad\quad\ $ by substituting $\:(2)\:$ in $\:(1)\:$

$(4)\rm\quad\quad\phantom{(n+1)\ n\ } 0\ \equiv\: -1\quad\quad$ by substituting $\:(3)\:$ in $(2)$

So we conclude $\rm\: 0\ \equiv\ 1\ $ i.e. $\rm\ d\ |\ 1\quad$ QED

Unwinding the linear relations used in the above proof (or, equivalently, using the extended Euclidean algorithm) yields the Bezout relation that I gave in the question that you linked to, viz.

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

Notice how what seems like magic viewed in terms of divisibility relations is reduced to a purely mechanical elimination process in equational form. In higher number theory you'll learn more precisely how linear algebra methods such as Gaussian elimination extend from fields to certain rings, e.g. google Hermite and Smith normal forms.

share|improve this answer
    
Hm, I don't see how n! is also congruent to -1. Could you expand on that? Thanks for the encouragement! I am just an engineer, so this one class will probably all the number theory I will learn, unless I end up inventing error correcting codes at my job. I am enjoying it though! –  Christoph Mar 8 '11 at 3:44
    
Ah wait. $n! + 1 \equiv 0$ means $n! \equiv -1$? I can just do that, just as if the $\equiv$ were an =? That n! is congruent to both 0 and -1 makes no sense in my head though.... –  Christoph Mar 8 '11 at 3:46
    
@Chris: Yes, you can add and multiply congruence just like integer equations. For an introduction see the Wikipedia article on modular arithmetic. –  Bill Dubuque Mar 8 '11 at 3:53

By the Euclidean Algorithm $$\left(n!+1,\ (n+1)!+1\right)=\left(n!+1,\ (n+1)!+1-(n!+1)\right)$$ $$=\left(n!+1,n\cdot n!\right).$$ It is clear the last two must be relatively prime, since if $p|\ (n!\cdot n)$ then $p| n!$ (and there is an extra +1 hanging around).

share|improve this answer

Suppose $m$ is a positive integer dividing both $n! + 1$ and $(n+1)! + 1$. The goal is to show that $m = 1$. Note that $m$ also divides $(n+1)*(n! + 1) - ((n+1)! + 1)$, which is equal to $(n+1)! + (n+1) - (n+1)! - 1 = n$. Since $m$ divides $n$, it also divides $n!$. Since it divides $n! + 1$ as well, it divides $n! + 1 - n!$ or just $1$. Hence $m = 1$ as needed.

share|improve this answer
    
Could you explain how you know that m divides (n+1)∗(n!+1)−(n+1)!+1? –  Christoph Mar 8 '11 at 3:41
    
if $m$ divides $a$ and $b$ then $m$ divides $ka + lb$ for any integers $k$ and $l$. So here $a = n! + 1$ and $b = (n+1)! + 1$, while $k = (n+1)$ and $l = -1$. –  Zarrax Mar 8 '11 at 3:52
    
Ah okay, thanks! –  Christoph Mar 8 '11 at 4:13

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.