Question

Let$f:\mathbb{Z}\to {\mathbb{Z}}_3\times {\mathbb{Z}}_4\times {\mathbb{Z}}_5$be given by$f\left(t\right)=({\left[t\right]}_3,{\left[t\right]}_4,{\left[t\right]}_5)$,where${\left[t\right]}_n$is the congruence class of$t$in${\mathbb{Z}}_n$.The function$f$may be thought of as representing t as an element ofrole="math" localid="1658833286608" ${\mathbb{Z}}_3\times {\mathbb{Z}}_4\times {\mathbb{Z}}_5$by taking its least residues.

1. If$0\le r,s<60$, prove thatif and only if$r=s$. [Hint: Theorem 14.2.]
2. Give an example to show that if$r$or$s$is greater than 60, then part (a) may be false.

Short answer

(a) It is proved that $f\left(r\right)=f\left(s\right)$if and only if $r=s$.

(b) It is proved that if $r\text{or}s$is greater than 60, then part (a) may be false.

Step-by-step solution

Theorem 14.2

According to theorem, let$m_1,m_2,,...,m_r$be pairwise relatively prime positive integers (meaning that$(m_i,m_j)=1$ whenever$i\ne j$). Let$a_1,a_2,,...,a_r$be any integers.

1. The system has a solution.

$\begin{array}{l}x\equiv a_1\left(\text{mod}{m}_1\right)\\ x\equiv a_2\left(\text{mod}{m}_2\right)\\ x\equiv a_3\left(\text{mod}{m}_3\right)\\ .\\ .\\ x\equiv a_r\left(\text{mod}{m}_r\right)\end{array}$

Has a solution.

1. If$t$is one solution of the system, then an integer$z$is also a solution if and only if$z\equiv t(\text{mod}{m}_1{m}_2...m_r)$.

Proving that f(r)=f(s)if and only if r=s

(a)

Implies part:

Suppose that for$r,s\in [0,60)$such that$f\left(r\right)=f\left(s\right)$

Since, 3, 4 and 5 are pairwise relatively prime positive integers.

So, we can apply theorem 14.2 and conclude that both$r\text{and}s$are solution of the system.

$\begin{array}{l}x\equiv r\left(\text{mod3}\right)\\ x\equiv r\left(\text{mod4}\right)\\ x\equiv r\left(\text{mod5}\right)\end{array}$

Now, from Theorem 14.2(2) we can see that if$r\text{and}s$are two solution of the system then it must satisfy,

$\begin{array}{c}r\equiv s(\text{mod3}\cdot \text{4}\cdot 5)\\ \equiv s\left(\text{mod60}\right)\end{array}$

Since,$r,s\in [0,60)$

We can conclude that .$r=s$

Converse part:

Now, suppose that $r=s$are integers.

So, we can write,

$\begin{array}{l}{\left[r\right]}_3={\left[s\right]}_3\\ {\left[r\right]}_4={\left[s\right]}_4\\ {\left[r\right]}_5={\left[s\right]}_5\end{array}$

Therefore, $f\left(r\right)=f\left(s\right)$.

Hence proved.

Showing that if ror s is greater than 60, then part (a) may be false

(b)

From the Chinese Reminder Theorem we know that the solution of the system:

$\begin{array}{l}x\equiv 1\left(\text{mod3}\right)\\ x\equiv 1\left(\text{mod4}\right)\\ x\equiv 1\left(\text{mod5}\right)\end{array}$

Now, let .$x\equiv 58\left(\text{mod60}\right)$

So, if we take$r=58,s=118$

We will get$f\left(r\right)=f\left(s\right)=(1,2,3)$

Here $f\left(r\right)=f\left(s\right)$, but $r\ne s$

So, Part (a) is false.

Hence proved.