2
$\begingroup$

Origin - Elementary Number Theory, Jones, p $5$, Lemma $1.5$

Are there any illustrations? I tried Wikipedia's article and the first picture to the right, but I think this delineates Euclid's Algorithm? I'm not querying about proofs.

$\endgroup$
1
  • $\begingroup$ What's unintuitive about the usual argument? Namely, from the given equation, each common divisor of $b$ and $r$ is a divisor of $a$; and from $r = a - q b$, each common divisor of $a$ and $b$ is a divisor of $r$? $\endgroup$
    – murray
    Jun 30 '16 at 0:49
6
$\begingroup$

This is how I visualized it:

enter image description here

where $(x, y)$ denotes $\text{gcd}(x, y)$.

Explanation:

Arithmetic of blocks:

An integer $x$ is represented by a rectangular block of unit width and height $x$. Arithmetic operations between integers can then be visualized as manipulation of their blocks.

  • $x + y$: Put a block of height $y$ on top of a block of height $x$ to produce a new block of height $x + y$.
  • $x - y$: Remove a block of height $y$ from a block of height $x$ to produce a new block of height $x - y$.
  • $x \cdot y$: Put $y$ blocks of height $x$ on top of each other to produce a new block of height $x \cdot y$.

Main idea in the diagram:

Use blocks of height $(x, y)$ to argue about divisibility.

Representation:

By definition, $x = (x, y) \cdot k_1 \text{ and } y = (x, y) \cdot k_2 \text{ where } k_1, k_2$ are integers. So, $x$ and $y$ can be drawn as a stack of some integral number of blocks each of height $(x, y)$.

Part 1:

  • Put $x = a, y = b$ to get the first three towers. I chose $k_1 =11$ and $k_2 = 3$ just as an example (to keep my drawing task manageable :)
  • The fourth tower represents $q \cdot b + r$.
  • $a = q \cdot b + r$ tells us that the third and fourth towers are identical. So, we get by visual inspection that $r = a - q \cdot b$ is the fifth tower.
  • Thus, $r$ is shown to be made up of the "building block" $(a, b)$. That is, $r = (a, b) \cdot k_3$ for some integer $k_3$. I chose $k_3 = 2$ just as an example.
  • We observe that $(a, b)$ divides both $r$ and $b$, and so it must divide $(r, b)$.

Part 2:

  • Put $x = r, y = b$ to get the first three towers. I could have chosen different $k_i$'s than in Part 1, but since they eventually turn out to be the same, I didn't do it.
  • The fourth tower represents $q \cdot b + r$.
  • The fifth tower represents $a$.
  • $a = q \cdot b + r$ tells us that the fourth and fifth towers are identical. So, by visual inspection we get that $a$ is the sixth tower, composed of the "building block" $(r, b)$. That is, $a = (r, b) \cdot k_4$ for some integer $k_4$. I chose $k_4 = 11$ to match with Part 1.
  • We observe that $(r, b)$ divides both $a$ and $b$, and so it must divide $(a, b)$

Implication:

I leave it for the reader to conclude that $x | y \text{ and } y | x \implies x = y$. That is, $(a, b) = (r, b) \blacksquare$

Note:

I chose positive integers in the diagram, but one could imagine negative integers as blocks below the horizontal line, representing negative height. But this would clutter the illustration.

$\endgroup$
6
  • $\begingroup$ Thank you. upvote. elysian illustration! did you draw it? please let me stew over it. if i forget to get back to you - i probably won't - please inform me. $\endgroup$ Apr 7 '14 at 13:31
  • 2
    $\begingroup$ Thanks a lot for the very kind comment :) Yes, I drew it. $\endgroup$
    – Anant
    Apr 7 '14 at 16:10
  • 1
    $\begingroup$ I added some explanation now. I used GeoGebra for the drawing. $\endgroup$
    – Anant
    Apr 8 '14 at 10:09
  • $\begingroup$ thanks again. last question for now, in part 2, you put $x = r$. in part 1, you picked $k_1 = 11$, thece shouldn't $r = 11\gcd(r,b)$? How's it $2\gcd(r,b)$? $\endgroup$ May 6 '14 at 13:28
  • $\begingroup$ The example used $a=(a,b)\cdot11$ and $b = (a,b)\cdot 3$. The equation $a = qb + r$ then fixes $r$ to equal $(a,b)\cdot 2 = (r, b) \cdot 2$, so when I use $x=r$, I must set it to $(r,b)\cdot 2$. Feel free to ping me on chat if you have more questions. $\endgroup$
    – Anant
    May 6 '14 at 14:32

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.