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.

I need to prove that

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

In class, the teacher advised us to use Bézout's Identity. So I wrote the following

$$ x(n!+1) + y[(n+1)! + 1] = 1 $$

But from there I'm at a loss.

To make the question more generic: I don't understand how Bézout's Identity can help me prove that the $\gcd$ of two numbers is really $n$.

Previous exercises I had to prove were much simpler; for example, I had to prove that $\gcd(2n+1, 3n+1) = 1$. In this case, I just tried to find $x$ and $y$ that make the statement $x(2n+1) + y(3n+1) = 1$ true. And by finding any two integers, I understood that I had provided enough proof. But I didn't do any math to find $x$ and $y$ in that simpler case... or I did, but I don't understand what I did... anyway, I could just "see", right away, that if $x=3$ and $y=-2$, then it would work out.

Can you help me understand how to use Bézout's Identity in proofs of any type? I think I'm not using it correctly.

share|improve this question
1  
If only everyone would post questions with as much context as you do... thank you. –  Git Gud Apr 10 '13 at 6:28
1  
@p and @andre-nicolas, what you did is really helping. I'm almost understanding it. I would keep trying today, but I must sleep. I'm taking notes of both your results to think more about it in the morning, after class, since I'll have access to internet only tomorrow afternoon. Thanks. –  BeetleTheNeato Apr 10 '13 at 6:49
add comment

2 Answers

up vote 2 down vote accepted

I would not use "Bézout" directly. Let $d$ be a divisor of 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$, it divides $1$.

Now if you wish you can work backwards, and find the appropriate multipliers. But we don't need them to prove relative primality.

Remark: In a sense, what we did is much like the procedure you described. You used $x$ and $y$ to get rid of the ugly part. We did the same thing in the first step, getting rid of the factorial stuff.

share|improve this answer
    
Well, I don't even think of the attempted process as Bezout. It is the trivial direction of Bezout, true almost anywhere there is a notion of relatively prime. The hard direction is to show that if $a$ and $b$ are relatively prime, then there exist integers $x$ and $y$ such that $ax+by=1$. –  André Nicolas Apr 10 '13 at 6:40
    
Very true. I actually tried to hint at the misspelling of "Bézout" as "Bezout" but apparently I haven't been clear. –  Lord_Farin Apr 10 '13 at 6:42
    
I'm afraid that if your keyboard does not support diacritics then there is no way around "insert symbol" or even copy-pasting. –  Lord_Farin Apr 10 '13 at 6:46
    
@Lord_Farin: Thanks for the suggestion. I went to Wikipedia and stole Bézout. –  André Nicolas Apr 10 '13 at 6:52
    
Three days and several pages later, I can say I don't understand it. For example, why do you start the proof with a multiple of $(n!+1)$? And, more importantly, I don't understand what seems to be the main argument: "if d divides n!+1 and n, it divides 1." Why? –  BeetleTheNeato Apr 13 '13 at 23:07
show 3 more comments

Hint:

  • $(n+1)\cdot(n!+1)-\left[(n+1)!+1\right]=\color{red}n$
  • $(n!+1)-(n-1)!\cdot \color{red}{n}=1$
share|improve this answer
add comment

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.