PGCD

PGCD stands for Plus Grand Commun Diviseur, the French term for the greatest common divisor (GCD). For two integers a and b, the PGCD is the largest positive integer that divides both a and b without remainder. It is usually denoted gcd(a,b) or PGCD(a,b). The concept extends to any finite set of integers by recursively taking the gcd of pairs. The gcd is always nonnegative and depends only on the absolute values of the inputs.

Key properties include commutativity (gcd(a,b) = gcd(b,a)) and the ability to factor integers. Any common divisor of a and b also divides gcd(a,b), and gcd(a,b) divides every integer combination ax + by (Bezout’s identity). If one argument is zero, gcd(a,0) = |a| and gcd(0,b) = |b|; gcd(0,0) is treated variably in some contexts, but many definitions require at least one nonzero input to obtain a positive gcd.

The most common algorithm for computing the PGCD is the Euclidean algorithm. It uses the principle gcd(a,b) = gcd(b, a mod b) and iterates until the remainder is zero; the last nonzero remainder is the gcd. The algorithm runs in time proportional to the logarithm of the smaller input, making it efficient for large integers.

Applications of the PGCD include simplifying fractions, solving linear Diophantine equations, and testing coprimality in number theory and cryptography. Related concepts include the least common multiple (LCM) and the Extended Euclidean algorithm, which also provides coefficients x and y satisfying ax + by = gcd(a,b).