Let integer $x$ satisfy both the following congruences:
$x ≡ a \pmod m$
$x ≡ b \pmod n$
Show that there is a solution to this system if and only if $\gcd (m, n) \mid (a− b$).
We're given $x ≡ a \pmod m$ and $x ≡ b \pmod n$, which means for some integers $p,q$
$$ x = a - pm $$
$$ x = b + qn $$
Equating, we have
$$ qn + pm = a - b $$
By Proposition (1.17) this has integer solutions for $p,q$ if and only if $gcd(n,m) \mid (a-b)$.
Show that if a polynomial $P (x)$ with integer coefficients satisfies $P (x) ≡ 0 \pmod n$ where $n = n_1 × n_2 × \ldots × n_r$ and $n_1, n_2, \ldots , n_r$ are pairwise prime integers then $P (x) ≡ 0 \pmod {n_k}$ for $k= 1, 2, 3, \ldots , r$.
We're given $P(x) \equiv 0 \pmod n$, which means $n$ divides $P(x)$. This means, for some integer $k$
$$ P(x) = k \times n $$
We're also given $n=n_1 \times n_2 \times \ldots \times n_r$, where the $n_k$ are pairwise coprime. This means
$$ \begin{align} P(x) & = k \times (n_1 \times n_2 \times \ldots \times n_k \times \ldots \times n_r) \\ \\ & = k \times \frac{(n_1 \times n_2 \times \ldots \times \cancel{n_k} \times \ldots \times n_r)}{\cancel{n_k}} \times n_k \end{align}$$
And so any $n_k$ divides $P(x)$. That is, for any $k=1,2,\ldots,r$
$$ P(x) \equiv 0 \pmod {n_k} $$
Note that we didn't use the pairwise coprimality of the $n_k$ factors of $n$.
Prove Proposition (3.24).
Proposition (3.24) is as follows.
Let $n_1, n_2, n_3, \ldots , n_r$ be positive integers which are pairwise prime. Also, integers $c_k$’s satisfy $\gcd (c_k, n_k) = 1$ for $k= 1, 2, \ldots , n$. Then the simultaneous linear congruences
$c_1 x ≡ b_1 \pmod {n_1}$
$c_2 x ≡ b_2 \pmod {n_2}$
⋮
$c_r x ≡ br \pmod {n_r}$
have a solution satisfying all these equations.
Moreover, the solution is unique modulo $n_1 × n_2 × n_3 × ⋯ × n_r$.
We're given that $\gcd(c_k, n_k)=1$ which means a linear congruence of the form $c_k x \equiv b_k \pmod {n_k}$ has a unique solution. This is Corollary (3.19), a specialisation of Proposition (3.16).
This means the simultaneous linear congruences are of the form
$ x \equiv d_1 \pmod {n_1}$
$ x \equiv d_1 \pmod {n_2}$
$\vdots$
$ x \equiv d_r \pmod {n_r}$
Since the modulii are all pair-wise corpime, then the Chinese Remainder Theorem can be used to find a unique solution modulo $n_1 \times n_2 \times \ldots \times n_r$.
(a) Let $p$ and $q$ be distinct primes such that $x ≡ M \pmod p$ and $x ≡ M \pmod q$ . Show that $x ≡ M \pmod {pq}$.
(b) Let $p_1, p_2, p_3, \ldots , p_k$ be distinct primes such that $x ≡ M \pmod {p_j}$ for $j= 1, 2, 3, \ldots , k$. Show that $x ≡ M \pmod {p_1 × p_2 × p_3 × \ldots × p_k}$.
(c) Prove that $a ≡ b \pmod {m_k} \iff a ≡ b \pmod {[m_1, m_2, \ldots , m_n]}$.
(a) We're given $x ≡ M \pmod p$ and $x ≡ M \pmod q$, which means
$$ p \mid (x - M) $$
$$ q \mid (x - M) $$
That is, $(x-M)$ is a multiple of $p$ and also a multiple of $q$.
This means $(x-M)$ is a multiple of the lowest common multiple of $p$ and $q$, denoted $[p,q]$.
$$ [p,q] \mid (x - M)$$
By Proposition (2.22) which states that $\gcd(a,b) \times [a,b] = a \times b$, and noting that $\gcd(p,q)=1$ because $p$ and $q$ are distinct primes, we have
$$ p \times q \mid (x - M) $$
which is equivalent to the statement
$$ x \equiv M \pmod {pq} $$
(b) We show this by induction on $k$.
Let statement $P(k)$ be
Let $p_1, p_2, p_3, \ldots , p_k$ be distinct primes such that $x ≡ M \pmod {p_j}$ for $j= 1, 2, 3, \ldots , k$. Then $x ≡ M \pmod {p_1 × p_2 × p_3 × \ldots × p_k}$.
We need to show both the base case $P(2)$ and the inductive step $P(k) \implies P(k+1)$.
Base Case $P(2)$
The base case $P(2)$ is
Let $p_1, p_2$ be distinct primes such that $x ≡ M \pmod {p_j}$ for $j= 1, 2$. Then $x ≡ M \pmod {p_1 × p_2}$.
We showed this in part (a), and so the base case is true.
Inductive Step $P(k) \implies P(k+1)$
We assume $P(k)$ is true as the induction hypothesis, and show $P(k+1)$ which is
Let $p_1, p_2, p_3, \ldots , p_k, p_{k+1}$ be distinct primes such that $x ≡ M \pmod {p_j}$ for $j= 1, 2, 3, \ldots , k, k+1$. Then $x ≡ M \pmod {p_1 × p_2 × p_3 × \ldots × p_k \times p_{k+1}}$.
We have
$$ \begin{align} \prod_{i=1}^k p_i & \mid (x - M) \quad \text{induction hypothesis} \\ \\ p_{k+1} & \mid (x - M) \end{align}$$
That is, $(x-M)$ is a multiple of both $ \prod_{i=1}^k p_i$ and $p_{k+1}$. This means $(x-M)$ is a multiple of the lowest common multiple of $ \prod_{i=1}^k p_i$ and $p_{k+1}$, denoted $[ \prod_{i=1}^k p_i, p_{k+1}]$.
By Proposiiton (2.22)
$$ \gcd(\prod_{i=1}^k p_i , p_{k+1}) \times [\prod_{i=1}^k p_i , p_{k+1}] = \prod_{i=1}^{k+1} p_i $$
The $p_1, p_2, \ldots, p_{k+1}$ are all prime, so $ \gcd(\prod_{i=1}^k p_i , p_{k+1}) =1$, which gives us
$$ [\prod_{i=1}^k p_i , p_{k+1}] = \prod_{i=1}^{k+1} p_i $$
That is, $(x-M)$ is a multiple of $ \prod_{i=1}^{k+1} p_i$, which is equivalent to
$$ x ≡ M \pmod {p_1 × p_2 × p_3 × \ldots × p_k \times p_{k+1}} $$
And so the inductive step is proven, $P(k) \implies P(k+1)$.
By induction we have proven the given statement.
(c) The statement
$$ a \equiv b \pmod {m_k} \iff a \equiv b \pmod {[m_1, m_2, \ldots , m_n]} $$
means, for all $k \in \{1,2, \ldots, n\}$, that $a \equiv b \pmod {m_k}$ is equivalent to $a \equiv b \pmod {[m_1, m_2, \ldots , m_n]}$.
($\impliedby$)
We assume $a \equiv b \pmod {[m_1, m_2, \ldots , m_n]}$. This means
$$ [m_1, m_2, \ldots, m_n] \mid (a-b) $$
Since by definition $ [m_1, m_2, \ldots, m_n] $ is a multiple of any one $m_k$, then we have
$$ m_k \mid [m_1, m_2, \ldots, m_n] \quad \land \quad [m_1, m_2, \ldots, m_n] \mid (a-b) $$
from which we have
$$ m_k \mid (a-b) $$
That is,
$$ a \equiv b \pmod {m_k} $$
($\implies$)
We assume $a \equiv b \pmod {m_k}$ for all $k \in \{1,2, \ldots, n\}$. This means
$$ m_k \mid (a-b) $$
That is, $(a-b)$ is a multiple of all $m_k$. Which means $(a-b)$ is a multiple of the lowest common multiple of all the $m_k$.
$$ [m_1, m_2, \ldots, m_n] \mid (a-b) $$
Which is equivalent to
$$ a \equiv b \pmod {[m_1, m_2, \ldots, m_n]} $$
We have shown both directions of the implication, and so we have shown that
$$ a \equiv b \pmod {m_k} \iff a \equiv b \pmod {[m_1, m_2, \ldots , m_n]} $$
Alternative Solution
By definition of congruence, we rewrite $a \equiv b \pmod {m_k}$ as $m_k \mid (a-b)$, which holds for all $k \in \{1,2, \ldots, n\}$.
Since $(a-b)$ is a multiple of all $m_k \in \{m_1, m_2, \ldots, m_n\}$ then $(a-b)$ is a multiple of the lowest common multiple of all the elements of $\{m_1, m_2, \ldots, m_n\}$.
$$ \forall_{k \in \{1,2, \ldots, n\}}\; a \equiv b \pmod {m_k} \quad \iff \quad \forall_{k \in \{1,2, \ldots, n\}}\; m_k \mid (a-b) \quad \iff \quad [m_1, m_2, \ldots, m_n] \mid (a-b) $$
which is equivalent to $a \equiv b \pmod {[m_1, m_2, \ldots, m_n]}$, and so we can conclude
$$ a \equiv b \pmod {m_k} \iff a \equiv b \pmod {[m_1, m_2, \ldots , m_n]} $$
Find the least positive integer $x$ which satisfies the following simultaneous equations:
$ 2x ≡ 1 \pmod 5 $
$ 3x ≡ 9 \pmod 6 $
$ 4x ≡ 1 \pmod 7 $
$ 5x ≡ 9 \pmod {11} $
We can rewrite the equations to isolate the variable $x$
$ 2x ≡ 1 \pmod 5 \iff 6x \equiv 3 \pmod 5 \iff x \equiv 3 \pmod 5$
$ 3x ≡ 9 \pmod 6 \iff 3x \equiv 3 \pmod 6 \iff x \equiv 1 \pmod {\frac{6}{\gcd(6,3)}} \iff x \equiv 1 \pmod 2 $
$ 4x ≡ 1 \pmod 7 \iff 8x \equiv 2 \pmod 7 \iff x \equiv 2 \pmod 7 $
$ 5x ≡ 9 \pmod {11} \iff 45x \equiv 81 \pmod {11} \iff x \equiv 4 \pmod {11} $
The modulii 5, 2, 7 and 11 are pair-wise coprime, and so we can use the Chinese Remainer Theorem to solve the following simultaneous linear congruences.
$ x \equiv 3 \pmod 5$
$ x \equiv 1 \pmod 2 $
$ x \equiv 2 \pmod 7 $
$ x \equiv 4 \pmod {11} $
Formula (3.23) here is
$$ x = a_1 N_1 x_1 + a_2 N_2 x_2 + a_3 N_3 x_3 + a_4 N_4 x_4 = 3(2 \times 7 \times 11)x_1 + 1(5 \times 7 \times 11)x_2 + 2(5 \times 2 \times 11)x_3 + 4(5 \times 2 \times 7)x_4 $$
where $N_k x_k \equiv 1 \pmod {n_k}$, and so
$$ \begin{align} 154 x_1 & \equiv 1 \pmod 5 \\ \\ 4 x_1 & \equiv 1 \pmod 5 \\ \\ x_1 & \equiv 4 \pmod 5 \end{align}$$
and
$$ \begin{align} 385 x_2 & \equiv 1 \pmod 2 \\ \\ x_2 & \equiv 1 \pmod 2 \end{align}$$
also
$$ \begin{align} 110 x_3 & \equiv 1 \pmod 7 \\ \\ 5 x_3 & \equiv 1 \pmod 7 \\ \\ x_3 & \equiv 3 \pmod 7 \end{align}$$
and also
$$ \begin{align} 70 x_4 & \equiv 1 \pmod {11} \\ \\ 4 x_4 & \equiv 1 \pmod {11} \\ \\ x_4 & \equiv 3 \pmod {11} \end{align}$$
This gives
$$ x = a_1 N_1 x_1 + a_2 N_2 x_2 + a_3 N_3 x_3 + a_4 N_4 x_4 = 3(2 \times 7 \times 11)4 + 1(5 \times 7 \times 11)1 + 2(5 \times 2 \times 11)3 + 4(5 \times 2 \times 7)3 = 3733 $$
The general unique solution is
$$ \begin{align} x & \equiv 3733 \pmod {5 \times 2 \times 7 \times 11} \\ \\ x & \equiv 653 \pmod {770} \end{align}$$
That is, for some integer $t$
$$ x = 653 + 770t$$
The least positive solution is $653$.
A general wanted to know how many soldiers he had in his battalion. He placed them into rows as follows:
2 left over when placed in rows of 5.
4 left over when placed in rows of 6.
1 left over when placed in rows of 7.
7 left over when placed in rows of 11.
What is the minimum number of soldiers he must have in his battalion?
The problem can formulated as finding the least non-negative solution to the following simultaneous linear congruences.
$ x \equiv 2 \pmod 5 $
$ x \equiv 4 \pmod 6 $
$ x \equiv 1 \pmod 7 $
$ x \equiv 7 \pmod {11} $
The modulii 5, 6, 7 and 11 are pair-wise coprime, and so we can use the Chinese Remainer Theorem.
Formula (3.23) here is
$$ x = a_1 N_1 x_1 + a_2 N_2 x_2 + a_3 N_3 x_3 + a_4 N_4 x_4 = 2(6 \times 7 \times 11)x_1 + 4(5 \times 7 \times 11)x_2 + 1(5 \times 6 \times 11)x_3 + 7(5 \times 6 \times 7)x_4 $$
where $N_k x_k \equiv 1 \pmod {n_k}$, and so
$$ \begin{align} 462 x_1 & \equiv 1 \pmod 5 \\ \\ 2 x_1 & \equiv 1 \pmod 5 \\ \\ x_1 & \equiv 3 \pmod 5 \end{align}$$
and
$$ \begin{align} 385 x_2 & \equiv 1 \pmod 6 \\ \\ x_2 & \equiv 1 \pmod 6 \end{align}$$
also
$$ \begin{align} 330 x_3 & \equiv 1 \pmod 7 \\ \\ x_3 & \equiv 1 \pmod 7 \end{align}$$
and also
$$ \begin{align} 210 x_4 & \equiv 1 \pmod {11} \\ \\ x_4 & \equiv 1 \pmod {11} \end{align}$$
This gives
$$ x = a_1 N_1 x_1 + a_2 N_2 x_2 + a_3 N_3 x_3 + a_4 N_4 x_4 = 2(6 \times 7 \times 11)3 + 4(5 \times 7 \times 11)1 + 1(5 \times 6 \times 11)1 + 7(5 \times 6 \times 7)1 = 6112 $$
The general unique solution is
$$ \begin{align} x & \equiv 6112 \pmod {5 \times 6 \times 7 \times 11} \\ \\ x & \equiv 1492 \pmod {2310} \end{align}$$
That is, for some integer $t$
$$ x = 1492 + 2310t$$
The least positive solution is $1492$.
Show that the following linear system has no solution:
$x ≡ 1 \pmod 2$ and $x ≡ 2 \pmod 4$.
The equivalent linear equation are, for some integers $a,b$,
$$ x = 1 + 2a, \quad x = 2 + 4b $$
Equating
$$ 2a - 4b = 1 $$
By proposition 1.17, this has integer solutions if $\gcd(2,4)=2$ divides 1, which it doesn't, and so there is no solution.