# Proof of $\gcd(n!+1, (n+1)!+1)=1$?

I guess the canonical proof to this problem is attained using the Euclidean Algorithm (I've seen some posts like this already). I came with this proof, based on gcd definition and some divisibility properties. I'd like to know if it seems correct to you.

Proof:

Let $d$ be a common divisor of both terms. Then $n! +1$ = $d$.$s$ and $(n+1)! +1 = d.t$, for $s, t$ in $\Bbb Z/{0}$. Therefore $(n +1)n! + 1 = n.n! + n! + 1 = n.n! + d.s = d.t$, and it follows that $d|n.n!$. Now, since $n=d(t-s)/n!$, $d|n$. Then $d$ must divide 1 ($n! + 1 = d.s$), and $|d|$ = 1. Being $d'$ another common divisor, it is clear that $d'$ must divide 1 also, and therefore it does divide $d$, so we have $d = gcd(n! + 1, (n+1)! +1) = 1$

## 3 Answers

There is one mistake in the proof: $n=d(t-s)/n!$ does not imply that $d|n$, because $(t-s)/n!$ may not be an integer. However, you can prove $d|n$ in this way:

$d|n!+1$ implies $d|(n+1)(n!+1)= (n+1)!+n+1$. This and $d|(n+1)!+1$ imply $d|n$. Like you said in the question this implies $d|1$, because $d|n$ implies $d|n!$ and by hypothesis $d|n!+1$.

Once we get $d|1$ we are done, because these means there isn't any prime number dividing $n!+1$ and $(n+1)!+1$, therefore the greatest common divisor is $1$

• Thanks. I was really doubtful about that. – izzorts Oct 17 '16 at 4:45

You can simplify this a lot by letting $a=n!$. From there, you have $\gcd(a+1,(n+1)*a+1)$. From there, you could just find $(n+1)*a+1\equiv1\mod a+1$.

• Indeed. I didn't made it clear, but I was willing to prove it without using the algorithm. – izzorts Oct 17 '16 at 3:19
• As long as you can prove that $a*b+1$ is not a multiple of $a$ (assuming $a\neq1$), you should be fine. – AlgorithmsX Oct 17 '16 at 4:16
• Did you potentially mean: you have $\gcd(a+1,(n+1)*a+1)$? – gowrath Oct 17 '16 at 8:54
• Sorry about that. Yes I did. – AlgorithmsX Oct 17 '16 at 10:52

Note that the result is right iff $n\neq 0$.

We have for all $n\in \mathbb{N^*}$, $(n+1)!+1\ge n!+1$.

Now we use euclidean algorithm :

$(n+1)!+1=(n+1)(n!+1)-n$ with $0<\vert- n\vert<n!+1$

Then $n!+1=(n-1)!\vert -n\vert+1$ with $0<1<\vert-n\vert$.

Then $\vert-n\vert = \vert-n\vert \times 1 +0.$

So we take the last remainder $\neq 0$. And it's $1$. So $\gcd(n!+1,(n+1)!+1)=1$