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

Question

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!

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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