I am unsure how to solve the following problem. I was able to find similar questions, but had trouble understanding them since they did not show full solutions.
The question:
Find ALL solutions (between $1$ & $40$) to the equation $25x \equiv 10 \pmod{40}$.
Let's use the definition of congruence. $a \equiv b \pmod{n} \iff a = b + kn$ for some integer $k$. Hence, $25x \equiv 10 \pmod{40}$ means $$25x = 10 + 40k$$ for some integer $k$. Dividing each side of the equation $25x = 10 + 40k$ by $5$ yields $$5x = 2 + 8k$$
for some integer $k$. Thus,
$$5x \equiv 2 \pmod{8}$$
Since $\gcd(5, 8) = 1$, $5$ has a multiplicative inverse modulo $8$. To isolate $x$, we must multiply both sides of the congruence $5x \equiv 2 \pmod{8}$ by the multiplicative inverse of $5$ modulo $8$. To find the multiplicative inverse, we use the extended Eucldean algorithm.
\begin{align*}
8 & = 5 + 3\\
5 & = 3 + 2\\
3 & = 2 + 1\\
2 & = 2 \cdot 1
\end{align*}
Working backwards through this partial sequence of Fibonacci numbers to solve for $1$ as a linear combination of $5$ and $8$ yields
\begin{align*}
1 & = 3 - 2\\
& = 3 - (5 - 3)\\
& = 2 \cdot 3 - 5\\
& = 2(8 - 5) - 5\\
& = 2 \cdot 8 - 3 \cdot 5
\end{align*}
Therefore, $1 \equiv -3 \cdot 5 \pmod{8}$. Hence, $-3 \equiv 5^{-1} \pmod{8}$. Since $-3 \equiv 5 \pmod{8}$, we have $5 \equiv 5^{-1} \pmod{8}$. Thus, $5 \cdot 5x \equiv x \pmod{8}$. Hence,
\begin{align*}
5x & \equiv 2 \pmod{8}\\
5 \cdot 5x & \equiv 5 \cdot 2 \pmod{8}\\
x & \equiv 10 \pmod{8}\\
x & \equiv 2 \pmod{8}
\end{align*}
What remains is for you to find the solutions of the congruence $x \equiv 2 \pmod{8}$ such that $0 \leq x < 40$.
It suffices to solve the equation $25x\equiv 10\ (\ mod\ 8\ )$ because modulo $5$, the equation holds no matter what $x$ is.
This gives $x\equiv 2\ (\ mod\ 8\ )$.
I think you can easily find out the solutions now.
