http://algolist.manual.ru/maths/teornum/nod.php#3
Можно ли его модифицировать так, чтобы все операции проводились только с неотрицательными числами? Важно только получение коэффициента при меньшем из a и b.

имеется в виду ax+by=1 или ax+by=1 mod m?
(потому что ответы для этих случаев будут разные)

ax + by = 1.
Изначально уравнение имеет вид by = 1 (mod a).

ну тогда без отрицательных чисел не получится
отбросим случай, когда одно из чисел =1
тогда какие бы ни были a и b>0, a*x+b*y будет >=x+y>1
т.е. отрицательные числа не просто возможны - один из коэффициентов всегда будет отрицательным

Именно отрицательный коэффициент мне и не нужен. Поэтому, может быть, его положительной заменой можно добиться неизменности другого коэффициента?

whoever

Значит, требуется найти его решение при y>0.
Значит, нужно решить уравнение ax + by = 1 при y>0, а x может быть любым.
Тогда решение такое: находим любое решение этого уравнения алгоритмом Евклида, а затем приводим y к положительному, пользуясь такой операцией (корректность которой очевидна): к y прибавить a, а от x отнять b.

нет, не получится
я ж написал, что при обоих положительных коэффициентах результат никак не может равняться 1
ну разве что числа, перед которыми коэффициенты ищутся, могут быть отрицательными?

а > b >= 0, x < 0, y > 0.
Кажется, Вы меня неверно поняли. В процессе вычисления x и y не имеется возможности использовать отрицательные числа. Каким будет в итоге x - неважно. Так вот: можно ли чем-то положительным в процессе вычисления заменять x, чтобы y остался правильным (т.е., не вычитать q*E[0][0] и q*E[1][0] из правого столбца, а прибавлять что-то другое).

Естественно, одно из x и y должно быть меньше нуля, но так как x < 0 неважен, с ним можно делать что угодно.

Это сообщение отредактировал(а) whoever - 6.4.2008, 19:25

пройди этот алгоритм до конца - найди д. потом методом подбора, увеличивая на 1 y найди подходящих х .

хм... тогда не очень понятна природа ограничения...
можно поподробнее описать его причины?
а то, обычно, если нельзя использовать отрицательные числа, значит, нет возможности их и получить...
ну разве что это ограничение для всех операций кроме последней?