1
$\begingroup$

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$

$\endgroup$
2
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Thanks. I was really doubtful about that. $\endgroup$ – izzorts Oct 17 '16 at 4:45
2
$\begingroup$

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

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

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.