Greatest common divisor

January 27, 2021

Bob has a strange problem. He has two fishing rods and thinks he can make more of them – by breaking them. Yeah, he's Bob – Pat and Mat's second cousin.

Bob making fishing rods

The original two rods are 10 and 15 meters long.

Bob sets himself two conditions:

  1. The new rods should all be the same length. In math jargon – the length of the new type of phishing rods should divide the length of the first rod as well as the length of the second rod.
  2. The length of the new rods should be as big as possible.

Yeah, Bob could make rods with a length of 1 meter. But is the second condition met? No.

He could try to make rods 2 meters long. Unfortunately, he would get seven and a half rods from the second rod (of 15 meters) 2 doesn't divide 15. Not good.

How about 5 meters? Bob would get two rods from the first rod and three rods from the second one. And he can't go any higher, so that's good. As soon as he executes his plan, he'll have five rods. He'll be able to go fishing with Pat and Mat. And two other friends.

Incidentally, Bob found a function to compute such a length. Just in case he will need to make some new phishing rods. This function is called the greatest common divisor.

Definition: The greatest common divisor of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers.

Being proactive Bob started building a computational engine – you can try the engine below, just type something like:

gcd 10 15
Bob's engine

There are no words to describe how disappointed Pat and Mat were when they heard they couldn't go fishing. Something went wrong in spite of all the heavy preparations. Somehow the rods were not useful at all.

You might want to observe the notes Bob took while studying
. Nothing beats a simple example.

gcd(60, 18)gcd(62, 18)gcd(65, 18)
60 - 3 ⋅ 18 = 662 - 3 ⋅ 18 = 865 - 3 ⋅ 18 = 11
18 - 3 ⋅ 6 = 018 - 2 ⋅ 8 = 218 - 1 ⋅ 11 = 7
8 - 4 ⋅ 2 = 011 - 1 ⋅ 7 = 4
7 - 1 ⋅ 4 = 3
4 - 1 ⋅ 3 = 1
3 - 3 ⋅ 1 = 0

In each step, you subtract the multiplication of the smaller number from the larger one. Once you get 0, the

can be found in the next to last line.


The Alice and Bob newsletter

Get highlights of Alice and Bob's adventures delivered to your email box.

Made by XLAB with ❤️
Follow us
Twitter Twitter