[Pavluha]

Код:

var n1,n2,r:longint;
function nod(a,b:longint):longint;
begin
 while (a<>0)and(b<>0) do
  if a>b then a:=a mod b else b:=b mod a;
 nod:=a+b;
end;
begin
 readln(n1,n2);
 r:=nod(n1,n2);
 writeln(r);
end.

вот оптимальный более-менее алгоритм. если нужно объяснить как работает -- пиши.

Pavluha, Но при целочисельных типах, кажется, нельзя делить »

делить нельзя, зато можно получить целую часть от деления (div) или остаток (mod).

если вдруг нужно будет найти НОК (наименьшее общее кратное, воспользуйся формулой n1*n2=НОД(n1,n2)*НОК(n1,n2).)