TeXipedia

gcd

Represents the greatest common divisor function in mathematics, used to find the largest number that divides two integers.

Overview

Essential in number theory and abstract algebra for analyzing relationships between integers and polynomial expressions.

  • Commonly used in fraction simplification and modular arithmetic.
  • Appears frequently in cryptography and computer science algorithms.
  • Important in solving Diophantine equations and determining coprimality.
  • Often paired with the least common multiple (LCM) in mathematical proofs and computations.

Examples

Finding the greatest common divisor of two numbers.

gcd⁡(24,36)=12\gcd(24, 36) = 12 
\gcd(24, 36) = 12

Using GCD in a number theory equation.

gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a,b) = \gcd(b, a \bmod b) 
\gcd(a,b) = \gcd(b, a \bmod b)

Expressing Bézout's identity with GCD.

gcd⁡(a,b)=ax+by for some x,y∈Z\gcd(a,b) = ax + by \text{ for some } x,y \in \mathbb{Z} 
\gcd(a,b) = ax + by \text{ for some } x,y \in \mathbb{Z}