Ага, что-то я погорячился, надо было чуть-чуть подумать, зато теперь я всё строго доказал! Для потомков изложу доказательство тут:
Утверждение: пусть x, y - результат работы расширенного алгоритма Евклида для неотрицательных чисел a, b. Тогда |x| ≤ b, |y| ≤ a.
Доказательство: по индукции. База - (a = 0 к сожалению не подходит) b делится на a, x = 1, y = 0, b ≠ 0, поэтому всё в порядке.
Переход - пусть из пары (b, bq + a) (a < b, q ≥ 0) мы попали в пару (a, b), для которой результат - (x, y). Тогда для первой пары результат будет (y-qx, x). Оценим: |y-qx| ≤ |y| + |qx| ≤ a + qb, |x| ≤ b(в неравенствах мы применяем предположения индукции), получили требуемое.
Но вообще изначально я создал тему вот из-за чего: надо было решить уравнение Ax+By=C, где A, B и C от 0 до 10^18. Пусть для простоты gcd(A, B) = 1, тогда для этого мы находим корень (x0, y0) уравнения Ax+By=1, и все решения нашего уравнения выглядят так: (C * x0 + B * n, C * y0 - A * n), n ∈ Z. Проблема - С * x0 теперь до 10^36, а тем не менее мне почему-то кажется, что всегда должен быть корень, влезающий в 64-битный тип.
Короче говоря вопрос, можно ли решить такую задачу без использования длинной арифметики?