Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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

3 Answers 3

up vote 7 down vote accepted

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.

share|improve this answer
    
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}$.

share|improve this answer

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 $

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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