Find the least positive integer $x$ that satisfies the congruence $90x\equiv 41\pmod{73}$.

It is clear that an attempt to write this out as $90x-41=73n,\exists n\in \mathbb{Z}$ won't be very efficient. Is there another way of solving this problem? Could I receive a bit of guidance?

EDIT: I followed anorton's advice as follows:

To find $90^{-1}\pmod{73}$, I use the Euclidean Algorithm to find $s$ and $t$ such that $90s+73t=1$. If my calculations are correct, the values $s=-30$ and $t=37$ work.

This means that $(90)( -30)\equiv 1 \pmod{73}$.

Now if I just multiply $-30$ by $41$, I will get

$$(90)(-30)(41)\equiv 41 \pmod{73}$$

$$(90)(-1230)\equiv 41 \pmod{73} \implies x=-1230$$

But $x$ isn't positive nor the smallest possible in magnitude, so we compute $-1230\pmod{73}$, which is $11$ I believe.

Does this look alright?


Some ideas, and we do arithmetic modulo $\;73\;$ all the time:

$$-32=41=90x=17x=-56x\stackrel{\div 8}\implies 4=7x$$


$$7\cdot21=147=1\implies 7^{-1}=21\;\implies$$

$$7x=4\implies x=7^{-1}\cdot4=21\cdot4=84=11$$


The numbers are small, so we use a "playing around" approach. Rewrite our congruence as $90x\equiv 114\pmod{73}$, which is equivalent to $15x\equiv 19\pmod{73}$, But $19\equiv 165\pmod{73}$, and from $15x\equiv 165\pmod{73}$ we write down the solution $x\equiv 11\pmod{73}$.


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.