11
$\begingroup$

For any $n \in \mathbb{N}$, find $\gcd(n!+1,(n+1)!+1)$. First come up with a conjecture, then prove it.

By testing some values, it seems like $\gcd(n!+1,(n+1)!+1) = 1$

I can simplify what's given to me to $\gcd(nn!, n!+1)=1$ but I can't find out how to get it into the form I want it. Can anybody look at what I'm doing and give me any guidance?

$\gcd(n!+1,(n+1)!+1) = 1 \implies \gcd(n!+1,(n+1)n!+1) = 1 \implies \gcd(n!+1,nn!+n!+1) = 1 \implies \gcd(nn!, n!+1) = 1$

  • 0
    .....and just in case anyone wonders: I just posted 5\gcd(a,b) and 5\mathrm{gcd}(a,b) within a "displayed" $\TeX$ setting in the "answer" box below. Try it and you'll see that they don't both look the same! (One of them has proper spacing between "$5$" and "$\gcd$".)2012-04-11

5 Answers 5

-1

I dont know i am right or wrong but i can do this example in following way,\ Let $\gcd(n\cdot n!,n!+1)=d$ $\therefore d\mid n\cdot n!\ ,\ d\mid n!+1$ $\Rightarrow d\mid n,\ d\mid n!,\ d\mid n!+1$ $ \Rightarrow d\mid n!+1-n!$ Thus $d\mid 1\ \Rightarrow d=1.$

  • 1
    \cdot is better than \circ for the multiplication dot.2012-04-11
11

You don’t need to use induction; you just need to prove the statement in the title. Suppose that $p$ is a prime factor of $nn!$; can $p$ divide $n!+1$?

  • 10
    @Bill: I didn’t say that they were. I offered what I consider an easy approach to the problem. In general I write primarily for the questioner, not for possible future readers.2012-04-11
9

Here is a proof that does not use induction but rather the key property of gcd: $(a,b) = (a-b,b) = (a-kb,b)$ for all $k$.

Take $a=nn!$, $b=n!+1$, $k=n$ and conclude that $(nn!, n!+1)=(nn!-n(n!+1),n!+1)=(-n,n!+1)=1$ since any divisor of $n$ is a divisor of $n!$.

  • 0
    @user28554: You are welcome!2012-04-11
1

Hint $\ $ Put $\rm\,k = n!\ $ in: $\rm\,\ \color{#c00}{n\mid k}\,\Rightarrow\,(1+k,nk)= 1\ $ by $\rm\, (1\!-\!k)\:(1\!+\!k) + (\color{#c00}{k/n})\: nk = 1.\ \ $ QED

Generally, $ $ the above Bezout equation implies coprimality of $\rm\, 1+k\,\ $ and $\rm\,\ nk\,$ in every ring.


Alternatively, with $\rm\,m = 1+k,\,$ we can employ Euclid's Lemma $\rm(EL)$ as follows:

$\rm\,n\mid k,\,(m,k) =1\,\Rightarrow (m,n) = 1\,\Rightarrow\,(m,nk)=1\ \ by\ \ EL$ i.e. $\rm\, mod\ m\!:\ x\,$ is a unit (invertible) iff $\rm\,(x,m) = 1.$ Units are closed under products and divisors, i.e. they form a saturated monoid, so since $\rm\,k\,$ is a unit so is its divisor $\rm\,n\,$ and the product $\rm\,nk.$

1

Note that $ (n-1)!\cdot \underline{n n!} - (n!-1)\underline{(n!+1)} = 1; $ this Bézout's identity shows that the two underlined quantities must be relatively prime (anything that divides them both must divide the right-hand side). The related identity $ (n-1)! \underline{((n+1)!+1)} - (n!+(n-1)!-1)\underline{(n!+1)} = 1 $ similarly proves that the greatest common divisor of these two underlined terms equals 1.

Of course, discovering these identities in the first place is best done by using the Euclidean algorithm, as in lhf's answer.

  • 0
    My concern is not priority but, rather, pedagogy. I explicitly *abstracted* $n!$ to any integer $k$ divisible by $n$ in order to make clearer the innate governing multiplicative structure. To succeed in elementary number theory it is *essential* to learn how to recognize such structure. If students are encouraged to follow shortcuts circumventing such pedagogical routes then they may completely miss the key ideas, and never see the forest for the trees.2012-04-12