2
$\begingroup$

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.

  • 2
    Look up the [Extended Euclidean Algorithm](http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm) and [Bezout's Identity](http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity). They are useful for solving this type of problem.2012-03-30

3 Answers 3

8

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.

  • 0
    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.2012-03-30
3

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

2

Hint $\ {\rm\ mod}\,\ 221\!:\quad\ \dfrac{1}{217}\equiv\dfrac{-220}{-4}\equiv 55$

${\rm mod}\,\ 4n\!+\!1\!:\ \ \dfrac{1}{4n\!+\!1\!-\!4}\equiv \dfrac{-4n}{-4}\equiv n\quad $ [above is case $\,n = 55$]

${\rm mod}\,\ an\!+\!1\!:\,\ \dfrac{1}{an\!+\!1\!-\!a}\equiv \dfrac{-an}{-a}\equiv n\quad $ [above is case $\,a=4$]

i.e. $\ \ \ an\!+\!1\equiv 0\,\Rightarrow\, (-a)n\equiv 1\ \Rightarrow\ n \equiv \dfrac{1}{-a\ }\equiv \dfrac{1}{-a + k(an\!+\!1)}$