# Euclid Lemma proof reasoning

This question is more concerned with understanding the reasoning behind mathematical proving rather than explaining this specific proof. I understand why this proof works.

This is the proof of Euclid Lemma from Wikipedia:

This states that if $$x$$ and $$y$$ are relatively prime integers (i.e. they share no common divisors other than 1) there exist integers $$r$$ and $$s$$ such that

$$rx+sy=1$$. Let $$a$$ and $$n$$ be relatively prime, and assume that $$n|ab$$. By Bézout's identity, there are $$r$$ and $$s$$ making

$$rn+sa=1$$. Multiply both sides by $$b$$:

$$rnb+sab=b$$. The first term on the left is divisible by $$n$$, and the second term is divisible by $$ab$$, which by hypothesis is divisible by $$n$$. Therefore their sum, $$b$$, is also divisible by $$n$$.

I am mostly concerned with this statement:

Multiply both sides by $$b$$:

My question is why this multiplication by $$b$$ happens. Is it because the person proving this observed that multiplying the equation by $$b$$ he would get a sum of two multiples of $$n$$? Or is there a mathematical rule by which we know that the next step is multiplying by $$b$$?

I am aware that this question might seem trivial to people here, but I just want to make sure.

• "Because we can" - You are free to multiply by $a^3$ or by $17$ instead. But that would not help you carry on. - How could one get the idea to multiply by $b$? Well, we are given a fact about $ab$, namely that it is a multiple of $n$. So any step that makes $ab$ appear and allows us to make use of that property might be helpful. – Hagen von Eitzen Oct 26 '18 at 11:50
• @HagenvonEitzen Thank you, that is exactly what bothered me. – Michael Munta Oct 26 '18 at 11:59

## 1 Answer

My question is why this multiplication by b happens. Is it because the person proving this observed that multiplying the equation by b he would get a sum of two multiples of n? Or is there a mathematical rule by which we know that the next step is multiplying by b?

Yes, the "rule" is that $$\color{#c00}{\rm invertible}$$ elements are always cancellable (by multiplying by their inverse), and integers coprime to $$\,n\,$$ are invertible$$\bmod n\,$$ (by Bezout).  Explicitly we have:

$$\qquad\qquad\ \ \ \ n\mid ax\,\Rightarrow\, n\mid x\ \$$ if $$\,\gcd(a,n) = 1,\,$$ interpreted mod $$n$$ becomes

$$\quad \iff\ \ \ ax\equiv 0\,\Rightarrow\, x\equiv 0\$$ if $$\,\gcd(a,n) = 1.\$$ But the coefficient $$\,a\,$$ is invertible by Bezout:

$$\qquad\ \ \qquad \color{#c00}{sa\equiv 1}\,\,\$$ by $$\ sa = 1 - rn\$$ for some $$\,s,r,\,$$ by Bezout identity for $$\,\gcd(a,n) = 1$$

$$\qquad\ \Rightarrow\, \color{#c00}{sa}x \equiv s0\$$ by multiplying 2nd last equation by $$\,s,\,$$ valid by the Congruence Product Rule

$$\qquad\ \Rightarrow\ \quad x\equiv 0\$$ by $$\ \color{#c00}{sa\equiv 1}$$

Remark $$\$$ Thus reformulating the divisibility relation as arithmetical operations mod $$\,n\,$$ clarifies the arithmetical essence of the matter. In the same way many divisibility properties are greatly clarified and simplified when reformulated arithmetically in congruence form.

• This is maybe too much for me to grasp. I am a beginner at this with very bad mathematical background. Also my question was probably very stupid to alot of people here. How would I go about reaching a level at math where all of this would be trivial to me at first sight? Should one simply have a knack for this? Right now it would take me multiple days just to understand what you wrote there. :) – Michael Munta Oct 26 '18 at 13:48
• How can gcd of anything be 0? It should be at least 1? – Michael Munta Oct 26 '18 at 14:40
• @Michael That's a typo, Any textbook on elementary number theory will explain congruences. Once you learn them then you can understand that the solution is trivial, just as it is for real numbers, viz. $\, ax = 0\,\Rightarrow\, x = 0\$ if $\,a\neq 0\,$ (i.e. if $a$ is invertible), which follows by multiplying through by $\,a^{-1}.\$ That's exactly what we do above when we multiply by $\,s\equiv a^{-1}\,$ in the ring of $\,\Bbb Z_n =$ integers $\!\bmod n\$ vs real numbers. – Bill Dubuque Oct 26 '18 at 14:53
• What do you mean by $a$ being invertible? What does that mean exactly? – Michael Munta Oct 26 '18 at 14:59
• @Michael Just as for real numbers, in the ring of integers $\bmod n\,$ if $\,ax\equiv 1\,$ has a solution $\,x \equiv s\,$ then we say $\,a\,$ is invertible with inverse $\,s,\,$ i.e. $\ s\equiv a^{-1}\,$. It's easy to show that this is well-defined, and inverses are unique (when they exist). – Bill Dubuque Oct 26 '18 at 15:07