PDA

View Full Version : easy way of finding GCD !



Edstroyer
10-28-2004, 07:05 AM
this method is called " method of successive division"

example : find the Greatest Common Divisor (GCD) of the two numbers:

31 and 27 ... ofcourse, you can pick any other two numbers, its that easy!

notice the pattern because its the only way i can explain it:

START :

31 = (27)*1 + [4]
(27) = [4]*6 + {3}
[4] = {3}*1 + (1) <--- GCD = (1)
{3} = (1)*3 + 0 ----> STOP when you see the Zero , your GCD is the previous step

ofcourse the GCD is a 1 because 31 is a prime , but try two other numbers and see how quick and easy this method is.

might just save you on the actual exam :whistle:

sabna
10-30-2004, 08:42 AM
hi....
its nice of u!!!!

thanks!!!!!!

sabna

calm_J
11-02-2004, 06:49 PM
thanks,
it's very helpful and fast

manwiththemission2005
10-22-2005, 01:24 PM
A really good method for finding GCD.

qiwenfarmer
10-23-2005, 04:26 PM
good work, never thought of it

SNYP40A1
09-10-2006, 09:58 PM
This deserves a bump!

bscout
09-11-2006, 03:31 PM
This kind of question is common on the GRE?

44 and 28

44 = (28)*1+[16]
28 = [16]*1+{12}
16 = {12}*1+(4)
12 = 4*3+0 ==> Answer 4. Is this right?

Annie9
09-11-2006, 05:15 PM
clear on this? Can someone explain?

jinics
10-13-2006, 11:18 PM
let me do it another way a bit graphical

---> 1
-->----
28 |44
---> 28 1
--->----------
--->16 | 28
-------->16 1
-------->----------
-------->12 | 16
------------->12 3
------------->-------------
------------->4 | 12
----------------->12
----------------->--------
------------------>X
----------------->---------

So 4 is the GCF.


regards
jinics

sarapigasso
10-15-2006, 05:21 PM
is this better?

44,28

1 l 44
2 l 22
2 l 11 prime =ending


1 l 28
2 l 14
2 l 7 prime = ending

answer is 1*2*2 = 4

just an alternative

Skl
10-16-2006, 05:36 AM
just wanna clarify, by solving this, is this correct?

25,16

25=16*1+[9]
16=[9]*1+{7}
[9]={7}*1+(2)
{7}=(2)*3+ 1
(2)= 1 * {2}+0

Is the GCD 1 for these two numbers.

jinics
10-16-2006, 07:33 AM
Is the GCD 1 for these two numbers.

yup :)

een
10-16-2006, 07:49 AM
Hi,Skl!
You are absolutely right! It is the Euclidean algorithm.
All the best!
Katya