1
$\begingroup$

I've been learning the Euclidean algorithm and came across this simple problem.

$101^{-1} (mod 203)$

So I attempted it as such:

$203 = 101(2) + 1$

So we got a gcd of 1, we can stop and do:

$1 = 203 - 101(2)$

And since it's mod 203, we have 101(2)

So shouldn't the answer be $2$? My textbook says it's $201$, help would be much appreciated, as this is confusing as ever.

Thanks.

$\endgroup$
  • $\begingroup$ It's $\color{red}{\boldsymbol{-}}2$, which is congruent to $201$\mod 203$. $\endgroup$ – Bernard Apr 10 '16 at 22:32
0
$\begingroup$

Observe that

$$2\cdot101=202=-1\pmod{203}\implies (101)^{-1}=-2=201\pmod{203}$$

Or using the EA:

$$203=2\cdot101+1\implies1\cdot203+\color{red}{(-2)}\cdot101=1\implies $$

$$\implies101^{-1}=-2\pmod{203}=201\pmod{203}$$

$\endgroup$
  • $\begingroup$ Is this the Euclidian algorithm, I'm not sure exactly what you're doing? $\endgroup$ – TTEd Apr 10 '16 at 22:33
  • $\begingroup$ Not needed as the value is pretty close to half the modulo, so just follow what is written there. $\endgroup$ – DonAntonio Apr 10 '16 at 22:37
0
$\begingroup$

Since $2\cdot101+1\equiv0\pmod{203}$, we have $$ 2\cdot101\equiv-1\pmod{203} $$ Multiplying by $-1$ gives $$ -2\cdot101\equiv1\pmod{203} $$ But $-2\equiv201\pmod{203}$. Therefore, $$ 201\cdot101\equiv1\pmod{203} $$ and this is exactly what $201\equiv101^{-1}\pmod{203}$ means.

$\endgroup$
  • $\begingroup$ Id really like to stick to the euclidean algorithm as I wouldn't be able to come up with this of the top of my head $\endgroup$ – TTEd Apr 10 '16 at 22:35
  • $\begingroup$ Well, you had $203\color{#C00000}{-2\cdot101}=1$ which means that $-2\cdot101\equiv1\pmod{203}$, so $-2$ is $101^{-1}$ modulo $203$. Euclid's Algorithm has already been used to get the first equation. $\endgroup$ – robjohn Apr 10 '16 at 22:39

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.