##  [Greatest Common Divisor](/greatest-common-divisor-0) 

 Definition

For integers a and b (not both zero), the greatest common divisor gcd(a,b) is the largest positive integer that divides both a and b without remainder.

 

 

 

 

 

 





## Principle

Principle

Among common divisors of two integers choose the maximal element under the usual order on positive integers; gcd is unique and can be characterized by Bézout's identity as the minimal positive linear combination of the integers.

 

 

 

 

 





## Demonstration

Demonstration

gcd(48,18)=6 because 6 divides both 48 and 18, and no larger positive integer does; also 6 = 48·(−1) + 18·3 verifies Bézout's relation.

 

 

 

 

## Misapplication

Misapplication

Confusing gcd with least common multiple, or using gcd algorithms incorrectly by assuming prime factorizations are required for computation; treating gcd(0,0) as well-defined without context.

 

 

 

 

 





## Consequence

Consequence

Correct use of gcd simplifies fraction reduction, computation of integer solutions to linear Diophantine equations, and understanding of modular inverses (existence when gcd=1).

 

 

 

 

## Reversal

Reversal

The complementary notion is least common multiple: while gcd is the greatest common divisor, lcm is the least common multiple; one inverts focus from common factors to common multiples.

 

 

 

 

 





## Boundary

Boundary

Defined for integers (including negatives by absolute value) and usually for pairs or finite tuples; gcd(0,0) is conventionally undefined or set to 0 depending on context and must be handled explicitly. Applies to principal ideal domains but not directly to arbitrary rings without modification.

 

 

 

 

 





## Semantic Tension

Semantic Tension

Tension with the concept of 'coprime': gcd(a,b)=1 is a property rather than a magnitude; also relates to Bézout coefficients which are not unique though gcd is unique up to sign.

 

 

 

 

 





## Synthesis

Synthesis

The greatest common divisor of integers a and b is the largest positive integer dividing both, uniquely determined and central to divisibility, reduction of fractions, and solvability of linear Diophantine relations.