Greatest common divisor
Euclidean algorithm

A more efficient method is the Euclidean algorithm, a variant in which the difference of the two numbers a and b is replaced by the remainder of the Euclidean division (also called division with remainder) of a by b.

Denoting this remainder as a mod b, the algorithm replaces (a, b) with (b, a mod b) repeatedly until the pair is (d, 0), where d is the greatest common divisor.

For example, to compute gcd(48,18), the computation is as follows:

This again gives gcd(48, 18) = 6.
language:response_language[Italian]