0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ "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. $\endgroup$ – Hagen von Eitzen Oct 26 '18 at 11:50
  • $\begingroup$ @HagenvonEitzen Thank you, that is exactly what bothered me. $\endgroup$ – Michael Munta Oct 26 '18 at 11:59
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. :) $\endgroup$ – Michael Munta Oct 26 '18 at 13:48
  • $\begingroup$ How can gcd of anything be 0? It should be at least 1? $\endgroup$ – Michael Munta Oct 26 '18 at 14:40
  • $\begingroup$ @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. $\endgroup$ – Bill Dubuque Oct 26 '18 at 14:53
  • $\begingroup$ What do you mean by $a$ being invertible? What does that mean exactly? $\endgroup$ – Michael Munta Oct 26 '18 at 14:59
  • $\begingroup$ @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). $\endgroup$ – Bill Dubuque Oct 26 '18 at 15:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.