0

This is part of proof in https://www.people.vcu.edu/~rhammack/BookOfProof/Main.pdf#page=165

"... show that $d$ is the unique such natural number. To do this, suppose $d'$ is any nautral number with the property the $d$ has: $m$ is a multiple of $d'$ $\Leftrightarrow$ $m=ax+by $ for some $x, y$ (7.1) ... Because of (7.1), $m = a · 1+ b · 0 = a$ is a multiple of $d'$. Likewise $m = a · 0 + b · 1 = b$ is a multiple of $d'$. Hence $a$ and $b$ are both multiples of $d'$, so $d'$ is a common divisor of $a$ and $b$, and therefore $d'$ ≤ gcd(a,b) = d"

I don't get the part where $d'$ can be a common divisor of $a$ and $b$. Shouldn't it be $m_a = a · 1+ b · 0 = a$ is a multiple of $d_a'$. Likewise $m_b = a · 0 + b · 1 = b$ is a multiple of $d_b'$? I don't understand why $m=m_a=m_b$ and $d'=d_a'=d_b'$.

I feel like the proof is saying $m = a · 1+ b · 0 = a = a · 0 + b · 1 = b$ or $m=a=b$. What's wrong with my understanding? Thanks.

user665125
  • 139

1 Answers1

1

Assume that it is proven that there exists at least one value $d$ such that $m$ is a multiple of $d$ if and only if $m$ can be written as $ax + by$.

Now assume that $d$ is not unique, so that there exists a similar number $e$ that is distinct from $d$.

Because $d$ is a multiple of $d$, this implies that $d$ can be expressed as $ax + by$.

Similarly, since $e$ is a multiple of $e$, this implies that $e$ can be expressed as $ax + by$.

However, by the definitions of $d$ and $e$, this implies that $d$ is a multiple of $e$ and that $e$ is a multiple of $d$. Under the assumption that $d \neq e$, you therefore have a contradiction.

user2661923
  • 35,619
  • 3
  • 17
  • 39
  • Sorry. I got confused. How do we know $d$ is a multiple of $e$? The third and fourth sentences are using different $m$. Then, $d=ax+by$ only implies $d$ is multiple of $d$ and $e=ax+by$ only implies $e$ is multiple of $e$. What's my misunderstanding? – user665125 Feb 16 '22 at 21:50
  • 1
    @user665125 By the definition of $e$, any number that can be written in the form $ax + by$ must be a multiple of $e$. $d$ is a multiple of $d$. Therefore, $d$ can be written in the form $ax + by$. Therefore, $d$ is a multiple of $e$. – user2661923 Feb 16 '22 at 21:52
  • Oh okay. THANK YOU!!!. I was so stuck. I didn't fully understand the definition. – user665125 Feb 16 '22 at 21:58