2
$\begingroup$

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.

  • 1
    What's your reasoning for $ab | (n+1)n! \Rightarrow a|(n+1)$ and $b|n!$ ?2012-06-18
  • 0
    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.2012-06-18
  • 2
    Have you tried the Euclidean algorithm?2012-06-18
  • 5
    $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!$.2012-06-18
  • 0
    I concede that my logic in separating the terms of $(n+1)n!$ is flawed. I'm considering alternatives.2012-06-19

4 Answers 4

10

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.

7

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, thus $p\mid n!$, so $p\nmid n!+1$, thus $\gcd(n!+1,n+1)=1$.

2

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.

1

$$ \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 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. $$