Thread: Greatset Common Divisor (GCD) Questions

Q1) Are the GCD, Greatest Common Factor (GCF) and Highest Common Factor (HCF) all referring to the same thing?

I'm using the GCD to simplify fractions to their lowest terms. To find the GCD I've been using two methods. The first method is doing prime factorization and multiplying the common prime factors together. The second method is called Euclid's algorithm. Both methods seem slow.

Q2) Should I be using GCD to simplify fractions? And does using prime factorization have a benefit over Euclid's method as I advance in Algebra or higher math?

Q3) My book shows the solution below to simply the fraction below.
3990 = 6* 665 = 665 = 7*95 = 95
6762 6*1127 1127 7*161 161

I don't understand how they arrived at the 6 and 7.
I did prime factorization and wrote out the following. (sorry, i used the , for multiplication on accident)
3990 = 2,3,7,5,19 = (2,3,7), 5,19 = 95
6762 2,3,7,7,23 (2,3,7), 7,23 161

I notice I could multiply 2*3 and arrive at the 6 and 7 like they did, but then that's doing more steps in the method I'm doing.
So I'd like to know ...

Q4) Is there is a simpler method they used to arrive at the 6 and 7?

Also, a further note, using Euclid's Algorithm was one step faster than the prime factorization in this particular problem, plus I didn't have to refer to (or memorize) a table of prime factors.

Thanks for taking the time to read my post to the end. I hope it's clear and easy to understand.

Originally Posted by MrDiedel

Q1) Are the GCD, Greatest Common Factor (GCF) and Highest Common Factor (HCF) all referring to the same thing?

Yes.

Originally Posted by MrDiedel

Q2) Should I be using GCD to simplify fractions? And does using prime factorization have a benefit over Euclid's method as I advance in Algebra or higher math?

The further you study math, the fewer numerical calculations you have to do. After you get a solid grasp of how to compute by hand, it becomes less important how you arrive at the numerical answer. Concerning fractions, I usually repeatedly divide the numerator and the denominator by the first suitable number I can find.

Originally Posted by MrDiedel

Q3) My book shows the solution below to simply the fraction below.
3990 = 6* 665 = 665 = 7*95 = 95
6762 6*1127 1127 7*161 161

I don't understand how they arrived at the 6 and 7.

3990 and 6762 are divisible by 6 because they are even and the sum of their digits is divisible by 3. For 7, they probably tried it and found that it divides both numbers. E.g., 665 = 630 + 35 = 7 * 90 + 7 * 5 and 1127 = 1120 + 7 = 7 * 16 + 7 * 1.

For really big numbers, Euclid's algorithm is more efficient because there are no currently known efficient factorization algorithms. "When the numbers are very large, no efficient, non-quantum integer factorization algorithm is known; an effort concluded in 2009 by several researchers factored a 232-digit number (RSA-768), utilizing hundreds of machines over a span of 2 years. The presumed difficulty of this problem is at the heart of widely used algorithms in cryptography such as RSA" (Wikipedia).

emakarov, I really appreicate your answer to question 2 and 3. However, I must confess I have no knowledge of RSA and the following text afterwards. I do conclude however, that they did not use anything other than guesswork to arrive at their 6 and 7 which was the point I wanted to know. As the book was not specific or clear on that point.

My conclusion,

I will use Euclid's algorithm for anything that is not apparently obvious to ME. I'm trusting your information based solely on your posts and thanks counts because I don't know you, however you appear to be intelligent and offer sound advice. Thanks again. Have a great day, I know I did!

3990/6762
It is not so simple for find prime factors.
use GCD by division method
3990)6762(1
----3990
-----------
-----2772
2772)3990(1
-----2772
-----------
------1218

1218)2772(2
-----2436
-------------
-----336
336)1218(3
----1008
---------
---- 210)336(1
---------210
--------------
-------- 126)210(1
----------- 126
----------------
---------- 84

84)126(1
--- 84
--------
----42)84(2
-------84
----------
------00
GCD is 42
3990/6762
= (3990÷ 42)/(6762÷ 42)
= 95/161
----