Toolkit 115

Solving Linear Congruences

9x\equiv5\pmod7\Longrightarrow x\equiv ?\pmod7

9x\equiv5\pmod7\Longrightarrow2x\equiv5\pmod7

\Longrightarrow8x\equiv20\pmod7\Longrightarrow x\equiv6\pmod7

9x\equiv5\pmod7\Longrightarrow2x\equiv-2\pmod7

\Longrightarrow x\equiv-1\pmod{\frac{7}{\gcd(7,2)}}\Longrightarrow x\equiv6\pmod7

There are infinitely many ways, but all of them try to achieve the common goal of reducing the coefficient of x.

11x\equiv3\pmod{17}\Longrightarrow x\equiv ?\pmod{17}

\times2\quad 22x\equiv6\pmod{17}\Longrightarrow5x\equiv6\pmod{17}

\times3\quad15x\equiv18\pmod{17}\Longrightarrow-2x\equiv18\pmod{17}

\div(-2)\quad x\equiv-9\equiv8\pmod{17}

11x\equiv-6x\equiv3\pmod{17}

\div(-3)\quad2x\equiv-1\equiv16\pmod{17}

\Longrightarrow x\equiv8\pmod{17}