What are the integral solutions of $239x-111y=1$

Question

What are the integral solutions of $239x-111y=1$

My Try:

$239x-111y=1$

$239x\equiv(1$ mod $111)$

$17x\equiv(13$ mod $111)$

$17(13x)\equiv(13$ mod $111)$

$x\equiv(98$ mod $11)$

So, $x=98$

Is my above attempt correct? Are there any better ways to solve this?

Answer 1

You did find a solution, but the part you're missing is that there are infinitely many such solutions. This is a linear Diophantine equation of two variables, and there's some good information on Wikipedia about this. The most important part is:

$$ax+by= c,\quad \text{(all integers)}$$ [The above equation] has a solution (where $x$ and $y$ are integers) if and only if $c$ is a multiple of the greatest common divisor of $a$ and $b$. Moreover, if $(x, y)$ is a solution, then the other solutions have the form $(x + kv, y − ku)$, where $k$ is an arbitrary integer, and $u$ and $v$ are the quotients of $a$ and $b$ (respectively) by the greatest common divisor of $a$ and $b$.

So, given a single solution, you can find all other solutions to the equation. The usual approach is to use Euclid's algorithm to find $x$ and $y$ such that $\gcd(a, b) = a\cdot x + b\cdot y$, then scale appropriately (i.e. multiply the whole equation by $\frac{c}{\gcd(a, b)}$.

However, you've already found a solution, so let's skip that part. Once you have a single solution $(x_0, y_0)$, you need to describe the solution set. This is:

\begin{equation} \left\{\left(x_0 + \frac{bn}{d}, y_0 + \frac{an}{d}\right) : n \in \mathbb{Z}, d = \gcd(a, b)\right\} \end{equation}

For your case, $a$ and $b$ are coprime, so $d=1$.

Answer 2

Similar to above, but names some important ideas.

The GCD of any two integers can be expressed as a linear combination if those integers, and that in infinite ways.

239 and 111 are relatively prime. The Extended Euclidean Algorithm can be used to find those infinite solutions.