# Using Bézout's Identity to prove that given $\gcd$ of two numbers is really true

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.

• If only everyone would post questions with as much context as you do... thank you. – Git Gud Apr 10 '13 at 6:28
• @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

## 2 Answers

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.

• 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

Hint:

• $(n+1)\cdot(n!+1)-\left[(n+1)!+1\right]=\color{red}n$
• $(n!+1)-(n-1)!\cdot \color{red}{n}=1$