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.

$9x \equiv 3 \pmod {23}$

How to derive the smallest $x$. I understand I can use the extended euclidean algorithm for eg $19x = 1 \pmod {35}$.

However, I not too sure how to work on it when it is $3 \pmod {23}$.

I am able to reach the step of $1 = -5(9) + 2(23$) after going thru the euclidean algorithm.

share|improve this question
3  
As $3$ is relatively prime to $23$, $9x\equiv 3\iff 3x\equiv 1$. Guessing shows that $23+1=24=3\cdot 8$ is a multiple of $3$. Indeed, $9\cdot 8=72=3\cdot 23+3$. –  Hagen von Eitzen Mar 10 '13 at 12:01

4 Answers 4

Ah, great, but this already means that $-5$ is the multiplicative inverse of $9$ modulo $23$, as $(-5)\cdot 9\equiv 1 \pmod{23}$. So you have $$x\equiv (-5)\cdot 9x\equiv (-5)\cdot 3=-15\equiv 8 \pmod{23}$$ Among these, $8$ is the smallest positive number.

share|improve this answer

As you computed, $9(-5)\equiv 1\pmod {23}\implies 9(-5)3\equiv 3\pmod {23}\implies 9(-15)\equiv 3\pmod{23}$ $\implies 9(8)\equiv3\pmod{23}$

share|improve this answer

Hint $\rm\,\ mod\ 23\!:\,\ 9x\equiv 3\iff x\equiv \dfrac{3}{9}\equiv \dfrac{1}3\equiv \dfrac{8}{24}\equiv \dfrac{8}1$

Remark $\ $ We used Gauss's algorithm for computing inverses $\rm\:mod\ p\:$ prime.

Beware $\ $ One can employ fractions $\rm\ x\equiv b/a\ $ in modular arithmetic (as above) only when the fractions have denominator $ $ coprime $ $ to the modulus $ $ (else the fraction may not uniquely exist, $ $ i.e. the equation $\rm\: ax\equiv b\,\ (mod\ m)\:$ might have no solutions, or more than one solution). The reason why such fraction arithmetic works here (and in analogous contexts) will become clearer when one learns about the universal properties of fraction rings (localizations).

share|improve this answer

$ _{_{_{x}}}$

(This is certainly a smaller $x$ than any other solution has)

(From reading "Littlewood's Miscellany" - highly recommended)

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.