Fastest way to calculate the GCF and LCM

[Eddie Gutia]

I was going through the MGMAT Number properties tutorial. I am wondering if there is an easy way to calculate LCM and GCF instead of using the method proposed in the book. Definitely I don't want to draw a venn diagram in GMAT :-) Thanks in advance.

[tim]

you can't get around prime factoring each number. once you've gone to that trouble, drawing the circles around the prime factors to create a Venn Diagram is trivial. in other words, you won't be able to cut any further corners.. :)

[andrew.weimholt]

you can't get around prime factoring each number. once you've gone to that trouble, drawing the circles around the prime factors to create a Venn Diagram is trivial. in other words, you won't be able to cut any further corners.. :)

NOT TRUE.
If G is the GCF of A and B, and A>B, then
A is congruent to k*G modulo B, where k is coprime to A and B.

This means we can find G as follows...

Suppose A=462 and B=632
632 mod 462 = 170 (so G must divide 170 and furthermore G=GCF(462,170))
462 mod 170 = 122 (so G must also divide 122, by now we can see it will be 2, but let's continue...)
170 mod 122 = 48
122 mod 48 = 26
48 mod 26 = 22
26 mod 22 = 4
22 mod 4 = 2
4 mod 2 = 0 (When we get to 0, the previous number is our G, so G=2).

Let's try again with 525 and 252...
525 mod 252 = 21
252 mod 21 = 0, therefore GCF(525,252) = 21

It can seem like more work than factoring, but for large numbers, it can be faster for a computer. Here is a recursive C function to find the gcf...

typedef unsigned long long u64;

u64 gcf(u64 a, u64 b)
{
u64 L = (a>b) ? a : b;
u64 S = (a>b) ? b : a;
u64 X = L%S;
return X ? gcf(X,S) : S;
}

[tim]

Aditya, do you see now why i said you can't get around prime factoring if you want an "easy way" to do this one? As Andrew demonstrates, pretty much the only other way to do this problem is to use his Euclidean Algorithm approach, which as you can see definitely does not fit the bill of an "easy way" by any stretch of the imagination.. :)