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.

The recent post didn't really provide sufficient help. It was too vague, most of it went over my head.

Anyway, I'm trying to find the $\gcd(n!+1,(n+1)!)$.

First I let $d=ab\mid(n!+1)$ and $d=ab\mid(n+1)n!$ where $d=ab$ is the GCD.

From $ab\mid(n+1)n!$ I get $a\mid(n+1)$ and $b|n!$.

Because $b\mid n!$ and $ab\mid(n!+1)$, $b$ must be 1.

Consequently, $a\mid(n!+1)$ and $a\mid(n+1)$.

So narrowing down options for $a$ should get me an answer. At this point I've tried to somehow bring it around and relate it to Wilson's theorem as this problem is from that section of my textbook, but I seem to be missing something. This is part of independent study, though help of any kind is appreciated.

share|improve this question
1  
What's your reasoning for $ab | (n+1)n! \Rightarrow a|(n+1)$ and $b|n!$ ? –  Cocopuffs Jun 18 '12 at 7:38
    
Your logic is sketchy but it can be made to work (you should define $a$ and $b$ much more carefully). You might want to consider separately the case where $n+1$ is prime and $n+1$ is composite. –  Erick Wong Jun 18 '12 at 7:39
2  
Have you tried the Euclidean algorithm? –  Qiaochu Yuan Jun 18 '12 at 7:40
4  
$ab|cd$ does not imply $a|c$ and $b|d$ (even if $a,b$ are prime). Suppose for example $n=4$ and we set $a=2$, $b=5$: then $2\cdot5|(4+1)\cdot 4!$, but we do not have $2|(4+1)$ nor do we have $5|4!$. –  anon Jun 18 '12 at 7:41
    
I concede that my logic in separating the terms of $(n+1)n!$ is flawed. I'm considering alternatives. –  jmedsy Jun 19 '12 at 8:18
add comment

4 Answers

up vote 9 down vote accepted

The previous posts have I think carefully explained why the gcd is $1$ if $n+1$ is composite. It comes down to this: if $q$ is a prime that divides $(n+1)!$, and $n+1$ is composite, then $q \lt n+1$, and therefore $q \le n$. But then $q$ divides $n!$, and therefore $q$ cannot divide $n!+1$.

You have shown that any common divisor of $n!+1$ and $(n+1)!$ must divide $n+1$.

Suppose now that $n+1$ is prime, say $n+1=p$. Then by Wilson's Theorem, $(p-1)!\equiv -1 \pmod p$. This says that $p$ divides $(p-1)!+1$, meaning that $n+1$ divides $n!+1$.

It follows that if $n+1$ is prime, then $n+1$ is a common divisor of $n!+1$ and $(n+1)!$. It is the greatest common divisor, since all common divisors must divide $n+1$, and nothing bigger than $n+1$ can divide $n+1$.

We conclude that $\gcd(n!+1,(n+1)!)=1$ if $n+1$ is composite, and $\gcd(n!+1,(n+1)!)=n+1$ if $n+1$ is prime.

share|improve this answer
add comment

Notice that $$\gcd(n!+1,(n+1)!)=\gcd(n!+1,(n+1)!-(n+1)(n!+1))=\gcd(n!+1,n+1)$$

Case 1. $n+1$ is prime, thus $n+1\mid n!+1$, for Wilson's theorem, so $\gcd(n!+1,n+1)=n+1$.

Case 2. $n+1$ is not prime, so $n+1$ is composite ($n+1>1$). Let $p$ is any prime divisor of $n+1$, so $2\le p<n+1$, thus $p\mid n!$, so $p\nmid n!+1$, thus $\gcd(n!+1,n+1)=1$.

share|improve this answer
add comment

By Euclid $\rm\,(k,k\!+\!1)=1\:\Rightarrow\:(p\!\ k,k\!+\!1) = (p,k\!+\!1)\ [= p\ $ if $\rm\:p\:$ prime, $\rm\:k=(p\!-\!1)!\:$ by Wilson. See here for $\rm\:p = n\!+\!1\:$ composite.

share|improve this answer
add comment

$$ \begin{align} \gcd(n!+1,(n+1)!) &=\gcd(n!+1,n!)\gcd(n!+1,n+1)\\ &=\gcd(n!+1,n+1) \end{align} $$ Wilson's theorem says that $n!+1=0\pmod{n+1}$ iff $n+1$ is prime. Therefore, if $n+1$ is prime, $\gcd(n!+1,n+1)=n+1$.

Suppose $n+1$ is composite. Let $p\,|\,n+1$ where $p<n+1$ is prime. Since $p\le n$, $p\,|\,n!$ Therefore, $p\not|\,n!+1$. This means that $\gcd(n!+1,n+1)=1$.

In conclusion, we get that $$ \gcd(n!+1,(n+1)!)=\left\{\begin{array}{}n+1&\text{if }n+1\text{ is prime}\\1&\text{if }n+1\text{ is not prime}\end{array}\right. $$

share|improve this answer
add comment

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.