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 aa and bb are distinct positive integers, on each iteration of the loop starting on line 5 arg1+arg2arg1 +arg2 gets smaller.

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

The same goes when aa and bb are of opposite parity.

Suppose aa and bb are distinct positive integers not both even. If dd is a common divisor of aa and bb, then dd must also be odd.

  • If both aa and bb are odd, then a+ba +b is even. Let rr be the largest power of 2 dividing a+ba +b. Since 2r2^{r} and dd are relative prime, then dd is a divisor of a+b2r\frac{a+b}{2^{r}}. Therefore dd is also a divisor of a+b2\frac{a+b}{2} and of min(a,b)\textrm{min}(a,b) .

  • By a similar argument, one can see that dd is a common divisor of aa and b2\frac{b}{2} (resp. a2\frac{a}{2} and bb) in case of aa and bb having opposite parity.

So if dd is a common divisor of aa and bb, then dd also is a divisor of the value returned by the bgcd function.

Lemma: Let mm and (n) be non-zero integers such that mnm \mid n and nmn \mid m. Then m=nm=n or (m=-n).

Letting m=\textrm{gcd(a,b), and nn the value returned by the bgcd function, we need to show nmn \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=ba=b. So we are left with the cases a<ba < b, b<ab < a. Suppose a<ba < b. Then m=gcd(a,bmoda)m=\textrm{gcd}(a, b \bmod{a}).

Note by Brilliant Member
1 year, 5 months ago

No vote yet
1 vote

  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:

  • 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. 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×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 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.

A Brilliant Member - 12 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...