Ну, можно порыть алгоритм в инете.
С другой стороны, могу подсказать некоторую эвристику.
1. НОД не может быть больше меньшего числа.
2. Нужно сравнивать отстатки от деления (д.б. = 0).
Код:
function FindNOD(A, B : Integer) : Integer;
begin
Result := Min(A,B);
While Result > 1 Do
If ((A mod result) = 0) And ((B mod result) = 0)
Then Break
Else Dec(Result);
end;
PS. Для данного кода входные значения д.б. положительные. Для отрицательных поправь вычисление стартового числа (в Min числа взять Abs).