Нахождение НОД двух чисел

[awlol]

Есть некоторое число х необходимо найти для него число у такое что удовлетворяет условие 1<у<x, НОД(y,x)=1....короче говоря нужно выбрать число меньше даного и взаимно простое с ним.

[Naive]

Пишите функцию считающую НОД 2х чисел, засовываете ее в цикл от 1 до числа Х и сравниваете с единицей. В чем сложность то?

[wm_leviathan]

{ фукнция поиска наи. общ. делителя }

function NOD(x,y:longint):longint; 
begin
   if x<>0 then NOD:=NOD(y mod x,x) else NOD:=y;
end;

begin { основная программа }
    readln(a,b);
    writeln( 'НОД этих чисел = ', NOD(a,b) );
    end.