Here is a function (in Python) which (hopefully) returns the gcd of two positive integers a and b:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 

Assuming \[a\] and \[b\] are distinct positive integers, on each iteration of the loop starting on line 5 \(arg1 +arg2\) gets smaller.
The same goes when \[a\] and \[b\] are of opposite parity.
Suppose \[a\] and \[b\] are distinct positive integers not both even. If \[d\] is a common divisor of \[a\] and \[b\], then \[d\] must also be odd.
If both \[a\] and \[b\] are odd, then \[a +b\] is even. Let \[r\] be the largest power of 2 dividing \[a +b\]. Since \[2^{r}\] and \[d\] are relative prime, then \[d\] is a divisor of \[\frac{a+b}{2^{r}}\]. Therefore \[d\] is also a divisor of \[\frac{a+b}{2}\] and of \[\textrm{min}(a,b) \].
By a similar argument, one can see that \(d\) is a common divisor of \(a\) and \(\frac{b}{2}\) (resp. \(\frac{a}{2}\) and \(b\)) in case of \(a\) and \(b\) having opposite parity.
So if \(d\) is a common divisor of \(a\) and \(b\), then \(d\) also is a divisor of the value returned by the bgcd function.
Lemma: Let \(m\) and (n) be nonzero integers such that \(m \mid n\) and \(n \mid m\). Then \(m=n\) or (m=n).
Letting \(m=\textrm{gcd(a,b)\), and \(n\) the value returned by the bgcd function, we need to show \(n \mid m\). From the definition of the greatest common divisor it follows that if \(n \mid a) and \(n \mid b), then \(n \mid m\). Clearly this is the case when \(a=b\). So we are left with the cases \(a < b\), \(b < a\). Suppose \(a < b\). Then \(m=\textrm{gcd}(a, b \bmod{a})\).
Problem Loading...
Note Loading...
Set Loading...
Easy Math Editor
*italics*
or_italics_
**bold**
or__bold__
paragraph 1
paragraph 2
[example link](https://brilliant.org)
> This is a quote
2 \times 3
2^{34}
a_{i1}
\frac{2}{3}
\sqrt{2}
\sum_{i=1}^3
\sin \theta
\boxed{123}
Comments
Sort by:
Top NewestPlease fix the LaTeX and your general formatting. Very hard to read when you display a lot of things that need not be displayed.
Log in to reply