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.

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$

share|improve this question
    
I changed numerous instances of \mathrm{gcd} in this question to \gcd. It's a standard operator name. –  Michael Hardy Apr 11 '12 at 2:42
    
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! –  highphi Apr 11 '12 at 11:34
    
.....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$".) –  Michael Hardy Apr 11 '12 at 21:00

5 Answers 5

up vote 8 down vote accepted

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

share|improve this answer
4  
Or apply the key property again: $(-n, n!+1) = (((n-1)!\times-n) + n! +1 , n! +1) = (1, n!+1) = 1$ –  Aryabhata Apr 11 '12 at 1:43
    
@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? –  highphi Apr 11 '12 at 16:37
    
@user28554: $(a,b) = (ka+b, a)$. The last term should be $-n$, instead of $n! + 1$. We chose $k = (n-1)!$. –  Aryabhata Apr 11 '12 at 16:41
    
@Aryabhata Ahh, I see now. Thanks! –  highphi Apr 11 '12 at 16:48
    
@user28554: You are welcome! –  Aryabhata Apr 11 '12 at 16:49

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

share|improve this answer
    
Primes aren't needed: if $\rm\:n\:|\:k\:$ then $\rm\:nk,\ k+1\:$ are coprime in any ring - see my answer. –  Bill Dubuque Apr 11 '12 at 3:22
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. –  Brian M. Scott Apr 11 '12 at 3:27

Hint $\ $ Put $\rm\:k = n!\ $ in: $\rm\ n\:|\:k\:\Rightarrow\:(1+k,nk)= 1\ $ by $\rm\: (1-k)\:(1+k) + (k/n)\: nk = 1.\ \ $ QED

More generally, note that the above Bezout equation implies $\rm\: 1+k\:$ and $\rm\:nk\:$ are coprime in every ring. Alternatively, with $\rm\:m = k+1,\:$ one can employ Euclid's Lemma (EL) as follows:

$$\rm\:(m,k) =1,\ n\:|\:k\:\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.$ But units are closed under products, divisors, i.e. they form a saturated monoid. So, since $\rm\:k\:$ is a unit so is its divisor $\rm\:n\:$ and so is the product $\rm\:nk.$

share|improve this answer

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.

share|improve this answer
    
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. –  Bill Dubuque Apr 11 '12 at 20:06
    
Well then, I won't claim priority. But some might find that my solution is more accessible to the OP than yours. –  Greg Martin Apr 12 '12 at 6:51
    
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. –  Bill Dubuque Apr 12 '12 at 14:15

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

share|improve this answer
    
Why does $d \mid n$ ? Perhaps you mean a prime $d$. –  lhf Apr 11 '12 at 1:47
    
$8 | 4 \times 4!$, but $8$ does not divide $4$. –  Aryabhata Apr 11 '12 at 1:47
    
Just for the record, if you want to write the "dot" for multiplication, you can use >\circ –  M Turgeon Apr 11 '12 at 2:45
1  
\cdot is better than \circ for the multiplication dot. –  Greg Martin Apr 11 '12 at 6:33

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.