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.

$(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?

share|improve this question

3 Answers 3

up vote 10 down vote accepted

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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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.