Greatest Common Divisor

The greatest common divisor of $a$ and $b$ GCD($a,b$), sometimes written $(a,b)$, is the largest Divisor common to $a$ and $b$. Symbolically, let

$$a \equiv \prod_i {p_i}^{\alpha_i}$$ (1)

$$b \equiv \prod_i {p_i}^{\beta_i}$$ (2)

Then the greatest common divisor is given by

$$(a,b)=\prod_i {p_i}^{\min(\alpha_i,\beta_i)},$$ (3)

where min denotes the Minimum. The GCD is Distributive

$$(ma,mb)=m(a,b)$$ (4)

$$(ma,mb,mc)=m(a,b,c),$$ (5)

and Associative

$$(a,b,c)=((a,b),c)=(a,(b,c))$$ (6)

$$(ab,cd)=(a,c)(b,d)\left({{a\over (a,c)}, {d\over (b,d)}}\right)\left({{c\over (a,c)}, {b\over (b,d)}}\right).$$ (7)

If $a=a_1(a,b)$ and $b=b_1(a,b)$, then

$$(a,b)=(a_1(a,b),b_1(a,b))=(a,b)(a_1,b_1),$$ (8)

so $(a_1,b_1)=1$ and $a_1$ and $b_1$ are said to be Relatively Prime. The GCD is also Idempotent

$$(a,a)=a,$$ (9)

Commutative

$$(a,b)=(b,a),$$ (10)

and satisfies the Absorption Law

$$[a,(a,b)]=a.$$ (11)

The probability that two Integers picked at random are Relatively Prime is $[\zeta(2)]^{-1}=6/\pi^2$, where $\zeta(z)$ is the Riemann Zeta Function. Polezzi (1997) observed that $(m,n)=k$, where $k$ is the number of Lattice Points in the Plane on the straight Line connecting the Vectors (0, 0) and $(m, n)$ (excluding $(m, n)$ itself). This observation is intimately connected with the probability of obtaining Relatively Prime integers, and also with the geometric interpretation of a Reduced Fraction $y/x$ as a string through a Lattice of points with ends at (1,0) and $(x,y)$. The pegs it presses against $(x_i, y_i)$ give alternate Convergents $y_i/x_i$ of the Continued Fraction for $y/x$, while the other Convergents are obtained from the pegs it presses against with the initial end at (0, 1).

Knuth showed that

$$(2^p-1, 2^q-1)=2^{(p,q)}-1.$$ (12)

The extended greatest common divisor of two Integers $m$ and $n$ can be defined as the greatest common divisor $(m, n)$ of $m$ and $n$ which also satisfies the constraint $(m,n)=rm+sn$ for $r$ and $s$ given Integers. It is used in solving Linear Diophantine Equations.

See also Bezout Numbers, Euclidean Algorithm, Least Prime Factor

References

Polezzi, M. ``A Geometrical Method for Finding an Explicit Formula for the Greatest Common Divisor.'' Amer. Math. Monthly 104, 445-446, 1997.