19
$\begingroup$

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.

$\endgroup$
31
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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!) $\endgroup$ – Arthur Collé Feb 27 '14 at 0:45
  • 2
    $\begingroup$ Il n'y a pas de quoi. $\endgroup$ – André Nicolas Feb 27 '14 at 0:52
  • $\begingroup$ "then d divides n! + 1 and n!" $\endgroup$ – Arthur Collé Feb 27 '14 at 1:05
  • 2
    $\begingroup$ Because $n$ divides $n!$. $\endgroup$ – André Nicolas Feb 27 '14 at 1:06
16
$\begingroup$

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*}

$\endgroup$
6
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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