1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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 $$

$\endgroup$
0
$\begingroup$

$$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).$

$\endgroup$
0
$\begingroup$

Applying Gauss's algorithm allows us to solve it with simple mental arithmetic

$ 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.