Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

Pages: **1**

**morik****Member**- Registered: 2005-11-23
- Posts: 16

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

Offline

**mathsyperson****Moderator**- Registered: 2005-06-22
- Posts: 4,900

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.

Offline

**morik****Member**- Registered: 2005-11-23
- Posts: 16

Ah I understand now! Thanks for the explanation

Offline

**pikatan****Member**- Registered: 2008-06-06
- Posts: 10

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

Offline

**Zazu****Member**- Registered: 2022-11-22
- Posts: 3

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

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

Offline

Pages: **1**