8
$\begingroup$

$(n!+1,(n+1)!)$ can be rewritten as $(n!+1,(n+1)*n!)$.

I know that if $n!$ is divisible by a prime $p$ then $p$ doesn't divide n!+1. So when I'm looking at then is $(n!+1 , n+1)$ which I can make $(n!-n,n+1)$ by subtracting $n+1$ from $n!+1$ and since gcd is preserved in linear combinations I still get the same gcd for $(n!-n,n+1)$. I then look at $n!-n = n[(n-1)!-1]$ again if a prime $p$ divides $n$ I'll find that $p$ doesn't divide $n+1$. So I'm looking at $((n-1)!-1,n+1)$. I've looked at the first few n's and it seems that the gcd is either 1 or n+1. But I'm stuck on how to get there from $((n-1)!-1,n+1)$.

Can anybody provide a hint as to how to proceed?

3 Answers 3

11

Hint $\ $ Consider $\rm\:(n+1,n!+1)\:.$ If prime $\rm\:p\ |\ n+1\:$ and $\rm\:p \le n\:$ then $\rm\:p\ |\ n!\:$ so $\rm\:p\nmid n!+1\:.$ So the gcd $ = 1\:$ if $\rm\:n+1\:$ is composite. For $\rm\:n+1\:$ prime use Wilson's theorem.

7

You've done great work!

So yes, you know that the only numbers that could possible divide both sides are $n+1$ or $1$ (which I consider to be the hard part). So we ask ourselves, what is $n! + 1 \mod (n+1)$. If it's zero, solid. If not, relatively prime.

What does Wilson's Theorem say again? (I love it when we get to use Wilson's Theorem for anything, as its applications sort of rarely come up).

2

Let

$gcd(n!+1,(n+1)!)=d$.\ $\therefore d/n!+1, d/(n+1)n!$.\ $\Rightarrow d/n!+1,d/n+1,d/n!$.\ $\Rightarrow d/n!+1-n!$.\ Hence we get $d/1$. It follows that $d=1$.