Определите значения x и y для заданныхм значений a и b .

[cail10]

В математике доказывается следующая теорема.Если a и b одновременно не равны нулю, то существуют целые числа x и y, такие, что НОД(a,b)= ax+by. Теорема не утверждает, что x и y определены однозначно, она лишь говорит о том, что НОД(a,b) может быть выражен в таком виде.
Привер: 6=НОД(12,-30)=12*3+(-30)*1==12*(-2)+(-30)*(-1)
Определите значения x и y для заданныхм значений a и b .
Блок схему и программу,пожалуйста))

[alexander13]

Гуглим соотношение Безу и алгоритм Евклида.

[cail10]

Ну реши уж,если сам знаешь)Пожалуйса))

[alexander13]

Сообщение от cail10

Ну реши уж,если сам знаешь)Пожалуйса))

После того, как увижу Ваши наработки и заинтересованность в решении.

[Poma][a]

Ну реши уж,если сам знаешь)Пожалуйса))

Ага! И принести на блюдечке с голубой каемочкой..

Гуглим соотношение Безу и алгоритм Евклида.

Александр, Спасибо!

Но все-таки я не понял как решить эту задачку, а гугл играет в партизана..

Задачу можно разбить на 2 подзадачи :
1) Находим НОД (как его найдем - это дело десятое)
2) Ищем коэффициенты Безу..

Вот со 2 у меня и проблемы.. Как искать эти коэффициенты? Перебор? А откуда и до куда? А если не он, то что?
За ранее спасибо!

[Mad_Cat]

можно наверно поискать примеры при которых решение не пройдет но мне лень честно говоря

var x,y,m,n:Longint;
i,j:Longint;
function NOD(x,y:longint):longint;
 begin
  if x<>0 then NOD:= NOD(y mod x,x) else NOD:= y;
 end;
begin
write('x=');readln(x);
write('y=');readln(y);
n:=NoD(x,y);
m:=x div n;
if m < (y div n) then m :=y div n;
for i := -m to m do
  For j:=-m to m do
  begin
    if x*i+y*j=n then
    writeln('(',x,')*(',i,')+(',y,')*(',j,')=(',n,')');
  end;
readln;
end.

[alexander13]

Сообщение от Poma][a

Вот со 2 у меня и проблемы.. Как искать эти коэффициенты? Перебор? А откуда и до куда? А если не он, то что?

Ищем НОД по алгоритму Евклида, как

a = b*q0 + r1
b = r1*q1 + r2
...
r[n-1] = rn*qn

Потом можем через связь остатков и НОДа найти коэффициенты перед a и b, для чего выражаем из первого равенства r1 = a - b*q0 и так далее, до самого НОДа. Получаем в итоге что-то типа

НОД = a*f1(q0,...,qn) + b*f2(q0,...,qn)

Отсюда находим частные коэффициенты. А потом по формуле можно вычислить все множество коэффициентов Безу, зная НОД и частные коэффициенты.


Upd.
На примере проще. Допустим, для чисел 380 и 24. Ищем НОД:

a = b*q0 + r1  ---  380 = 24*15 + 20
b = r1*q1 + r2  ---  24 = 20*1 + 4
r1 = r2*q2 + r3  ---  20 = 4*5 + 0

Откуда, НОД = 4, q0 = 15, q1 = 1.
Теперь ищем x и y.

r1 = a - b*q0
r2 = b - r1*q1 = b - a*q1 + b*q0*q1 = b(1 + q0*q1) + a(-q1) = a*xч + b*yч
xч = -q1 = -1
yч = 1 + q0*q1 = 16

Ну и множество (x,y) определяется как

(xч + k*b/НОД, yч - k*a/НОД)

В нашем случае (-1 + 6*k, 16 - 95*k), где k - целое число. Как-то так.

[Poma][a]

Огроменное Спасибо!!