# Another way of computing the gcd of 2 integers

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 def bgcd(a,b): arg1=int(a) arg2=int(b) factor = 1 while arg1 != arg2: while (arg1 & 1 ==0) and (arg2 & 1 ==0): arg1 /=2 arg2 /=2 factor*=2 while arg2 & 1 ==0: arg2 /= 2 while arg1 & 1 ==0: arg1 /=2 if arg1 & 1 ==1 and arg2 & 1 == 1: mean=(arg1+arg2)/2 if arg1 < arg2: arg2 = mean else: arg1=mean return factor * arg1 

Assuming $a$ and $b$ are distinct positive integers, on each iteration of the loop starting on line 5 $arg1 +arg2$ gets smaller.

• If $a$ and $b$ both are even, then $\frac{a}{2} +\frac{b}{2} < a +b$.
• If both $a$ and $b$ are odd, then $\textrm{min}(a,b) +\frac{a+b}{2} =a+b -\frac{\lvert a-b\rvert}{2} < a+b$

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 non-zero 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})$. Note by A Former Brilliant Member 2 years, 5 months ago 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: • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused . • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone. • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge. • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events. MarkdownAppears as *italics* or _italics_ italics **bold** or __bold__ bold - bulleted- list • bulleted • list 1. numbered2. list 1. numbered 2. list Note: you must add a full line of space before and after lists for them to show up correctly paragraph 1paragraph 2 paragraph 1 paragraph 2 [example link](https://brilliant.org)example link > This is a quote This is a quote  # I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world" # I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world" MathAppears as Remember to wrap math in \( ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by: