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

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?

• If you write it in that form, you can solve it using Euclid's algorithm – Mathmo123 Dec 16 '14 at 15:50
• @Mathmo123 Could you expand on that in an answer please? – Arturo don Juan Dec 16 '14 at 15:59
• – lab bhattacharjee Dec 16 '14 at 16:04
• See the edit guys – Arturo don Juan Dec 16 '14 at 16:45

2 Answers

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

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

But

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