# Find the smallest $x$ for $9x \equiv 3 \pmod {23}$

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

-
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

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.

-

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

-

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).

-

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

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

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

-