Solve for x in $5 \equiv 128x$ (mod 59) I'm just running a blank here in review for finals and cannot seem to figure it out for the life of me. I want to say that you must use extended euclidean algorithm somehow, and I checked that the gcd(a,n)=1 where the fraction is $\frac{b}{a}$. Cant seem to get anywhere though.
 A: $5 \equiv 128x ($mod $59)$ means there exists $k \in \mathbb{Z}$ such that $128x=59k+5$. Euklidean algorithm:
$$128 = 2\cdot 59 + 10$$
$$59 = 5 \cdot 10 + 9$$
$$10 = 1 \cdot 9 + 1$$
Now you can solve those equations for the remainders $10,9$ and $1$ and substitute:
$$1 = 10 - 9 = 10 - (59-5\cdot 10)\\
=(128-2 \cdot 59) - (59 - 5 \cdot(128-2 \cdot 59))\\
=6 \cdot 128 - 13 \cdot 59$$
Now multiply by $5$ and you get:
$$5 = 30 \cdot 128 - 65 \cdot 59 \equiv 30 \cdot 128$$
So $x = 30$ is a solution.
A: A: x = 30
If x = 5 ≡ 128x(mod 59), look at 128(mod 59). It is 10, so if you multiply by 6, you will get 60, which is the congruent to 1(mod 59). Multiply that by 5, and you will get 5(mod 59). 6*5 = 30. This was done without any theorems, just patterns and common sense.
A: Hint $\displaystyle\rm\,\ mod\ 59\!:\,\ 128x\equiv 5\iff x\,\equiv\, \frac{5}{\color{#0a0}{128}}
\,\equiv\, \frac{5}{\color{#0a0}{10}}
\,\equiv\, \frac{\color{#c00}1}2
\,\equiv\, \frac{\color{#c00}{60}}{2}
\,\equiv\, 30\ \ \,  $
by $\ \begin{array}{r}\color{#c00}{1\equiv 60}\\ \color{#0A0}{128\equiv 10}\,\end{array} $
