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
    I changed numerous instances of \mathrm{gcd} in this question to \gcd. It's a standard operator name.2012-04-11
  • 0
    Thanks for modifying my question to use \gcd and making me realize that command exists. That will help me in the future! Also, thanks to everybody who answered; you all have really helped me!2012-04-11
  • 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.$

  • 0
    Why does $d \mid n$ ? Perhaps you mean a *prime* $d$.2012-04-11
  • 0
    $8 | 4 \times 4!$, but $8$ does not divide $4$.2012-04-11
  • 0
    Just for the record, if you want to write the "dot" for multiplication, you can use >\circ2012-04-11
  • 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$?

  • 0
    Primes aren't needed: if $\rm\:n\:|\:k\:$ then $\rm\:nk,\ k+1\:$ are coprime in *any* ring - see my answer.2012-04-11
  • 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!$.

  • 4
    Or apply the key property again: $(-n, n!+1) = (((n-1)!\times-n) + n! +1 , n! +1) = (1, n!+1) = 1$2012-04-11
  • 0
    @Aryabhata This is probably a really simple question, but how did you get from $(-n, n!+1)$ to $(((n-1)!\cdot-n)+n!+1, n!+1)$ from this "key property"? I see how you used it to add $n!+1$ to the first term, but where did the $(n-1)!$ multiplier come from?2012-04-11
  • 0
    @user28554: $(a,b) = (ka+b, a)$. The last term should be $-n$, instead of $n! + 1$. We chose $k = (n-1)!$.2012-04-11
  • 0
    @Aryabhata Ahh, I see now. Thanks!2012-04-11
  • 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
    This is *precisely* what I wrote 5 hours prior, except it *explicitly* replaces $\rm\:k\:$ by $\rm\: n!\:$ in my Bezout equation. Doing so decreases the generality of the proof, and obscures the key (unit group) structure.2012-04-11
  • 0
    Well then, I won't claim priority. But some might find that my solution is more accessible to the OP than yours.2012-04-12
  • 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