# Solve $9x$ $\equiv 4 \mod1453$

In Underwood Dudley's Number theory book second edition chapter 5 problem 7 I encountered this problem:

Solve $9x\equiv 4 \mod1453$

I know that since $gcd(9,1453)=1$, there exists a unique solution. I found the answer in the back to be 1292 but I have no clue how to find this without doing guess and check--a method I'm sure is not very efficient here.

Does anyone know how to go about solving this? If it helps, 1453 is prime.

Thank you!

You could try the method of adding the modulus:

mod $1453$: $9x\equiv 4\equiv 1457\equiv 2910$.

At this point you can cancel $3$ (since $3$ is relatively prime to $1453$).

This gives $3x\equiv 970\pmod{1453}$.

You can now continue adding the modulus until you can cancel the remaining $3$.

• Great idea! Thank you. – candido Oct 28 '14 at 23:24

You have $9x\equiv 4 \mod1453$. Since $\gcd(9,1453) = 1$, by Bezout's theorem, we have $r,s \in \Bbb Z$ such that $9r + 1453s = 1$. Then: $$9r \equiv 1 \mod 1453.$$ Multiplying your initial congruence by $r$ wields: $$x \equiv 4r \ \mathrm{mod} \ 1453 \iff x = 4r + 1453k, \ k \in \Bbb Z.$$

The inverse modulo $1453$ can be computed with the extended Euclidean algorithm: \begin{align} 1453&=9\cdot161+4\\ 9&=4\cdot2+1 \end{align} Thus $$1=9-4\cdot2=9-(1453-9\cdot161)\cdot2=323\cdot9-1453$$ Hence $$9\cdot323\equiv 1\pmod{1453}$$ which means that $$x\equiv 323\cdot9x\equiv323\cdot4\pmod{1453}$$ or $$x\equiv1292\pmod{1453}$$