5
$\begingroup$

Does anyone have a intuition or argument or sketch proof of why $\gcd(a,b) = \gcd(b, a \pmod b)$?

I do have a proof and I understand it, so an intuition would be more helpful.


The proof that I already have:

I show $\gcd(a,b) \mid \gcd(b, a \pmod b)$ and $\gcd(b, a \pmod b) \mid \gcd(a, b)$ which implies $\gcd(a,b) = \gcd(b, a \pmod b)$ and stuff is non-negative.

WLOG $a \geq b$

$\gcd(a,b) \mid a$

$\gcd(a,b) \mid b$

so it divides any linear combination of a and b

Since $a \pmod b = a - qb$ then:

$\gcd(b, a - qb) = bx + (a-qb)y$

$\gcd(b, a - qb) = bx + ay - qby $

$\gcd(b, a \pmod b) = b(x-qy) + ay$

which is a LC of $a$ and $b$.

So $\gcd(a,b) \mid \gcd(b, a \pmod b)$.

Other direction is nearly identical.

$\endgroup$
  • 4
    $\begingroup$ You must mean mod $b$ not $p$. $\endgroup$ – Bill Dubuque Jan 19 '14 at 22:01
  • $\begingroup$ let me correct that, no idea why there is a p there. typo. Yes I meant b, sorry, I usually do mod p prime so I just wrote p and then I copied pasted every time I needed that expression. Its corrected now. $\endgroup$ – Pinocchio Jan 19 '14 at 22:03
  • $\begingroup$ It's not clear how you have: $gcd(b, a \pmod p) = b(x-qy) + ay$. Where did that come from? $\endgroup$ – Thomas Andrews Jan 19 '14 at 22:08
  • $\begingroup$ @ThomasAndrews I updated my question. Does it make sense now? $\endgroup$ – Pinocchio Jan 19 '14 at 22:11
  • $\begingroup$ The current version of your proof is fine, yes. You don't really need $a\geq b$, and you still have a $p$ in there. $\endgroup$ – Thomas Andrews Jan 19 '14 at 23:01
6
$\begingroup$

Let $\, a\ {\rm mod}\ b = a-kb.\, $ If $\, d\mid b\ $ then $\ d\mid \color{#0a0}{a-kb}\iff d\mid \color{#c00}a.\ $ Thus $\ \color{#0a0}{a-kb},b\ $ and $\ \color{#c00}a,b\ $ have the same set $S$ of common divisors $\,d,\,$ so they have the same greatest common divisor $\,(= \max S).$

$\endgroup$
  • $\begingroup$ Hi Bill. Came back after a year to this post I think I don't remember how I filled in the gaps from your hint. How did you conclude that $a-kb, b$ and $a,b$ have the same set of common divisors? Once thats clear it should be super obvious. $\endgroup$ – Pinocchio Oct 7 '15 at 17:14
  • $\begingroup$ @Pin It follows from my 2nd sentence: if $\,d\mid b\,$ then ... Do you see how to prove that $\iff$? $\quad$ $\endgroup$ – Bill Dubuque Oct 7 '15 at 23:54
  • $\begingroup$ @Pin It's even clearer mod $\,d,\,$ viz. $\,a,b\equiv 0\iff a-kb,b\equiv 0,\,$ or, equivalently, if $\,b\equiv 0\,$ then $\,a\equiv 0\iff a-kb\equiv 0.$ $\quad$ $\endgroup$ – Bill Dubuque Oct 8 '15 at 1:06
6
$\begingroup$

Hint: Show that more generally $\gcd(a,b)=\gcd(b,a-bk)$ for any integer $k$.

Then note that $a\pmod b = a-bk$ for some $k$.

$\endgroup$
  • 1
    $\begingroup$ @Pinocchio But that's precisely what I proved, since the proof is valid for all $k\in \Bbb N$. $\endgroup$ – Bill Dubuque Jan 19 '14 at 22:23
  • 4
    $\begingroup$ @BillDubuque There is no point in engaging in such discussion. $\endgroup$ – Pedro Tamaroff Jan 19 '14 at 22:24
  • 2
    $\begingroup$ @Pedro It is interesting pedagogically, since if some view things differently then it helps to understand why. Sometimes this is because an answer wasn't clear, and sometimes it's because a reader had some misunderstanding, or various other possibilities. One cannot know which without discussing it. $\endgroup$ – Bill Dubuque Jan 19 '14 at 22:25
  • 1
    $\begingroup$ @Pinocchio That's why it is a "hint". I hoped that the reader might make that small leap, and thereby gain a better learning experience. My experience is that students remember proofs better the more they discover the key ideas on their own. $\endgroup$ – Bill Dubuque Jan 19 '14 at 22:31
  • 1
    $\begingroup$ @BillDubuque Well, I'm a pretty smart guy, and a couple people here are saying my answer made things clearer. I realize, it is at heart just a tiny tweak to your hint, but it is a tiny tweak that makes things much clearer. But keep litigating, it really makes you seem nice. $\endgroup$ – Thomas Andrews Jan 19 '14 at 22:37
5
$\begingroup$

The crux of all proofs is that $gcd(b,a) = gcd(b,a-b)$.

This should be easy to see intuitively; if you add or subtract two multiples of $g$ you get a multiple of $g$, so all factors are retained both ways.

Once you have that, you know that you can subtract one number from the other as many times as you like, without changing the gcd.

If you continue subtracting $b$ from the second number, you will eventually arrive at a number between 0 and $b-1$; specifically $a\bmod b$.

$\endgroup$
  • $\begingroup$ I am not sure if I understood your most important sentence (second one). Do you mind rephrasing it? When you say you add two multiples of g, you add them to what or subtract them from what? It wasn't entirely clear what it mean. (Thanks though, I think this has the potential to be the best answer!) $\endgroup$ – Pinocchio Jan 19 '14 at 22:22
  • 2
    $\begingroup$ If $g | gcd(b,a)$, then $g | a$ and $g | b$, so $g | a - b$, so $g | gcd(b,a-b)$. The same is true in reverse, so any factor of the LHS is a factor of the RHS, and vice versa; so they are equal. $\endgroup$ – user11977 Jan 19 '14 at 22:24
2
$\begingroup$

For me it all really comes down to this equation $$ a=qb+r $$ For if $d$ divides $b$ and any of the two $a$ or $r$ it has to divide the last of $a$ and $r$ too in order for this equation to hold.

$\endgroup$
  • 1
    $\begingroup$ It's important to stress that one needs the reverse implication too, i.e. not only $\,d\mid a,b \color{#0a0}\Rightarrow d\mid r\,$ but also $\,d\mid a\color{#c00}\Leftarrow d\mid r,b,\,$ hence $\,d\mid a,b\color{#c00}\Leftarrow\!\!\color{#0a0}\Rightarrow d\mid r,b;\, $ e.g. $\ r = ja+kb\ $ sastifies $(\color{#0a0}\Rightarrow)$ but need not satisfy $(\color{#c00}\Leftarrow)$. Indeed generally $\,\gcd(a,b)\ne \gcd(ja+kb,b) = \gcd(ja,b),\,$ e.g. let $\,b = ja\,$ for $\,j>1.\ $ $\endgroup$ – Bill Dubuque Jan 20 '14 at 0:23
  • $\begingroup$ @BillDubuque: It has been fixed. Thanks again! $\endgroup$ – String Jan 20 '14 at 14:38
1
$\begingroup$

Suppose each of $a$ and $b$ is an integer number of miles. Then so is $a\bmod b$.

If a mile is a "common measure" (as Euclid's translators say) of both distances, then a mile is a common measure of what's left when $b$ has been taken from $a$ as many times as possible.

$\endgroup$

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.