# Find integers x and y with 103x + 113y=1

Find integers $x$ and $y$ with $103x + 113y=1$

How would you solve this problem? I'm thinking maybe you can use Euclidean Algorithm to solve for the inverse?

We can use the Extended Euclidean Algorithm. One implementation is the Euclid-Wallis Algorithm: $$\begin{array}{r} &&1&10&3&3\\\hline 1&0&1&-10&31&-103\\ 0&1&-1&11&-34&113\\ 113&103&10&3&1&0\\ &&&&{\uparrow} \end{array}$$ The column with the arrow says that $$31\cdot113-34\cdot103=1$$
$$113y≡1(mod103)$$ $$10y≡1(mod103)$$ $$10y≡1+309(mod103)$$ $$y≡31(mod103)$$ Hence $y≡31(mod103).$
It is easy to show that $x≡-34(mod113).$
$103x\!+\!113y=1\$ $\Rightarrow$ $\ {\rm mod}\ 103\!:\,\ y\equiv \dfrac{1}{113}\equiv\dfrac{1}{10}\equiv\dfrac{10}{100}\equiv\dfrac{10}{-3}\equiv\dfrac{-93}{-3}\equiv 31$
Beware $\$ Modular fraction arithmetic is well-defined only for fractions with denominator coprime to the modulus. See here for further discussion.