Math Is Fun Forum

morik

Member

Registered: 2005-11-23

Posts: 16

Greatest Common Divisor

What is, and how do I find, the greatest common divisor of 771,708 ?

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: Greatest Common Divisor

The greatest common divisor is also known as the highest common factor. It's the highest number that both of your numbers are divisible by.

With relatively small numbers like yours, you can break the numbers down into their prime factors.

So, 771 = 3*257
And, 708 = 2²*3²*59

By looking at these, we can see that 3 is the highest common factor.

As your numbers get bigger though, it gets much harder to break them down into prime factors. Even 3-digit numbers like those can be a little tricky. There is, however, an alternative method called Euclid's algorithm that works much better with big numbers.

This works by dividing the bigger of your two numbers by the smaller one, and looking at the remainder. You then replace the big number with the remainder, and repeat until you get a remainder of 0. The penultimate remainder was the highest common factor.

Using your question as an example,

771 = 708(*1) + 63
708 = 11*63 + 15
63 = 4*15 + 3
15 = 5*3 (+0)

The penultimate remainder was 3, and so that is your highest common factor.

---

Why did the vector cross the road?
It wanted to be normal.

morik

Member

Registered: 2005-11-23

Posts: 16

Re: Greatest Common Divisor

Ah I understand now! Thanks for the explanation

pikatan

Member

Registered: 2008-06-06

Posts: 10

Re: Greatest Common Divisor

use MS Excel and type =GCD(771,708 ) you will get 3

Zazu

Member

Registered: 2022-11-22

Posts: 3

Re: Greatest Common Divisor

This can also be solved quickly using the GCD calculator with steps.

Last edited by Zazu (2022-11-23 01:00:03)