ЗАДАНИЕ №2. Даны натуральные числа х и у, не равные нулю одновременно

Даны натуральные числа х и у, не равные нулю одновременно. Найти d=НОД (х, у) и такие целые q и w, что d = q*x + w*y.

Решение:

Введем переменные p, q, r, s, m и n, такие, что m = p*a + q*b, n = r*a + s*b. Первоначально m = a = x, n = b = y.

Имеем программу:

Program example1;

Var

x, y: integer;

p, q, r, s, m, n: integer;

{Вспомогательные переменные}

d: integer;

{Значение наибольшего общего делителя}

begin

read (x, y);

m: =x; n: =y; p: =1; q: =0; r: =0; s: =1;

Repeat

If m> n

then

begin

k: =m div n;

m: = m mod n;

p: =p-k*r;

q: =q-k*s

end

else

begin

k: =n div m;

n: =n div m;

r: =r-k*p;

s: =s-k*q

end;

Until (m=0) or (n=0);

If m=0

then

begin

d: =n; q: =r; w: =s

end

else

begin

d: =m; q: =p; w: =q

end;

writeln (d, ‘ – ‘, q, ‘ * ‘, x, ‘ + ‘, w, ‘ * ‘, y);

readln

end.

Значение переменных p, q, r, s изменяются следующим образом:

· Как только значение переменной m уменьшается на k*n, значение p уменьшается на k*r, а q уменьшается на k*s;

· Аналогично, как только значение n уменьшается на k*m, значение переменных r и s уменьшаются соответственно на k*p и на k*q.

Задачи для самостоятельного решения.

1. Найти НОД трех чисел, учитывая НОД (а, b, c) = НОД (НОД (a, b), c).
2. Два числа называются взаимно простыми, если их наибольший общий делитель равен 1. Проверить, являются ли два данных числа взаимно простыми.
3. Найти наименьшее общее кратное (НОК) чисел n и m, используя соотношение:
4. От прямоугольника 324*141 отрезают квадраты со сторонами 141, пока это возможно. Затем вновь отрезают квадраты со стороной, равной 324-2*141=42 и т. д. На какие квадраты и на сколько квадратов будет разрезан прямоугольник?
5. Написать программу для нахождения НОД, используя следующие соотношения: НОД (2а, 2b) = 2НОД (а, b)

НОД (2а, b) = НОД (а, b) при нечетном b.

В программе не должно использоваться деление с остатком. Можно лишь делить на 2 и проверять числа на четность.