Step 1

Given a system of linear congruences

\(\displaystyle{x}+{2}{y}\equiv{1}{\left(\text{mod}{5}\right)}\)

\(\displaystyle{2}{x}+{y}\equiv{1}{\left(\text{mod}{5}\right)}\)

Solve it.

Step 2

Multiply the first congruence by 2.

\(\displaystyle{2}{x}+{4}{y}\equiv{2}{\left(\text{mod}{5}\right)}\)

Add the preceding one with the second congruence in the system.

\(\displaystyle{4}{x}+{5}{y}\equiv{3}{\left(\text{mod}{5}\right)}\)

\(\displaystyle\Rightarrow{4}{x}\equiv{3}{\left(\text{mod}{5}\right)}\)

Step 3

Multiply the congruence by \(\displaystyle{4}^{{-{1}}}{\left(\text{mod}{5}\right)}={4}\) to get

\(\displaystyle{16}{x}\equiv{12}{\left(\text{mod}{5}\right)}\)

\(\displaystyle\Rightarrow{x}\equiv{2}{\left(\text{mod}{5}\right)}\)

Step 4

Plugging back in x for the second equation.

\(\displaystyle{4}+{y}\equiv{1}{\left(\text{mod}{5}\right)}\)

\(\displaystyle\Rightarrow{y}\equiv-{3}{\left(\text{mod}{5}\right)}{\quad\text{or}\quad}{y}\equiv{2}{\left(\text{mod}{5}\right)}\)

Thus the solution of the system of congruences is

\(\displaystyle{x}\equiv{2}{\left(\text{mod}{5}\right)},{y}\equiv{2}{\left(\text{mod}{5}\right)}\)

Given a system of linear congruences

\(\displaystyle{x}+{2}{y}\equiv{1}{\left(\text{mod}{5}\right)}\)

\(\displaystyle{2}{x}+{y}\equiv{1}{\left(\text{mod}{5}\right)}\)

Solve it.

Step 2

Multiply the first congruence by 2.

\(\displaystyle{2}{x}+{4}{y}\equiv{2}{\left(\text{mod}{5}\right)}\)

Add the preceding one with the second congruence in the system.

\(\displaystyle{4}{x}+{5}{y}\equiv{3}{\left(\text{mod}{5}\right)}\)

\(\displaystyle\Rightarrow{4}{x}\equiv{3}{\left(\text{mod}{5}\right)}\)

Step 3

Multiply the congruence by \(\displaystyle{4}^{{-{1}}}{\left(\text{mod}{5}\right)}={4}\) to get

\(\displaystyle{16}{x}\equiv{12}{\left(\text{mod}{5}\right)}\)

\(\displaystyle\Rightarrow{x}\equiv{2}{\left(\text{mod}{5}\right)}\)

Step 4

Plugging back in x for the second equation.

\(\displaystyle{4}+{y}\equiv{1}{\left(\text{mod}{5}\right)}\)

\(\displaystyle\Rightarrow{y}\equiv-{3}{\left(\text{mod}{5}\right)}{\quad\text{or}\quad}{y}\equiv{2}{\left(\text{mod}{5}\right)}\)

Thus the solution of the system of congruences is

\(\displaystyle{x}\equiv{2}{\left(\text{mod}{5}\right)},{y}\equiv{2}{\left(\text{mod}{5}\right)}\)