Time for Computers to Take Over

This is not a complete solution. The following is the program to solve this problem.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

from math import floor
from math import ceil

def bezout(a, b):
    q = (floor(a / b) if b > 0 else ceil(a / b))
    r = a - b * q
    if b % r == 0:
        return (1, -q)
    else:
        x, y = bezout(b, r)
        return (y, x - q * y)

a, b = 233987973, 41111687
x, y = bezout(a, b)
print(x % b + y % a)

We can see, that equation in the statement has the next form:

$a \cdot x + b \cdot y = gcd(a, b)$ (Bezout's identity)

To solve it we can use extended Euclidean algorithm. Using such algorithm we can found only one solution, but this equation has infinite amount of solutions. All solutions we can found in this way:

Let's suppose that the numbers $x_0$ and $y_0$ are a solution for our equation. We can found all solutions using such formula:

$\cases{ x = x_0 + k \cdot \frac{b}{g}, \cr y = y_0 - k \cdot \frac{a}{g}, }$ where $g = gcd(a, b)$ and $k \in \mathbb{Z}$ .

For this statement all solutions can be found as following:

$\cases{ x = x_0 + k \cdot b, \cr y = y_0 - k \cdot a, }$

And finally, we need to understand, that:

$\cases{ x \equiv x_0 \pmod{b}, \cr y \equiv y_0 \pmod{a} }$

This is programmatic solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

# Extended Euclidean algorithm
def solve(a, b):
    if a == 0:
        return 0, 1
    x, y = solve(b % a, a)
    return y - b // a * x, x

a, b = 233987973, 41111687
x, y = solve(a, b)
print(x % b + y % a)