what are two methods for Greatest Common Factors?

Answer 1

The greatest common divisor (gcd) can be found in (at least) two different methods:

1st (and most likely the most simple):
Split the two numbers a and b into their prime factorizations:
a=2^(a1) • 3^(a2) • 5^(a3) • . . . • (pn)^(an) • (p(n+1))^(a(n+1)) • . . .
b=2^(b1) • 3^(b2) • 5^(b3) • . . . • (pn)^(bn) • (p(n+1))^(b(n+1)) • . . .
let cn=max(an,bn)
then gcd(a,b) = 2^(c1) • 3^(c2) • 5^(c3) • . . . • (pn)^(cn) • (p(n+1))^(c(n+1)) • . . .

For example let a=112, and b=244
a = 16•7 = 2^4•3^0•5^0•7^1•11^0 . . .
b = 4•61 = 2^2 • 61^1 (leaving out the primes to 0th power, since they are just multiples of 1)

thus c1 = 2, and all other cn = 0 for all n>1, thus the gcd(112,244) = 4

2nd method:
By using the division algorithm (a>b)
a=(q1)b+(r1) where 0≤r1 b= (q2)(r1)+ (r2) where 0≤r2 . . .
rn=(q(n+2))(r(n+1))+(r(n+2)) where 0≤r(n+2)
now compute until the first time rn=0, then the gcd(a,b) = r(n-1)

Example a=112, b=244

244 = 2•112+20 r1=20
112 = 5•20+12 r2=12
20 = 1•12+ 8 r3=8
12 = 1•8+4 r4=4
8 = 2•4+0 r5=0

Thus we go up the the line before:
12 = 1•8+4 and look at the remainder r4=4. The gcd(112,244) = r4=4.


Those are the two most common ways (in my opinion).

Answer 2

let's say you want the GCF of A and B. Lets say A= 1001 and B is 154.
1. factor A into all of its primes: e.g. 1001 = 7 * 11 * 13
2. factor B int all of its primes: e.g. 154 = 2* 7 * 11
3. collect all the common factors: 7, 11
4. multiply them all together 7*11 = 77.
therefore 77 is the GCF of 1001 and 154.

Answer 3

1) List all the factors (This method is best when you are working with small numbers).
2) Use the prime factorization form of the numbers (This method is best for large numbers).