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})$.
Easy Math Editor
This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.
When posting on Brilliant:
*italics*
or_italics_
**bold**
or__bold__
paragraph 1
paragraph 2
[example link](https://brilliant.org)
> This is a quote
\(
...\)
or\[
...\]
to ensure proper formatting.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