11
$\begingroup$

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

I did find a somewhat related post that uses a different method: How to show that $\gcd(n! + 1, (n + 1)! + 1) \mid 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!

5 Answers 5

7

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.

  • 0
    @Chris: Yes, you can add and multiply congruence just like integer equations. For an introduction see the Wikipedia article on [modular arithmetic.](http://en.wikipedia.org/wiki/Modular_arithmetic)2011-03-08
7

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

4

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.

  • 1
    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$.2011-03-08
1

This is a direct application to the division algorithm which says:

for any two integers a,b, a>b the following holds: $a = qb + r$

If we show that $0, we are done.

Replace $a$ by $(n+1)!+1$, $q$ by $n$, $b$ by $(n!+1)$ and $r$ by $n!-n+1$ which is greater than $0$ and less than $b$, as required.

More Clarificatoin:

The left hand side is:$(n+1)!+1$ while the right hand side is: $n(n!+1)+(n!-n+1) \Longrightarrow nn!+n+(n!-n+1) \Longrightarrow n!(n+1)+1 \Longrightarrow (n+1)!+1$

0

This is just an alternative to the approach in Eric Naslund's answer.

From the rule $(a,b)=(a,b-ka)$ for any $k$ along with $(a,b)=(b,a)$ and $(a,b)=(|a|,|b|)$, we have

$\begin{align} (n!+1,(n+1)!+1) &=(n!+1,(n+1)!+1-(n+1)(n!+1))\\ &=(n!+1,-n)\\ &=(n,n!+1)\\ &=(n,n!+1-(n-1)!n)\\ &=(n,1)\\ &=1 \end{align}$