# 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 Brilliant Member
1 year, 4 months ago

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}$

## Comments

Sort by:

Top Newest

Please fix the LaTeX and your general formatting. Very hard to read when you display a lot of things that need not be displayed.

- 11 months, 1 week ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...