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!
 A: 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$.
A: 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. $$
A: 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}
$$
A: Since the OP threw out the 'guess-and-check' approach, we start by examining
$\quad 9x = 4 + 1453k \quad k \ge 1$
and try $k = 1$.
Applying Euclidean division,
$\quad 1457 = 9 \cdot 161 + 8$
allowing us write a truth chain of equivalent statements,
$\quad 4 \equiv 9 \cdot 161 + 8 \pmod{1453} \quad \text{iff }$
$\; -4 \equiv 9 \cdot 161 \pmod{1453} \quad \quad \;\, \text{ iff }$
$\quad 4 \equiv 9 \cdot (-161) \pmod{1453} \quad \, \text{iff }$
$\quad 4 \equiv 9 \cdot 1292\pmod{1453}$
and we have a solution, $x \equiv 1292\pmod{1453}$.
