I've done proofs in discrete mathematics, but I'm still at the stage where proofs with more than a few steps make me uncomfortable.
From Apostol's Mathematical Analysis [2nd Ed.] on page 5, we have
Theorem 1.6. Every pair of integers $a$ and $b$ has a common divisor $d$ of the form $$ d = ax + by $$ where $x$ and $y$ are integers. Moreover, every common divisor of $a$ and $b$ divides this $d$.
The proof (with my questions throughout) goes as follows:
Proof. First assume that $a \geq 0, b \geq 0$ and use induction on $n = a + b$. If $n = 0$ then $a = b = 0$, and we can take $d = 0$ with $x = y = 0$. Assume, then, that the theorem has been proved for $0, 1, 2, ..., n - 1$.
I am a little confused about taking $n$ to be $a + b$, since it's not obvious that all pairs $\{a, b\}$ would be covered by induction for all combinations of $a, b \in \mathbb{Z}$.
By symmetry, we can assume $a \geq b$. If $b = 0$ take $d = a, x = 1, y = 0$.
OK.
If $b \geq 1$ we can apply the induction hypothesis to $a - b$ and $b$, since their sum is $a = n - b \leq n - 1$. Hence there is a common divisor $d$ of $a - b$ and $b$ of the form $d = (a - b)x + by$.
I'm going to let $a' = a - b$, let $b' = b$ and let $d' = a'x + b'y$. (I wish Apostol did something like this to make his proofs clearer.)
I don't understand this logical step. Why does the fact that $a' + b' \leq n - 1$ imply that $d'$ exists and is a common divisor of $a'$ and $b'$? This seems like a huge leap.
This $d$ also divides $(a - b) + b = a$, so $d$ is a common divisor of $a$ and $b$ and we have $d = ax + (y-x)b$, a linear combination of $a$ and $b$.
At this point I am clueless. Why does $d$ divide $a$ and why does this imply it also divides $b$? And where does Apostol get $y-x$ from??
To complete the proof we need to show that every common divisor divides $d$. Since a common divisor divides $a$ and $b$, it also divides the linear combination $ax + (y-x)b = d$. This completes the proof if $a \geq 0$ and $b \geq 0$. If one or both of $a$ and $b$ is negative, apply the result just proved to $|a|$ and $|b|$.
Why not just do the entire proof with absolute values from the beginning?
Soft question: is it normal for authors to be very terse and not explain or give motivation for any steps? How do you go about trying to understand proofs that require a higher level of intuition than you currently have?
from Hot Weekly Questions - Mathematics Stack Exchange
Post a Comment