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
3 months, 1 week ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 1

paragraph 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

There are no comments in this discussion.

×

Problem Loading...

Note Loading...

Set Loading...