Solving a congruence equation using a corollary of Fermats Little Theorem

Question

I have the congruence equation $$4x=11 \mod{19}$$ How can I solve this using $$x\equiv a^{p-2}b\mod{p} $$

Any pointers would be greatly appreciated!

Answer 1

Basically, you have $$ax \equiv 11 \mod 19 \mbox{ with } a = 4$$ and you would like to multiply this congruence with the inverse $a^{-1} \mod 19$.

Little Fermat tells you: $$a^{18} \equiv 1 \mod 19 \Rightarrow a^{-1} \equiv a^{17} \mod 19$$ But this is not necessarily the most efficient way to calculate $a^{-1} \mod 19$.

Here Will Jagy's comment comes into play: $$4\cdot 5 = 20 = 19 + 1 \Rightarrow 4^{17} \equiv 4^{-1} \equiv 5 \mod 19$$ Now you can solve your congruence $$4x \equiv 11 \mod 19 \Leftrightarrow 4^{-1}\cdot 4x \equiv 4^{-1}\cdot 11 \mod 19 \Leftrightarrow \color{blue}{x} \equiv 5\cdot 11 \color{blue}{\equiv 17 \mod 19}$$