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.

How does one show that two general numbers $n! + 1$ and $(n+1)! + 1$ are relatively prime?

I don't mind if someone uses a different example, I want to learn how to prove this class of problems.

My professor seems to really emphasize that you can use the division algorithm, or find the greatest common divisor using the division algorithm rather, in order to assess the nature of relative-prime-ness and I am kind of confused as to how to apply it.

share|improve this question

5 Answers 5

up vote 28 down vote accepted

Suppose that $d$ divides both. Then $d$ divides $(n+1)(n!+1)$ and $(n+1)!+1$, so it divides their difference, which is $n$.

But if $d$ divides $n!+1$ and $n$, then $d$ divides $n!+1$ and $n!$, so $d$ divides $1$.

share|improve this answer
1  
André tu m'aides avec mes preuves mathematique depuis trois ans, merci encore une fois! (English: Andre you have assisted me with mathematical proofs for the last three years, thanks again!) –  Arthur Collé Feb 27 at 0:45
2  
Il n'y a pas de quoi. –  André Nicolas Feb 27 at 0:52
    
"then d divides n! + 1 and n!" –  Arthur Collé Feb 27 at 1:05
2  
Because $n$ divides $n!$. –  André Nicolas Feb 27 at 1:06

I'll use $\big(a,b\big)$ to denote the gcd of $a$ and $b$. The basic idea of division algorithm is that $(a,b) = (a - kb,b)$ for any integer $k$.

\begin{align*} \Big((n+1)! + 1 \; , \; n! + 1\Big) &= \Big([(n+1)! + 1] - (n+1)[n! + 1] \; , \; n! + 1 \Big) \\ &= \Big((n+1)(n!) - (n+1)(n!) + 1 - (n+1) \; , \; n! + 1 \Big) \\ &= \Big(-n , \; n! + 1 \Big) \\ &= \Big(n , \; n! + 1 \Big) \\ &= \Big(n , \; n! + 1 - (n-1)!(n) \Big) \\ &= \Big(n , \; 1 \Big) \\ &= 1 \\ \end{align*}

share|improve this answer

The key identity is $$\gcd (a,b) = \gcd (a-kb ,b).$$

So, the task is to choose the $k$ such that the expression gets simpler.

In this particular case, it is the plus 1 which is blocking the nice multiplicative structure, so you can choose $k=1$ to eliminate it which gives

$$\gcd ((n+1)!+1,n!+1) = \gcd (n\cdot n! ,n!+1).$$

But this is clearly 1 because every factor of $n\cdot n!$ is relatively prime to $n!+1$.

(Note that the other answers choose $k=n+1$ to eliminate the factorial instead of the 1, so you have usually more than one good option to choose $k$.)

share|improve this answer

Hint $\ $ Let $\, k = n!\,$ below

$$(k\!+\!1,(n\!+\!1)k\!+\!1) = (\color{#c00}{k\!+\!1},(n\!+\!1)(\color{#c00}{k\!+\!1})\!-\!n) = (\color{}{k\!+\!1},-n)\,\ \ \left(\,= 1\ \ {\rm if}\ \ n\mid k\,\right)$$

share|improve this answer

Hint: $$(n+1)!+1\ =\ (n+1)\,n!\,+1 = (n+1)\,(n!+1)\ -\ (n+1)\ +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.