Greatest common divisor of two positive integer numbers N and M, both larger then zero is the largest integer R that divide both N and M. If for given N and M, greatest common divisor is 1, we say that N and M are relatively prime, or coprime. The easiest practical way for finding greatest common divisor is Euclidean algorithm, described as follows:

**Step 1:**

Compare N and M, and if M is larger then swap them so that N is made to be larger number.

**Step 2:**

Find reminder when N is dived with M ( R = N div M )

**Step 3:**

If reminder is greater then zero, then let N take value of M, M take value of R

**Step 4:**

Calculate R again as reminder of new N and M

**Step 5:**

Repeat steps 3 and 4 as long as R greater then zero.

**Step 6:**

Once when R reaches zero, return M as greatest common divisor.

Code is as follows:

static int GCD(int N, int M)

{

int R;

R = N % M;

while (R > 0)

{

N = M;

M = R;

R = N % M;

}

return M;

}

static void Main(string[] args)

{

int A = 518;

int B = 392;

int C = GCD(A, B);

Console.WriteLine(“{0}”, C);

Console.ReadLine();

}

Greatest common divisor can be used for reducing fractions and for finding least common multiple.

Calculate greatest common divisor online.

**External links:**

Greatest Common Divisor on Wikipedia

Greatest Common Divisor on Calculatorsoup

Greatest Common Divisor on Mathportal

## Leave a Reply