## Assignment 2: Euclid's algorithm for GCD(A,B)

Weight : 30
Due Date:  3rd Feb.

- Make FORTRAN 90 Source and output into one file and upload to your HUxx account in MUSICB.

- E-MAIL that file to HUAB on MUSIC B from your HUxx account.

#### This assignment has to be done in FORTRAN 90, using the LAHEY compiler, which you can download for free from www.lahey.com or this is available in the EMF.See the documentation on the LAHEY website for installation and running programs on your own machine. Note your FORTRAN 90 source code should be the ELF90 directory with the compiler for easy operation.

If A and B are two integers, any number that divides both A and B is called a common divisor of A and B. For example, the common divisors of 12 and 18 are 1,2,3,6. The largest of the divisors is called the GCD(Greatest Common Divisor) of A and B. A procedure known as Euclid's algorithm is one of the basic methods of elementary number theory. Suppose that A and B are the two integer numbers. We divide B into A, using integer division, finding a quotient Q and a remainder R. This means that
A = Q*B + R
Then we divide R into B and keep iterating until the remainder is 0. The last nonzero divisor becomes the GCD.
For example, to find the GCD of  1976  and  1032

1976 = 1032 x 1 + 944
1032 = 944 x 1 + 88
944 = 88 x 10 + 56
88 = 56 x 1 + 32
56 = 32 x 1 + 24
32 = 24 x 1 + 8
24 =  8 x 3 + 0

The GCD of 1976 and 1032 is 8.

Find the GCD of following datas.

60      5280
139     49
3850    5280
1124    1472
17296   18416
76084   63020
13398   7854