×

# GCD and the Euclidean Algorithm

Introducing …. the Greedy Calvinosaurus Dinosaur

In this week's post, learn about Greatest Common Divisor.

Last week, we introduced several questions based on calculating the Greatest Common Divisor of several integers and polynomials. Using the Euclidean Algorithm is a standard approach to helping us to quickly calculate these values.

Judging from the comments in the solution discussions, here are some questions for you to ponder:

1) If $$n < 10$$, can $$\gcd (n, m ) > 10$$?

2) What is the value of $$\gcd( -14, -21 )$$?

3) Why does the Euclidean algorithm work? Specifically, why does $$\gcd(n,m) = \gcd(n, m+kn )$$ for any integers $$n, m, k$$?

For those who want a coding challenge:

Write code to calculate the GCD of 2 numbers, which ends in finitely many steps. You are not allowed to use conditions like “If n > 0, continue” or equivalent hacks.

Note by Calvin Lin
4 years, 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}$$

Sort by:

I generally programme in Pascal. Apart from the setting-up exercises (to ensure that $$a$$ and $$b$$ are positive and ordered), the function calls itself recursively as many times as the Euclidean algorithm is used in the calculation of the gcd.

function gcd(a,b: Integer): Integer;
begin
if ((a < 0) or (b < 0)) then
begin
Result := gcd(Abs(a),Abs(b));
exit;
end;
if a < b then
begin
Result := gcd(b,a);
exit;
end
if b = 0 then
Result := a
else
Result := gcd(b, a%b);
end;


- 4 years, 4 months ago

As I said, you are not allowed to use "if n $$> 0$$" conditions (similarly for "while $$n>0$$"). You have hidden it within calling of the gcd function.

The main aspect of this problem is to figure out the number of steps which the Euclidean algorithm has to take.

Staff - 4 years, 4 months ago

So you want to know about the time complexity of the Euclidean algorithm. Try some consecutive Fibonacci numbers.

- 4 years, 4 months ago

Yes, that is the idea of the question.

Staff - 4 years, 4 months ago

If $$a \ge b \ge 1$$, then the number of applications of the Division Algorithm needed to calculate the HCF of $$a$$ and $$b$$ is no greater than $$5\log_{10} b$$. Thus:

function gcd(a,b: Integer): Integer;
var i,j,k,m: Integer;
begin
if Abs(a) >= Abs(b) then
begin
Result := Abs(a);
j := Abs(b);
end
else
begin
Result := Abs(b);
j := Abs(a);
end;
k := Int(5*Log(j));
for i := 1 to k do
begin
if j = 0 then break;
m := j;
j := Result % j;
Result := m;
end;
end;


- 4 years, 4 months ago

I hope these are right:

1) Yes, if $$n < -10$$

2) 7

- 4 years, 4 months ago

Yup.

- 4 years, 4 months ago

Hello Calvin! Will you post the answers to the 3 questions in the future? That would greatly help.

A few questions, how do you define gcd of negative numbers? Can you please give a few hints for the second question? In the first question, can n be negative?

Thanks!

- 4 years, 4 months ago

@Calvin What do you mean by " finite many steps"? Do you mean to write a code in the least amount of lines of code?

- 4 years, 4 months ago

It shouldn't have a phrase equivalent to "If $$n, m>0$$, continue".

It can have a phrase "For i = 1 to $$\max(n,m)$$", though of course this is very inefficient.

Staff - 4 years, 4 months ago

Is this one legit?

def gcd(m, n):

a = max(abs(m), abs(n))

b = min(abs(m), abs(n))

for i in reversed(range(b+1)):

if a % i == 0 and b % i == 0:

return i


- 4 years, 4 months ago

This has to check every number from 1 to $$\max(a,b)$$, which is extremely tedious. What is the complexity of your statement? How many steps would it take for you to find the gcd two $$10^9$$ numbers?

Staff - 4 years, 4 months ago

The complexity is O(n) I guess, because it would take about min(a, b) steps in the worst case to find the GCD. Right? How can I find the complexity of the one down below? I think it's O(log(n)) but I am not at all sure and have no idea how to find it. What does it mean to 'find the gcd two $$10^9$$ numbers'? Thanks for replying.

- 4 years, 4 months ago

I'm guessing he means "find the GCD of two numbers each about $$10^9.$$"

- 4 years, 4 months ago

I am wondering, compared to the one below and above, which one's the better one in terms of speed?

def gcd2(m, n):

a, b = max(abs(m), abs(n)), min(abs(m), abs(n))

if a % b == 0:

return b

elif a % b == 1:

return 1

else:

return gcd2(b, a%b)


- 4 years, 4 months ago

Your code would crash if you entered $$0$$ as one of the values - it would try to divide by $$0$$.

If you fix this, the code is about optimal for speed, but it breaks the rules about no loops, like my first version did.

- 4 years, 4 months ago

I think this one is good... I dident think of that.. nice..

- 4 years, 4 months ago

Alright. I'm working on a code right now...during class.

- 4 years, 4 months ago

So in Python, we can't use a while loop?

- 4 years, 4 months ago

I guess not..All the codes i have scripted use a loop and i guess thats not permitted here.

- 4 years, 4 months ago

1) If $$n < 10$$, then $$gcd(n, m)$$ can be greater than $$10$$. This is because if n can be negative too. Here's an example $$gcd(-20, 40) = 20$$.

2) $$gcd(-14, -21) = 7$$

3) I'll post it later

- 2 years, 3 months ago

I'm not sure if this is allowed but it works.

astr = input("Type first number") bstr = input("Type second number") a = int(astr) b = int(bstr) while a < b or a > b: if a > b: a = a-b else: b = b-a if a == b: astr1 = str(a) print(astr1)

- 4 years, 4 months ago