Let $\mathbb Z_5 = \mathbb Z/5\mathbb Z$.
The value of $x$ which satisfies the equation $3x = 4\bmod 5$ is...?
The answer is $3$. I understand why the answer is $3$, but not how it was derived. Is there an equation or process I can use that will give me the correct answer no matter how large the numbers in the equation?
On
Your candidates are $$0,1,2,3,,4 $$
We can check each of them to see which one satisfies the equation $$ 3x=4 \pmod 5$$
For $$x=3$$ we get $$3x =9 \equiv4 \pmod 5 $$ Other candidates do not satisfy the equation.
Thus the only answer $$ x\equiv 3\pmod 5 $$
On
Consider equations of the form $m\cdot x = n\bmod p$, where $p$ is a prime number. The other answer is a correct way to derive the solution, but it takes as many as $p$ tries to find it in the worst case. A more efficient solution is the following. First, compute $m^{-1}$, that is, the only solution $y$ to the equation $m\cdot y = 1\bmod p$. This can be done using the extended euclidean algorithm. Then, let $x:= m^{-1}\cdot n$. One can then check that $m\cdot x = mm^{-1}n \bmod p = n\bmod p$.
In case $p$ is not a prime number, one can also use this method in the case that $m$ and $p$ are coprime (which guarantees the existence of $m^{-1}$). Suppose now that $p$ and $m$ share a factor, and call it $q$. If $n$ is not divisible by $q$, then there is no solution (you can prove this using arithmetic modulo $q$). If $q$ also divides $n$, then the equation reduces to $\frac{m}{q}\cdot x = \frac{n}{q}\bmod \frac{p}{q}$. You can now continue this process, until you find a solution.
You need to find the inverse of $3$ modulo $5$. By Bézout’s identity, there are integers $x$ and $y$ such that $3x+5y=1$, which you can find with the (reverse) Euclidean algorithm: \begin{align} \color{red}{5}&=\color{red}{3}\cdot1+\color{red}{2}\\ \color{red}{3}&=\color{red}{2}\cdot1+\color{red}{1}\\ \color{red}{2}&=\color{red}{1}\cdot2+0 \end{align} The reverse algorithm gives \begin{align} \color{red}{1}&=\color{red}{3}+\color{red}{2}\cdot(-1)\\ &=\color{red}{3}+(\color{red}{5}+\color{red}{3}\cdot(-1))\cdot(-1)\\ &=\color{red}{3}\cdot(1+1)+\color{red}{5}\cdot(-1)\\ &=\color{red}{3}\cdot2+\color{red}{5}\cdot(-1) \end{align} which shows we can choose $x=2$ and $y=-1$. Since $3\cdot2+5\cdot(-1)=1$, we have $$ 2\cdot3\equiv 1\pmod{5} $$ and so $$ 2\cdot3x\equiv2\cdot4\pmod{5} $$ which gives $$ x\equiv3\pmod{5} $$ Of course, for congruences modulo $5$ it's much easier to do trial and error, that is, trying $3\cdot m$ for $m=1,2,3,4$ and stop when the hit is found.
On the other hand, the above method will work for every problem of the form $$ ax\equiv b\pmod{n} $$ where $\gcd(a,n)=1$.