Name

Edit

## Overview

### Notation

### Example

### Reducing fractions

### Coprime numbers

### A geometric view

### Using Euclid's algorithm

In mathematics, the **greatest common divisor** (**gcd**), also known as the **greatest common factor** (**gcf**), or **highest common factor** (**hcf**), of two or more integers (at least one of which is not zero), is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4.

This notion can be extended to polynomials, see Polynomial greatest common divisor, or to rational numbers (with integer quotients).

In this article we will denote the greatest common divisor of two integers *a* and *b* as gcd(*a*,*b*). Some older textbooks use (*a*,*b*).^{[1]}^{[2]}

The number 54 can be expressed as a product of two other integers in several different ways:

Thus the **divisors of 54** are:

Similarly **the divisors of 24** are:

The numbers that these two lists share in common are the **common divisors** of 54 and 24:

The greatest of these is 6. That is the **greatest common divisor** of 54 and 24. One writes:

The greatest common divisor is useful for reducing fractions to be in lowest terms. For example, gcd(42, 56) = 14, therefore,

Two numbers are called *relatively prime*, or *coprime* if their greatest common divisor equals 1. For example, 9 and 28 are relatively prime.

For example, a 24-by-60 rectangular area can be divided into a grid of: 1-by-1 squares, 2-by-2 squares, 3-by-3 squares, 4-by-4 squares, 6-by-6 squares or 12-by-12 squares. Therefore, 12 is the greatest common divisor of 24 and 60. A 24-by-60 rectangular area can be divided into a grid of 12-by-12 squares, with two squares along one edge (24/12 = 2) and five squares along the other (60/12 = 5).

A much more efficient method is the Euclidean algorithm, which uses a division algorithm such as long division in combination with the observation that the gcd of two numbers also divides their difference. To compute gcd(48,18), divide 48 by 18 to get a quotient of 2 and a remainder of 12. Then divide 18 by 12 to get a quotient of 1 and a remainder of 6. Then divide 12 by 6 to get a remainder of 0, which means that 6 is the gcd. Note that we ignored the quotient in each step except to notice when the remainder reached 0, signalling that we had arrived at the answer. Formally the algorithm can be described as:

- ,

where

- .

If the arguments are both greater than zero then the algorithm can be written in more elementary terms as follows:

- if
*a*>*b* - if
*b*>*a*

C++