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.

#NumberTheory #ComputerScience #KeyTechniques

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.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered 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"

Math	Appears 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

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;

Mark Hennings - 7 years, 8 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.

Calvin Lin Staff - 7 years, 8 months ago

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

Mark Hennings - 7 years, 8 months ago

@Mark Hennings – Yes, that is the idea of the question.

Calvin Lin Staff - 7 years, 8 months ago

@Calvin Lin – 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;

Mark Hennings - 7 years, 8 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!

Pranav Arora - 7 years, 8 months ago

I hope these are right:

1) Yes, if $n < -10$

2) 7

C D - 7 years, 8 months ago

Yup.

Tim Vermeulen - 7 years, 8 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?

Nathan Antwi - 7 years, 9 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.

Calvin Lin Staff - 7 years, 9 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

Lokesh Sharma - 7 years, 8 months ago

@Lokesh Sharma – 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)

Lokesh Sharma - 7 years, 8 months ago

@Lokesh Sharma – 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.

Mark Hennings - 7 years, 8 months ago

@Lokesh Sharma – 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?

Calvin Lin Staff - 7 years, 8 months ago

@Calvin Lin – 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.

Lokesh Sharma - 7 years, 8 months ago

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

Michael Tang - 7 years, 8 months ago

@Lokesh Sharma – I think this one is good... I dident think of that.. nice..

Nathan Antwi - 7 years, 8 months ago

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

Nathan Antwi - 7 years, 9 months ago

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

Michael Tang - 7 years, 8 months ago

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

Nathan Antwi - 7 years, 8 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)

C D - 7 years, 8 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

Arulx Z - 5 years, 8 months ago

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