Greatest common divisor

The greatest common divisor of two integers is the largest integer that divides them both. If numbers are 121 and 143 then greatest common divisor is 11.

There are many methods to calculate this. For example, the division-based Euclidean algorithm version may be programmed:

function greatestCommonDivisor

function greatestCommonDivisor(a, b: Int64): Int64;
var
  temp: Int64;
begin
  while b <> 0 do
  begin
    temp := b;
    b := a mod b;
    a := temp
  end;
  result := a;
end;

function greatestCommonDivisor_euclidsSubtractionMethod(a, b: Int64): Int64;
begin
  // only works with positive integers
  if (a < 0) then a := -a;
  if (b < 0) then b := -b;
  // don't enter loop, since subtracting zero won't break condition
  if (a = 0) then exit(b);
  if (b = 0) then exit(a);
  while not (a = b) do
  begin
    if (a > b) then
     a := a - b
    else
     b := b - a;
  end;
  result := a;
end;

see also

• least common multiple
• mod operator
• mpz_gcd in GMP (GNU multiple precision)

external references

• Recursive example

From the Free Pascal wiki, page "Greatest common divisor", as it stood on 2023-12-13 after a change by Rvr, out of the wiki's dump of 2024-05-26. Copyright stays with the author who wrote it, according to the old wiki's Licensing page. If you have concerns about this material, message the admin.