# Solving $217 x \equiv 1 \quad \text{(mod 221)}$

I am given the problem:

Find an integer $x$ between $0$ and $221$ such that $$217 x \equiv 1 \quad \text{(mod 221)}$$

How do I solve this? Unfortunately I am lost.

-
Look up the Extended Euclidean Algorithm and Bezout's Identity. They are useful for solving this type of problem. – robjohn Mar 30 '12 at 17:22

In this special case, you can multiply the congruence by $-1$ and you'll get $$4x\equiv 220 \pmod{221}.$$ (Just notice that $-217 \equiv 4 \pmod{221}$ and $-1\equiv220\pmod{221}$.)

This implies that $x\equiv 55 \pmod{221}$ is a solution. (And since $\gcd(4,221)=1$, there is only one solution modulo $221$.)

In general, for questions of this type you can use extended Euclidean algorithm see Wikipedia.

You can find some examples at this site, e.g. here.

-
can you elaborate on we get from multiplying by -1, to $4x \equiv 220 \text{(mod 221)}$? I see the parenthesis, but can say that more explicitly? having a little trouble following – Dominick Gerard Mar 30 '12 at 15:20
$-217$ and $4$ are congruent modulo $221$, hence we can replace $-217$ by $4$ without changing the validity of the congruence relation. The same is true for $-1$ and $220$. – Martin Sleziak Mar 30 '12 at 15:23
perfect, thank you – Dominick Gerard Mar 30 '12 at 15:26
Although in this case we were able to make a guess which made finding the solution easy, it is useful to learn a method how to do this in general. – Martin Sleziak Mar 30 '12 at 15:32

Using the Euclid-Wallis Algorithm: $$\begin{array}{r} &&1&54&4\\ \hline \color{red}{1}&0&1&\color{red}{-54}&217\\ 0&\color{green}{1}&-1&\color{green}{55}&-221\\ \color{red}{221}&\color{green}{217}&4&\color{blue}{1}&0 \end{array}$$ we get that $\color{green}{55\cdot217}\color{red}{-54\cdot221}=\color{blue}{1}$. Thus, $x=55\pmod{221}$.

-

Hint $\rm\ mod\ 221\!:\ \dfrac{1}{217}\:\equiv\: \dfrac{1}{-4}\:\equiv\: - \left(\dfrac{1}{2}\right)^2 \equiv\: -(111)^2,\$ or $\ \dfrac{1}{217}\:\equiv\dfrac{1}{-4} \:\equiv\: \dfrac{-1}{4} \:\equiv\: \dfrac{220}4 \:\equiv\: 55$

$\rm\ mod\ 2n-1\!:\ \dfrac{1}{2n-5}\:\equiv\: \dfrac{1}{-4}\:\equiv\: - \left(\dfrac{1}{2}\right)^2 \equiv\: -n^2$

-