/sci/ - Science & Math

>>11354969
>gcd(a,b) = gcd(b, a mod b)
I'll give an informal proof.
We have that [math]d|a[/math] and [math]d|b[/math]. Because of this, we know that [math]d|a-b[/math]. To prove it, we just use [math]a=dr_a[/math] and [math]b=dr_b[/math] for some [math]r_a, ~ r_b[/math], and then we have [math]a-b = d(r_a - r_b)[/math].
So for whatever [math]a[/math] we start with, we can just keep subtracting [math]b[/math] from it and that won't change [math]a[/math] and [math]b[/math]'s common divisors.
So we could, for example, keep subtracting [math]b[/math] until [math]a[/math] is as small as possible, which gives us gcd(a,b) = gcd(b, a mod b).
>>11355182
See https://i.imgur.com/vPAp2YD.png
Also, see the TeX button on the posting box.