Question

Which integers are divisible by 5 but leave a remainderof 1 when divided by 3?

Short answer

Answer is not given in the file.

Step-by-step solution

Step1

Given

\(\begin{array}{*{20}{c}}{x \equiv 1(\bmod 2)}\\{x \equiv 1(\bmod 3)}\end{array}\)

These equations then give us:

\(\begin{array}{*{20}{c}}{{a_1} = 1}\\{{a_2} = 1}\\{{m_1} = 2}\\{{m_2} = 3}\end{array}\)

M is then defined as the product of all \({m_i}\;s\)

\(m = {m_1} \cdot {m_2} = 2 \cdot 3 = 6\)

Next \({M_i}\) is defined as m dived by\({m_i}\)

\(\begin{array}{*{20}{c}}{{M_1} = \frac{m}{{{m_1}}} = \frac{6}{2} = 3}\\{{M_2} = \frac{m}{{{m_2}}} = \frac{6}{3} = 2}\end{array}\)

We need determine the inverse of \({m_i}\)modulo \({m_i}\)

\({M_1}\bmod {m_1} = 3\bmod 2 = 1\)

Inverse is 1 since\(1 \cdot 1\bmod 2 = 1\bmod 2 = 1\)

\({M_2}\bmod {m_2} = 2\bmod 3 = 2\)

Inverse is 2 since\(2 \cdot 2\,\bmod \,3 = 4\,\bmod \,3 = 1\)

Step2

The inverse is noted as\({y_i}\)

\(\begin{array}{*{20}{c}}{{y_1} = 1}\\{{y_2} = 2}\end{array}\)

We can then determine the solution of the system:

\(x \equiv {a_1}{M_1}{y_1} + {a_2}{M_2}{y_2}(\bmod m)\)

\(\begin{array}{l} = 1.3.1 + 1.2.2\\ = 7\\ \equiv 1(\bmod 6)\end{array}\)

Thus \(x \equiv 1(\bmod 6)\) and thus \(x = 1 + 6k\) with k an integer are all solutions of the system