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

DEFINITION

a divides b if there exists an integer c such that b=ac

Notation:\(a|b\)

Quotient- Reminder theorem

Let n an integer and d a positive integer

Then there are unique integer q and r with \(0 \le r < d\) such that \(n = dq + r\).

Q is called the quotient and r is called the remainder

\(\begin{array}{l}q = n div d\\r = n mod d\end{array}\)

Step 2

Let x be an integer that is divisible by 5, while x also leaves a remainder of 1

When x is divided by 3.

\(\begin{array}{l}x \equiv 0(mod 5)\\x \equiv 1(mod 3)\end{array}\)

I will use the construction in the proof of the Chinese remainder theorem to find all the solution to the system of congruences. These equations then give us:

\(\begin{array}{*{20}{r}}{{a_1} = 0}\\{{a_2} = 1}\\{{m_1} = 5}\\{{m_2} = 3}\end{array}\)

m is defined as the product of all \({m_i}\;'s\)

\(m = {m_1} \cdot {m_2} = 5 \cdot 3 = 15\)

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

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

Step 3

We need determine the inverses of \(\;{M_i}\) modulo \({m_i}\)

\({M_1}\bmod {m_1} = 3\bmod 5 = 3\)

\(Inverse is\;2\;since\;3 \cdot 2\bmod 3 = 6\bmod 5 = 1\)

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

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

The inverses are notated as

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

We can determine the solution of the system:

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

\(\begin{array}{l} \equiv 0.3.2 + 1.5.2\\ \equiv 10\\ \equiv 10(\bmod 15)\end{array}\)

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