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?
Best Answer
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}$.