2
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Great idea! Thank you. $\endgroup$ – candido Oct 28 '14 at 23:24
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.