Solving mod problems

Question

Can somebody run me through a step-by-step of how to solve a problem of this nature?

$3x+5\equiv 12 \mod 5$

Answer 1

$$ 3x + 5 \equiv 12 \mod 5 \\ 3x \equiv 7 \equiv 2 \mod 5 $$ Now via Euclide algorithm: $3\times 2 - 5 = 1$ so $$3\times 2 \equiv 1 \mod 5\\ 3\times 4 \equiv 2 = 3x \mod 5\\ 0 \equiv 3(x-4) \mod 5$$ and multiply by 2: $$ 0 \equiv 2\times 3(x-4) \equiv x - 4 \mod 5\\ x \equiv 4 \mod 5 $$

Answer 2

I guess the hard part is finding inverses, i.e. how to divide. Therefore, one possibility (apart from guessing, which in cases with small numbers like these is possibly the fastest) is using the euclidean algorithm: In this case find integers $a,b$ such that $$3a+5b=1.$$ Then $a$ is an inverse of 3 mod 5. Also works for non prime numbers as long as they are coprime (gcd=1).

A step by step solution for a problem of the kind $$rx+s=t\text{ mod }u$$ with gcd(u,r)=1 would then be:

Step 1: Simplify everything by substracting $s$ and "modding out" as much $u$ as possible

Step 2: Use euclidean algorithm to find modular inverse of r

Step 3: Multiply everything by this inverse

Step 4: Read off result (maybe simplify again).

Answer 3

$\!{\rm mod}\ \color{#c00}m\!:\ an\equiv ax\!+\!\overbrace{\color{#c00}my}^{\equiv\ 0}\equiv ax\!\iff\! a(x\!-\!n)\equiv 0\!\iff\!m\mid a(x\!-\!n)\!\overset{\ \color{#0a0}{(m,a)\,=\,1}}\iff\! m\mid x\!-\!n\, $ by $\rm\color{#0a0}{Euclid.}$

$\!{\rm mod}\ \color{#c00}5\!:\ 3\cdot 4\equiv 3x + \color{#c00}5\,\equiv\, 3x\!\iff\ldots$