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.
Find the least positive integer which leaves remainder 1 when divided by 5, remainder 2 when divided by 7, remainder 3 when divided by 9, and remainder 4 when divided by 11.
The problem can be formulated as solving the following simultaneous linear congruences.
$ x \equiv 1 \pmod 5 $
$ x \equiv 2 \pmod 7 $
$ x \equiv 3 \pmod 9 $
$ x \equiv 4 \pmod {11} $
The modulii 5, 7, 9 and 11 are coprime, so we can use the Chinese Remainder 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 = 1(7 \times 9 \times 11)x_1 + 2(5 \times 9 \times 11)x_2 + 3(5 \times 7 \times 11)x_3 + 4(5 \times 7 \times 9)x_4 $$
where $N_k x_k \equiv 1 \pmod {n_k}$, and so
$$ \begin{align} 693 x_1 & \equiv 1 \pmod 5 \\ \\ 3 x_1 & \equiv 1 \pmod 5 \\ \\ x_1 & \equiv 2 \pmod 5 \end{align}$$
and
$$ \begin{align} 495 x_2 & \equiv 1 \pmod 7 \\ \\ 5 x_2 & \equiv 1 \pmod 7 \\ \\ x_2 & \equiv 3 \pmod 7 \end{align}$$
also
$$ \begin{align} 385 x_3 & \equiv 1 \pmod 9 \\ \\ 7 x_3 & \equiv 1 \pmod 9 \\ \\ x_3 & \equiv 4 \pmod 9 \end{align}$$
and also
$$ \begin{align} 315 x_4 & \equiv 1 \pmod {11} \\ \\ 7 x_4 & \equiv 1 \pmod {11} \\ \\ x_4 & \equiv 8 \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 = 1(7 \times 9 \times 11)2 + 2(5 \times 9 \times 11)3 + 3(5 \times 7 \times 11)4 + 4(5 \times 7 \times 9)8 = 19056$$
The general unique solution is
$$ \begin{align} x & \equiv 19056 \pmod {5 \times 7 \times 9 \times 11} \\ \\ x & \equiv 1731 \pmod {3465} \end{align}$$
That is, for some integer $t$
$$ x = 1731 + 3465t$$
The least positive solution is $x=1731$.
Find the least positive integer which leaves remainder 2 when divided by 7, remainder 3 when divided by 9, and remainder 6 when divided by 11.
The problem can be formulated as solving the following simultaneous linear congruencies
$ x \equiv 2 \pmod 7 $
$ x \equiv 3 \pmod 9 $
$ x \equiv 6 \pmod {11} $
The modulii 7, 9 and 11 are coprime, so we can use the Chinese Remainder 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 = 2(9 \times 11)x_1 + 3(7 \times 11)x_2 + 6(7 \times 9)x_3 $$
where $N_k x_k \equiv 1 \pmod {n_k}$, and so
$$ \begin{align} 99 x_1 & \equiv 1 \pmod 7 \\ \\ x_1 & \equiv 1 \pmod 7 \end{align}$$
and
$$ \begin{align} 77 x_2 & \equiv 1 \pmod 9 \\ \\ 5 x_2 & \equiv 1 \pmod 9 \\ \\ x_2 & \equiv 2 \pmod 9 \end{align}$$
also
$$ \begin{align} 63 x_3 & \equiv 1 \pmod {11} \\ \\ 8 x_3 & \equiv 1 \pmod {11} \\ \\ x_3 & \equiv 7 \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 = 2(9 \times 11)1 + 3(7 \times 11)2 + 6(7 \times 9)7 = 3306 $$
The general unique solution is
$$ \begin{align} x & \equiv 3306 \pmod {7 \times 9 \times 11} \\ \\ x & \equiv 534 \pmod {693} \end{align}$$
That is, for some integer $t$
$$ x = 534 + 693t$$
The least positive solution is $x=534$.
Solve the following simultaneous equations. Write down the general solution and the least positive integer which satisfies these equations:
(a) $2x ≡ 1 \pmod 3$, $5x ≡ 2 \pmod 7$
(b) $2x ≡ 1 \pmod {13}$, $3x ≡ 2 \pmod {19}$
(c) $3x ≡ 5 \pmod 7$, $5x ≡ 2 \pmod {11}$, $9x ≡ 1 \pmod {5}$
(d) $x ≡ 3 \pmod 7$, $x ≡ 9 \pmod {11}$
(a) We rewrite the equations to isolate the variable $x$
$ 2x \equiv 1 \pmod 3 \iff 4x \equiv 2 \pmod 3 \iff x \equiv 2 \pmod 3 $
$ 5x \equiv 2 \pmod 7 \iff 15x \equiv 6 \pmod 7 \iff x \equiv 6 \pmod 7$
The modulii 3 and 7 are indeed pair-wise coprime, so we can use the Chinese Remainder Theorem to solve
$x ≡ 2 \pmod 3 $
$x ≡ 6 \pmod 7$
Formula (3.23) here is
$$ x = a_1 N_1 x_1 + a_2 N_2 x_2 = 2(7)x_1 + 6(3)x_2$$
where $N_k x_k \equiv 1 \pmod {n_k}$, and so
$$ \begin{align} 7 x_1 & \equiv 1 \pmod 3 \\ \\ x_1 & \equiv 1 \pmod 3 \end{align}$$
and
$$ \begin{align} 3 x_2 & \equiv 1 \pmod 7 \\ \\ x_2 & \equiv 5 \pmod 7 \end{align}$$
which gives
$$ x = a_1 N_1 x_1 + a_2 N_2 x_2 = 2(7)1 + 6(3)5 = 104$$
The general unique solution is
$$ \begin{align} x & \equiv 104 \pmod {3 \times 7} \\ \\ x & \equiv 20 \pmod {21} \end{align}$$
That is, for some integer $t$
$$ x = 20 + 21t$$
The least positive solution is $x=20$.
(b) We rewrite the equations to isolate the variable $x$
$ 2x \equiv 1 \pmod {13} \iff 14x \equiv 7 \pmod {13} \iff x \equiv 7 \pmod {13} $
$ 3x \equiv 2 \pmod {19} \iff 39x \equiv 26 \pmod {19} \iff x \equiv 7 \pmod {19} $
The modulii 13 and 19 are indeed pair-wise coprime, so we can use the Chinese Remainder Theorem to solve
$ x \equiv 7 \pmod {13} $
$ x \equiv 7 \pmod {19} $
Formula (3.23) here is
$$ x = a_1 N_1 x_1 + a_2 N_2 x_2 = 7(19)x_1 + 7(13)x_2$$
where $N_k x_k \equiv 1 \pmod {n_k}$, and so
$$ \begin{align} 19 x_1 & \equiv 1 \pmod {13} \\ \\ 6 x_1 & \equiv 1 \pmod {13} \\ \\ x_1 & \equiv 11 \pmod {13} \end{align}$$
and
$$ \begin{align} 13 x_2 & \equiv 1 \pmod {19} \\ \\ x_2 & \equiv 3 \pmod {19} \end{align}$$
which gives
$$ x = a_1 N_1 x_1 + a_2 N_2 x_2 = 7(19)11 + 7(13)3 = 1736$$
The general solution is
$$ \begin{align} x & \equiv 1736 \pmod {13 \times 19} \\ \\ x & \equiv 7 \pmod {247} \end{align}$$
That is, for some integer $t$
$$ x = 7 + 247t$$
The least positive solution is $x=7$.
(c) We rewrite the equations to isolate the variable $x$
$ 3x \equiv 5 \pmod 7 \iff 15x \equiv 25 \pmod 7 \iff x \equiv 4 \pmod 7 $
$ 5x \equiv 2 \pmod {11} \iff 45x \equiv 18 \pmod {11} \iff x \equiv 7 \pmod {11} $
$ 9x \equiv 1 \pmod {5} \iff 4x \equiv 1 \pmod 5 \iff 16x \equiv 4 \pmod 5 \iff x \equiv 4 \pmod 5$
The modulii 7, 11 and 5 are indeed pair-wise coprime, so we can use the Chinese Remainder Theorem to solve.
$ x \equiv 4 \pmod 7 $
$ x \equiv 7 \pmod {11} $
$ x \equiv 4 \pmod 5$
Formula (3.23) here is
$$ x = a_1 N_1 x_1 + a_2 N_2 x_2 + a_3 N_3 x_3 = 4(11 \times 5)x_1 + 7(7 \times 5)x_2 + 4(7 \times 11)x_3$$
where $N_k x_k \equiv 1 \pmod {n_k}$, and so
$$ \begin{align} 55 x_1 & \equiv 1 \pmod 7 \\ \\ 6 x_1 & \equiv 1 \pmod 7 \\ \\ x_1 & \equiv 6 \pmod 7 \end{align}$$
and
$$ \begin{align} 35 x_2 & \equiv 1 \pmod {11} \\ \\ 2 x_2 & \equiv 1 \pmod {11} \\ \\ x_2 & \equiv 6 \pmod {11} \end{align}$$
also
$$ \begin{align} 77 x_3 & \equiv 1 \pmod 5\\ \\ 2 x_3 & \equiv 1 \pmod 5 \\ \\ x_3 & \equiv 3 \pmod 5 \end{align}$$
which gives
$$ x = a_1 N_1 x_1 + a_2 N_2 x_2 + a_3 N_3 x_3 = 4(11 \times 5)6 + 7(7 \times 5)6 + 4(7 \times 11)3 = 3714 $$
The general solution is
$$ \begin{align} x & \equiv 3714 \pmod {7 \times 11 \times 5} \\ \\ x & \equiv 249 \pmod {385} \end{align}$$
That is, for some integer $t$
$$ x = 249 + 385t$$
The least positive solution is $x=249$.
(d) The modulii 7 and 11 are pair-wise coprime, so we can use the Chinese Remainder Theorem to solve
$x ≡ 3 \pmod 7$
$x ≡ 9 \pmod {11}$
Formula (3.23) here is
$$ x = a_1 N_1 x_1 + a_2 N_2 x_2 = 3(11)x_1 + 9(7)x_2$$
where $N_k x_k \equiv 1 \pmod {n_k}$, and so
$$ \begin{align} 11 x_1 & \equiv 1 \pmod {7} \\ \\ 4 x_1 & \equiv 1 \pmod 7 \\ \\ x_1 & \equiv 2 \pmod 7 \end{align}$$
and
$$ \begin{align} 7 x_2 & \equiv 1 \pmod {11} \\ \\ x_2 & \equiv 8 \pmod {11} \end{align}$$
which gives
$$ x = a_1 N_1 x_1 + a_2 N_2 x_2 = 3(11)2 + 9(7)8 = 570$$
The general solution is
$$ \begin{align} x & \equiv 570 \pmod {7 \times 11} \\ \\ x & \equiv 31 \pmod {77} \end{align}$$
That is, for some integer $t$
$$ x = 31 + 77t$$
The least positive solution is $x=31$.
Solve the following simultaneous equations:
(a) $x ≡ 5 \pmod 7 $, $x ≡ 4 \pmod {11}$
(b) $x ≡ 0 \pmod 5$, $x ≡ 0 \pmod 6$
(c) $x ≡ 3 \pmod 8$, $x ≡ 5 \pmod {13}$
(d) $x ≡ 1 \pmod 3$, $x ≡ 2 \pmod 5$, $x ≡ 3 \pmod 7$
(e) $x ≡ 1 \pmod 5$, $x ≡ 3 \pmod 7$, $x ≡ 5 \pmod {11}$
(a) The modulii 7 and 11 are indeed pair-wise coprime, so we can use the Chinese Remainder Theorem to solve
$x ≡ 5 \pmod 7 $
$x ≡ 4 \pmod {11}$
Formula (3.23) here is
$$ x = a_1 N_1 x_1 + a_2 N_2 x_2 = 5(11)x_1 + 4(7)x_2$$
where $N_k x_k \equiv 1 \pmod {n_k}$, and so
$$ \begin{align} 11 x_1 & \equiv 1 \pmod 7 \\ \\ 4 x_1 & \equiv 1 \pmod 7 \\ \\ x_1 & \equiv 2 \pmod 7 \end{align}$$
and
$$ \begin{align} 7 x_2 & \equiv 1 \pmod {11} \\ \\ x_2 & \equiv 8 \pmod {11} \end{align}$$
which gives
$$ x = a_1N_1x_1 + a_2N_2x_2 = 5(11)2 + 4(7)8 = 334 $$
The general unique solution is
$$ \begin{align} x & \equiv 334 \pmod {7 \times 11} \\ \\ x & \equiv 26 \pmod {77} \end{align}$$
(b) The modulii 5 and 6 are indeed pair-wise coprime., so we can use the Chinese Remainder Theorem to solve
$x ≡ 0 \pmod 5$
$x ≡ 0 \pmod 6$
Formula (3.23) here is
$$ x = a_1 N_1 x_1 + a_2 N_2 x_2 = 0 \quad \text { since } a_1=0, a_2 = 0$$
So the general unique solution is
$$ \begin{align} x & \equiv 0 \pmod {5 \times 6} \\ \\ x & \equiv 0 \pmod {30} \end{align}$$
(c) The modulii 8 and 13 are indeed pair-wise coprime, so we can use the Chinese Remainder Theorem to solve
$x ≡ 3 \pmod 8$
$x ≡ 5 \pmod {13}$
Formula (3.23) here is
$$ x = a_1 N_1 x_1 + a_2 N_2 x_2 = 3(13)x_1 + 5(8)x_2$$
where $N_k x_k \equiv 1 \pmod {n_k}$, and so
$$ \begin{align} 13 x_1 & \equiv 1 \pmod {8} \\ \\ 5 x_1 & \equiv 1 \pmod 8 \\ \\ x_1 & \equiv 5 \pmod 8 \end{align}$$
and
$$ \begin{align} 8 x_2 & \equiv 1 \pmod {13} \\ \\ x_2 & \equiv 5 \pmod {13} \end{align}$$
which gives
$$ x = a_1 N_1 x_1 + a_2 N_2 x_2 = 3(13)(5) + 5(8)(5) = 395 $$
So the general unique solution is
$$ \begin{align} x & \equiv 395 \pmod {8 \times 13} \\ \\ x & \equiv 83 \pmod {104} \end{align}$$
(d) The modulii 3, 5 and 7 are indeed pair-wise coprime, so we can use the Chinese Remainder Theorem to solve
$x ≡ 1 \pmod 3$
$x ≡ 2 \pmod 5$
$x ≡ 3 \pmod 7$
Formula (3.23) here is
$$ x = a_1 N_1 x_1 + a_2 N_2 x_2 + a_3 N_3 x_3 = 1(5 \times 7)x_1 + 2(3 \times 7)x_2 + 3(3 \times 5)x_3 $$
where $N_k x_k \equiv 1 \pmod {n_k}$, and so
$$ \begin{align} 35 x_1 & \equiv 1 \pmod 3 \\ \\ 2 x_1 & \equiv 1 \pmod 3 \\ \\ x_1 & \equiv 2 \pmod 3 \end{align}$$
and
$$ \begin{align} 21 x_1 & \equiv 1 \pmod 5 \\ \\ x_1 & \equiv 1 \pmod 5 \end{align}$$
also
$$ \begin{align} 15 x_3 & \equiv 1 \pmod 7 \\ \\ x_3 & \equiv 1 \pmod 7 \end{align}$$
which gives
$$ x = a_1 N_1 x_1 + a_2 N_2 x_2 + a_3 N_3 x_3 = 1(5 \times 7)2 + 2(3 \times 7)1 + 3(3 \times 5)1 = 157 $$
So the general unique solution is
$$ \begin{align} x & \equiv 157 \pmod {3 \times 5 \times 7} \\ \\ x & \equiv 52 \pmod {105} \end{align}$$
(e) The modulii 5, 7 and 11 are indeed pair-wise coprime, so we can use the Chinese Remainder Theorem to solve
$x ≡ 1 \pmod 5$
$x ≡ 3 \pmod 7$
$x ≡ 5 \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 = 1(7 \times 11)x_1 + 3(5 \times 11)x_2 + 5(5 \times 7)x_3 $$
where $N_k x_k \equiv 1 \pmod {n_k}$, and so
$$ \begin{align} 77 x_1 & \equiv 1 \pmod 5 \\ \\ 2 x_1 & \equiv 1 \pmod 5 \\ \\ x_1 & \equiv 3 \pmod 5 \end{align}$$
and
$$ \begin{align} 55 x_2 & \equiv 1 \pmod 7 \\ \\ 6 x_2 & \equiv 1 \pmod 7 \\ \\ x_2 & \equiv 6 \pmod 7 \end{align}$$
also
$$ \begin{align} 35 x_3 & \equiv 1 \pmod {11} \\ \\ 2 x_3 & \equiv 1 \pmod {11} \\ \\ x_3 & \equiv 6 \pmod {11} \end{align}$$
which gives
$$ x = a_1 N_1 x_1 + a_2 N_2 x_2 + a_3 N_3 x_3 = 1(7 \times 11)3 + 3(5 \times 11)6 + 5(5 \times 7)6 = 2271 $$
So the general unique solution is
$$ \begin{align} x & \equiv 2271 \pmod {5 \times 7 \times 11} \\ \\ x & \equiv 346 \pmod {385} \end{align}$$
Prove Proposition (3.16).
Proposition (3.16):
The linear congruence $ax ≡ b \pmod n$ has exactly $g$ incongruent solutions modulo $n$, provided $g \mid b$ where $g= \gcd (a, n)$.
We first prove a lemma which we'll use in the proof.
Lemma (A): If integer $x$ runs through the complete residue system $\{0,1, \ldots, n-1\}$ for modulo $n$, then so does $ax \pmod n$, provided $\gcd(a,b)=1$.
That is, $ax \pmod n$ takes on one and only one value in the residue system $\{0,1, \ldots, n-1\}$.
Proof: Consider two elements $x$ and $y$ from the residue system. If $ax \equiv ay \pmod n$, then this means $ax -ay = a(x-y) = kn$, for some integer $k$. Since $\gcd(a,n)=1$, that is, $a$ and $n$ share no common factors, then it must be that $n$ divides $(x-y)$. That is $x=y \pmod n$, which means $x$ and $y$ are the same element. And so $ax \pmod n$ runs through the residue system without repetition as $x$ runs through the residue system.
Another way of saying this is that if $ax \equiv r \pmod n$, then no other element of the residue system $y \ne x$ results in $ay \equiv r \pmod n$.
Note: this online solution helped with this proof.
We consider two cases, $g=\gcd(a,n) =1$ and $g=\gcd(a,n)>1$.
Case $g=1$
Since $g=\gcd(a,n)=1$, Lemma A tells us that as $x$ runs through the complete residue system $\{0, 1, \ldots, n-1\}$ modulo $n$, then so does $ax \pmod n$. That is $ax \equiv b$ for only one value of $x$. Therefore the number of incongruent solutions for $ax \equiv b \pmod n$ is $g$.
Case $g>1$
We simplify the linear congruence from $ax \equiv b \pmod n$ to
$$ \begin{align} a_0 x & \equiv b_0 \pmod {\frac{n}{\gcd(n,g)}} \quad \quad \text{Proposition 3.10}\\ \\ & \equiv b_0 \pmod{ \frac{n}{\gcd(g n_0,g)} } \\ \\ & \equiv b_0 \pmod{ \frac{n}{g}} \\ \\ a_0 x & \equiv b_0 \pmod{n_0} \end{align}$$
where $ga_0 = a$, $g b_0 = b$ and $g n_0 = n$.
By definition $\gcd(n_0, a_0)=1$ and so the linear congruence $a_0 x \equiv b_0 \pmod{n_0} $ has one incongruent solution, by Lemma A above.
If $x_0$ is the smallest non-negative solution, then the congruent solutions in modulo $n_0$ are
$$ x_0 + (n_0)t $$
for integer $t$.
These are incongruent in modulo $n$ when
$$ x_0 + (n_0)t < n $$
That is
$$\begin{align} t & < \frac{n - x_0}{n_0} \\ \\ & = \frac{n}{n_0} - \frac{x_0}{n_0} \\ \\ & = g - \frac{x_0}{n_0}\end{align}$$
Here $\frac{x_0}{n_0} < 1$ because $x_0$ is a residue in modulo $n_0$, and so $x_0 < n_0$. This means the largest integer $t$ is $g-1$.
So $t$ ranges from 0 to $g-1$, that is, takes on $g$ values. This means there are $g$ incongruent solutions $ x_0 + (n_0)t $ for the linear congruence $ax \equiv b \pmod n$.
In both cases we have shown there are exactly $g=\gcd(a,n)$ incongruent solutions to the linear congruence $ax \equiv b \pmod n$, provided $g \mid b$.
This is a question on cryptography — secure communication.
Let $p= 11$, $q= 13$, and $e = 17$.
Bob’s public key is given by the two numbers $p × q$ and $e$.
Bob’s private key, the number $d$, satisfies
$$ d ≡ e^{−1} \pmod {(p− 1) (q− 1)} $$
(i) Determine Bob’s public key numbers and the private key number.
(ii) Alice encrypts a message $M = 12$ by forming
$$ M^e ≡ a \pmod {pq} $$
Bob recovers the message by using his private key $d$ such that
$$M ≡ a^d \pmod {pq}$$
Find $a \pmod {pq}$ and show that
$$ M ≡ a^d \pmod {pq}$$
(i) Bob's public key numbers are $p \times q = 11 \times 13 = 143$ and $17$.
Bob's private key number $d$ satisfies
$$ \begin{align} d & \equiv e^{−1} \pmod {(p− 1) (q− 1)} \\ \\ & \equiv e^{-1} \pmod {120} \\ \\ 17d & \equiv 1 \pmod {120} \end{align} $$
Here $d=113$ satisfies this, and so Bob's private key is 113.
(ii) We have $a$ as
$$ \begin{align} a & \equiv M^e \pmod {pq} \\ \\ & \equiv 12^{17} \pmod {143} \\ \\ & \equiv (12^2)^8 \times 12 \pmod {143} \\ \\ & \equiv (-1)^8×12 \pmod{143} \\ \\ a & \equiv 12 \pmod {143} \end{align} $$
We now recover $M$
$$ \begin{align} a^d & \equiv 12^{113} \pmod {143} \\ \\ & \equiv (12^2)^{56} \times 12 \\ \\ & \equiv (-1)^{56} \times 12 \\ \\ & \equiv 12 \pmod {143} \\ \\ & \equiv M \pmod {143} \end{align} $$
(a) Explain why the congruence equation $x^5 ≡ x \pmod 5$ has more than one solution and find all the solutions.
(b) Solve the congruence $x^5 + 1 ≡ 0 \pmod 5$.
(a) We only need to consider residues $x \equiv 0, 1, 2, 3, 4 \pmod 5$. Let's consider each case in turn
$x \equiv 0 \pmod 5$ means $x^5 \equiv 0 \pmod 5$, and so is a solution.
$x \equiv 1 \pmod 5$ means $x^5 \equiv 1 \pmod 5$, and so is a solution.
$x \equiv 2 \pmod 5$ means $x^5 \equiv 32 \equiv 2 \pmod 5$, and so is a solution.
$x \equiv 3 \pmod 5$ means $x^5 \equiv 243 \equiv 3 \pmod 5$, and so is a solution.
$x \equiv 4 \pmod 5$ means $x^5 \equiv 1024 \equiv 4 \pmod 5$, and so is a solution.
So there are five incongruent solutions:
$x \equiv 0 \pmod 5$
$x \equiv 1 \pmod 5$
$x \equiv 2 \pmod 5$
$x \equiv 3 \pmod 5$
$x \equiv 4 \pmod 5$
(b) We can rewrite the congruence $x^5 +1 \equiv 0 \pmod 5$ as
$$ x^5 \equiv 4 \pmod 5 $$
Using the result above, there is only one solution which is $x \equiv 4 \pmod 5$.
Determine $71^{−1} \pmod {771}$.
By definition $x = 71^{-1} \pmod {771}$ is the unique solution to
$$ 71x \equiv 1 \pmod {771} $$
Here $g=\gcd(771,71)=1$ and so there is a unique solution.
The equivalent Diophantine equation is
$$ 71x + 771y = 1 $$
Let's apply the Euclidean Algorithm to 771 and 71.
$ 771 = 10(71) + 61 $
$ 71 = 1(61) + 10 $
$ 61 = 6(10) + 1 $
$ 10 = 10(1) + 0 $
And so
$ 1 = 61 - 6(10) = 61 - 6(71 - 61) = - 6(71) +7(61) $
$ 1 = 7(771 - 10(71)) - 6(71) = 771(7) + 71(-76)$
So $x=-76, y = 7$ is a solution to the Diophantine equation.
Noting that $-76 \equiv 695 \pmod {771}$, the unique solution to $ 71x \equiv 1 \pmod {771} $ is $695 \pmod {771}$.
And so the multiplicative inverse $7^{-1} \pmod{771}$ is $ 695 \pmod{771}$.
Use an equivalent congruence to find the general solution of the following Diophantine equations:
(a) $6x + 7y= 100$
(b) $1998x + 100y= 5192$
(a) The equivalent congruence is
$$ 6x \equiv 100 \pmod 7 $$
Here $g = \gcd(7,6)=1$ and so there is a unique solution.
$$ \begin{align} 6x & \equiv 100 \pmod 7 \\ \\ -x & \equiv 2 \pmod 7 \\ \\ x & \equiv 5 /pmod 7 \end{align}$$
So $x=5 + 7t$ for some integer $t$.
Substituting into $6x + 7y = 100$ gives us $y=10-6t$. So the general solution is
$$ x = 5 + 7t, \quad y = 10-6t $$
for some integer $t$.
(b) The equivalent congruence is
$$ 1998x \equiv 5192 \pmod {100} $$
Here $g = \gcd(100, 1998) = 2$, and $g\mid 5192$ and so there are two incongruent solutions.
$$ \begin{align} 1998x & \equiv 5192 \pmod {100} \\ \\ -2x & \equiv -8 \pmod {100} \\ \\ 2x & \equiv 8 \pmod {100} \\ \\ x & \equiv 4 \pmod {50} \end{align}$$
So $x= 4 + 50t$ for some integer $t$.
Substitution into $1998x + 100y= 5192$ gives us $y = -28 -999t$.
So the general solution is
$$ x = 4 + 50t , \quad y=-28 -999t $$
for some integer $t$.
Note: The two solutions are $x \equiv 4 \pmod {100}$ and $x \equiv 54 \pmod {100}$, but in modulo 50, we reduce the number of solutions to one.
Solve the linear Diophantine equation $15x− 6y= 3$.
Using your solutions to this equation, solve $15x ≡ 3 \pmod 6$.
We start with
$$ 15x -6y = 3 $$
By Proposition 1.17, this has integer solutions if $g=\gcd(15, -6) = 3$ divides 3, which it does.
By inspection, a solution is $x=1, y=2$. So the general solution is, by Proposition 1.18,
$$ x = 1 -2t , \quad y =2 - 5t $$
for some integer $t$.
The linear congruence $15x \equiv 3 \pmod 6$ is equivalent to
$$ 15x-3 = 6y $$
for some integer $y$.
We've shown that $x=1-2t$ for some integer $t$. This is equivalent to
$$ x \equiv 1 \pmod 2$$
This is equivalent to a set of $g=3$ solutions in modulo 6.
$x \equiv 1 \pmod 6$
$x \equiv 3 \pmod 6$
$x \equiv 5 \pmod 6$
(All of these are congruent to 1 in modulo 2).
Alternative Solution
The linear congruence $15x \equiv 3 \pmod 6$ is equivalent to
$$ 15x-3 = 6y $$
for some integer $y$.
We've shown that $x=1-2t$ for some integer $t$. That is
$$ x \equiv 1-2t \pmod 6 $$
where $t=0, 1, 2$ because there are $g=3$ incongruent solutions. The solution are therefore
$x \equiv 1 \pmod 6$
$x \equiv -1 \pmod 6$
$x \equiv -3 \pmod 6$
Substituting with the equivalent non-negative residues
$x \equiv 1 \pmod 6$
$x \equiv 3 \pmod 6$
$x \equiv 5 \pmod 6$
Show that the equation
$$ \frac{a} {g} x ≡ b (mod \frac{n}{ g} ) $$
where $g= \gcd (a, n)$ has solutions.
How many solutions does this equation have?
For the equation to have solutions we need $f = \gcd( \frac{n}{g}, \frac{a}{g} )$ to divide $b$.
We have
$$ \begin{align} f & = \gcd( \frac{n}{g}, \frac{a}{g} ) \\ \\ & = 1 \quad \text{Proposition 1.5}\end{align} $$
This divides any integer, including $b$, and so the equation has solutions.
The number of solutions is $f$, that is, there is only one incongruent solution.
Show that the equation
$$n (a + b) x ≡ [a^2− b^2] \pmod {(a + b)}$$
has solutions.
How many solutions does this equation have?
For the equation to have solutions we need $g= \gcd((a+b), n(a+b))$ to divide $[a^2 - b^2]$.
We have
$$ \begin{align} g & = \gcd(a+b, n(a+b) \\ \\ & = \left | (a+b) \right | \times \gcd(n,1) \\ \\ &= \left | (a+b) \right | \end{align}$$
Since $[a^2 - b^2] = (a+b)(a-b)$, we can see that $g \mid [a^2 - b^2]$ and so the equation does have solutions.
The number of incongruent solutions is the gcd $g$, which is $\left | (a+b) \right |$.
Show that none of the elements in $\{2, 3, \ldots , p− 2\}$ modulo $p$ are self-invertible.
Self-invertible means $a^{−1} ≡ a \pmod n$.
Let's assume, for the purpose of contradiction, that $a$ is self-invertible, where $a \in \{2, 3, \ldots , p− 2\}$.
That is,
$$ a^{-1} \equiv a \pmod p$$
By definition of a multiplicative inverse,
$$ a \times a^{-1} \equiv 1 \pmod p $$
Since $a^{-1} \equiv a \pmod p$
$$ \begin{align} a \times a & \equiv 1 \pmod p \\ \\ a^2 -1 & \equiv 0 \pmod p \\ \\ (a+1)(a-1) & \equiv 0 \pmod p \end{align}$$
By Proposition (3.14)(a) we have $(a +1) \equiv 0 \pmod p$ or $(a -1) \equiv 0 \pmod p$.
That is, at least one of the following is true
Neither of these are in $\{2, 3, \ldots , p− 2\}$ modulo $p$, which contradicts the assumption that elements in $\{2, 3, \ldots , p− 2\}$ are self-invertible.
So we conclude that none of the elements in $\{2, 3, \ldots , p− 2\}$ are self-invertible.
Alternatively, from Exercise (3.3).11, $a$ is only self-invertible in modulo $p$ if $a \equiv \pm 1 \pmod p$. That is $a \equiv 1 \pmod p$ or $a \equiv -1 \equiv p-1 \pmod p$. But these $a$ are not in $\{2, 3, \ldots , p− 2\}$, and so elements of this set are not self-invertible.
Show that every integer $a$ such that $1 ≤ a < p$ where $p$ is prime has a multiplicative inverse modulo $p$.
Since $p$ is prime, it only has factors 1 and $p$. This means $\gcd(a,p)=1$ for $1 \le a < p$.
Then then means the following linear congruence has a unique solution for $x$
$$ ax \equiv 1 \pmod p$$
Here $x$ is the multiplicative inverse of $a$ modulo $p$.
Show that the linear congruence $ax ≡ b \pmod n$ where $\gcd (a, n) = 1$ has the unique solution given by $x ≡ a^{−1}b \pmod n$.
Determine $9^{−1} \pmod {21}$.
By proposition (3.21), since $\gcd(a,n)=1$ then $a \pmod n$ has a unique inverse.
$$ aa^{-1} \equiv 1 \pmod n $$
Multiplying by $b \pmod n$ gives us
$$ aa^{-1}b \equiv b \pmod n $$
This is of the form $ax \equiv b \pmod n$ where $x \equiv a^{-1}b \pmod n$. This $x$ is a unique solution because $\gcd(a,n)=1$.
$x = 9^{-1} \pmod{21}$ would be the unique solution to the linear congruence
$$ 9x \equiv 1 \pmod {21}$$
Here $g = \gcd(21,9)=3$ and $g$ does not divide 1, and so there is no solution.
That is, $9^{-1} \pmod{21}$ does not exist. Alternatively, 9 does not have a multiplicative inverse in modulo 21.
Prove Proposition (3.21).
Proposition (3.21) states that $a \pmod n$ has an inverse if and only if $\gcd (a, n) = 1$.
($\implies$)
If $x$ is the multiplicative inverse of $a$ modulo $n$ then
$$ ax \equiv 1 \pmod n $$
By Proposition (3.16), for there to be a unique solution to this linear congruence, we must have $\gcd(n,a)=1$.
($\impliedby$)
If $\gcd(a,n)=1$ then by Bezout's Identity there exist integers $x,y$ such that
$$ ax + yn = 1 $$
That is
$$ ax = 1 - yn $$
Or equivalently
$$ ax \equiv 1 \pmod n $$
By showing the implications hold in both directions, we have proven Proposition (3.21).
Show that if $a^{−1} ≡ b \pmod n$ then $b^{−1} ≡ a \pmod n$.
We're given $a^{−1} ≡ b \pmod n$ which means
$$ab \equiv 1 \pmod n$$
Since $ab = ba$, we have
$$ba \equiv 1 \pmod n$$
Which gives us that $a \pmod n$ is the multiplicative inverse of $b$ modulo $n$. That is, $b^{-1} \equiv a \pmod n$.
Let $p$ be prime. Show that $a$ modulo $p$ has its own inverse if and only if $a ≡ ±1 \pmod p$.
($\implies$)
If $a$ has its own inverse then
$$ \begin{align} a \times a & \equiv 1 \pmod p \\ \\ a^2 -1 & \equiv 0 \pmod p \\ \\ (a+1) \times (a-1) & \equiv 0 \pmod p \end{align} $$
Proposition (3.14)(a) tells us that either $a -1 \equiv 0 \pmod p$ or $a+1 \equiv 0 \pmod p$. That is $a \equiv \pm 1 \pmod p$.
($\impliedby$)
We start with $a \equiv \pm 1 \pmod p$. This means either $a -1 \equiv 0 \pmod p$ or $a+1 \equiv 0 \pmod p$. This gives us
$$ \begin{align} (a-1) \times (a+1) \equiv 0 \pmod p \\ \\ a^2 - 1 \equiv 0 \pmod p \\ \\ a \times a \equiv 1 \pmod p \end{align} $$
That is, $a$ has its own inverse.
By showing the implication in both directions, we have shown that for prime $p$, $a$ modulo $p$ has its own inverse if and only if $a ≡ ±1 \pmod p$.
Give an example of a linear congruence $ax ≡ b \pmod n$ where integer $d > 1$ divides $a$, $n$, and $b$ but the equation has no solutions.
Since $d > 1$ divides $a$, $n$, and $b$, we have for some integers $p, q, r$
$$ \begin{align} a & = pd \\ \\ b & = qd \\ \\ n & = rd \end{align} $$
So we can rewrite the linear congruence as
$$ pdx \equiv qd \pmod {rd}$$
which reduces to
$$ \begin{align} px & \equiv q \pmod {\frac{rd}{\gcd(rd,d)}} \\ \\ px & \equiv q \pmod {\frac{rd}{d\gcd(r,1)}} \\ \\ & \equiv q \pmod {\frac{rd}{d}} \\ \\ px & \equiv q \pmod {r} \end{align} $$
For there to be no solutions
$$ \gcd(r,p) \not \mid q $$
The candidates $r=2, p=2, q=3$ satisfy $\gcd(r,p) \not \mid q$.
We can then try $d=2$, giving $a=4, b=6, n=4$.
So an example of a linear congruence is
$$ 4x \equiv 6 \pmod 4 $$
Let's check: $g = \gcd(4,4)=4$ and $g \not \mid 6$, so there are no solutions, yet $d=2$ divides 4 and 6.
Determine the integers $a$ which have a multiplicative inverse:
(a) modulo 12
(b) modulo 13
(c) modulo 15
(a) $ax \equiv 1 \pmod {12}$ is the equation we want to solve.
We require $\gcd(12,a)=1$ for there to be a unique solution.
This limits the values of $a$ to 1, 5, 7, 11.
(b) $ax \equiv 1 \pmod {13}$ is the equation we want to solve.
We require $\gcd(13,a)=1$ for there to be a unique solution. Since 13 is prime, then any integer greater than 0 is co-prime to it,
The values of $a$ are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,12.
(c) (a) $ax \equiv 1 \pmod {15}$ is the equation we want to solve.
We require $\gcd(15,a)=1$ for there to be a unique solution.
This limits the values of $a$ to 1, 2, 4, 7, 8, 11, 13, 14.
Find the multiplicative inverses of the following:
(a) $6 \pmod {13}$
(b) $5 \pmod {6}$
(c) $12 \pmod {17}$
(d) $16 \pmod {17}$
(e) $9 \pmod {101}$
(f) $n + 1 \pmod {n}$
The multiplicative inverse of $a$ modulo $n$ is the unique solution $x \pmod n$ of $ax \equiv 1 \pmod n$.
(a) $6x \equiv 1 \pmod {13}$ is the equation we want to solve.
$g = \gcd(13, 6)=1$ and $g \mid 1$ so there is a unique solution.
By inspection $x=11$ is a solution, so the general solution is $$ x \equiv 11 \pmod {13} $$
(b) $5x \equiv 1 \pmod 6$ is the equation to solve.
$g = \gcd(6,5) =1$ and $g \mid 1$ so there is a unique solution.
By inspection $x=5$ is a solution, so the general solution is $$ x \equiv 5 \pmod 6 $$
(c) $12x \equiv 1 \pmod {17}$ is the equation to solve.
$g = \gcd(17,12) =1$ and $g \mid 1$ so there is a unique solution.
By inspection $x=10$ is a solution, so the general solution is $$ x \equiv 10 \pmod {17} $$
(d) $16x \equiv 1 \pmod {17}$ is the equation to solve.
$g = \gcd(17,16) =1$ and $g \mid 1$ so there is a unique solution.
By inspection $x=16$ is a solution, so the general solution is $$ x \equiv 16 \pmod {17} $$
(e) $9x \equiv 1 \pmod {101}$ is the equation to solve.
$g = \gcd(101,9) =1$ and $g \mid 1$ so there is a unique solution.
$9x \equiv 1 \pmod {101}$ means $x = \frac{101k + 1}{9}$ for some integer $k$. For $x$ to be an integer, $101k + 1$ must be a multiple of nine. A guess is $101k+1 =405$, and so $k=4$, which gives $x=45$. So the general solution is $$x \equiv 45 \pmod {101}$.
(f) $(n+1) x \equiv 1 \pmod n$ is the equation to solve.
$g = \gcd(n,n+1) =1$ and $g \mid 1$ so there is a unique solution.
By inspection $x=1$ is a solution, so the general solution is $$ x \equiv 1 \pmod n $$
Just for fun, let's check this with $x=n+1$. We have $(n+1)(n+1) = n^2 + 2n +1 \equiv 1 \pmod n$, as expected.
Consider the linear congruence equation $nx ≡ b \pmod {n^2}$ where $n ≥ 1$.
Determine the integers $b$ for which there are solutions and state the number of solutions.
For there to be solutions $g = \gcd(n^2, n)=n$ must divide b.
So there are solutions for $b=nk$ for some integer $k$, that is, $b$ is a multiple of $n$.
The number of incongruent solutions is $n$.
Consider the linear congruence $15x ≡ b \pmod {25}$. Find the integers $b$ for which this linear congruence has solutions.
How many incongruent solutions does it have?
For there to be solutions $g=\gcd(25,15)=5$ needs to divide $b$.
So $b=5k$ for some integer $k$ means the linear congruence has solutions, and the number of incongruent solutions is 5.
Find all solutions of the following congruences:
(a) $10x ≡ 20 \pmod {15}$
(b) $12x ≡ 18 \pmod {48}$
(c) $12x ≡ 48 \pmod {18}$
(a) $g = \gcd(15,10) = 5$ and $5 \mid 20$ so there are 5 solutions.
We simplify $10x ≡ 20 \pmod {15}$ as $x \equiv 2 \pmod {3}$. By inspection $x=2$ is a solution.
So the 5 solutions are
$x \equiv 2 \pmod {15}$
$x \equiv 5 \pmod {15}$
$x \equiv 8 \pmod {15}$
$x \equiv 11 \pmod {15}$
$x \equiv 14 \pmod {15}$
(b) $g = \gcd(48,12)=12$ and $g \not \mid 18$ so there is no solution.
(c) $g = \gcd(18,12)=6$ and $g \mid 48$ so there are 6 solutions.
We simplify $12x \equiv 48 \pmod {18}$ as $12x \equiv 12 \pmod {18}$. This can be further simplified as $x \equiv 1 \pmod 3$. By inspection, $x=1$ is a solution.
So the 6 solutions are
$x \equiv 1 \pmod {18}$
$x \equiv 4 \pmod {18}$
$x \equiv 7 \pmod {18}$
$x \equiv 10 \pmod {18}$
$x \equiv 13 \pmod {18}$
$x \equiv 16 \pmod {18}$
Which of the following congruences equations have no solutions? If any of these have solutions, find them.
(a) $12x ≡ 4 \pmod {18}$
(b) $13x ≡ 5 \pmod {65}$
(c) $18x ≡ 1 \pmod {16}$
(d) $1001x ≡ 121 \pmod {11}$
(e) $15x ≡ 9 \pmod {27}$
(f) $407x ≡ 40 \pmod {666}$
(a) $g = \gcd(18,12)=6$ but $g \not \mid 4$ so there is no solution.
(b) $g = \gcd(65, 13)=13$ and $g \not \mid 5$ so there is no solution.
(c) $g = \gcd(16,18)=2$ and $g \not \mid 1$ so there is no solution.
(d) $g = \gcd(11,1001)=11$ and $g \mid 121$ so there are 11 solutions.
Since we are working with modulo 11, then 11 solutions means $x=1,2, \ldots, 9,1 0 \pmod{11}$.
Alternatively, we can simplify $1001x ≡ 121 \pmod {11}$ as $0x = 0 \pmod {11}$ for which any integer is a solution.
(e) $g = \gcd(27,15)=3$ and $g \mid 9$, so there are 3 solutions.
We can simplify $15x ≡ 9 \pmod {27}$ as $5x \equiv 3 \pmod{9}$. By inspection $x=6$ is a solution.
So the full set of 3 solutions is
$ x \equiv 6 \pmod {27}$
$ x \equiv 15 \pmod {27}$
$ x \equiv 24 \pmod {27}$
(f) $g= \gcd(666,407) = 34$ but $g \not \mid 40$ so there is no solution.
Find all the solutions of the following linear congruences:
(a) $6x ≡ 2 \pmod {4}$
(b) $12x ≡ 6 \pmod {18}$
(c) $15x ≡ 10 \pmod {25}$
(d) $7x ≡ 21 \pmod {1001}$
(a) $g = \gcd(4,6)=2$ and $g \mid 2$ so there are 2 incongruent solutions.
We can simplify $6x \equiv 2 \pmod 4$ as $2x \equiv 2 \pmod 4$. By inspection $x=1$ and $x=3$ are solutions.
So the general solutions is $x \equiv 1 \pmod 4$ and $x \equiv 3 \pmod 4$.
(b) $g = \gcd(18,12)=6$ and $g \mid 6$ so there are 6 incongruent solutions.
By Proposition (3.10) we can simplify $12x \equiv 6 \pmod {18}$ as $2x \equiv 1 \pmod 3$. By inspection $x \equiv 2 \pmod {3}$.
So the 6 incongruent solutions are
$x \equiv 2 \pmod {18}$
$x \equiv 5 \pmod {18}$
$x \equiv 8 \pmod {18}$
$x \equiv 11 \pmod {18}$
$x \equiv 14 \pmod {18}$
$x \equiv 17 \pmod {18}$
(c) $g = \gcd(25,15)=5$ and $g \mid 10$ so there are 5 incongruent solutions.
By Proposition (3.10) we can simplify $15x ≡ 10 \pmod {25}$ as $3x \equiv 2 \pmod 5$. By inspection $x \equiv 4 \pmod 5$.
So the 5 incongruent solutions are
$ x \equiv 4 \pmod {25} $
$ x \equiv 9 \pmod {25} $
$ x \equiv 14 \pmod {25} $
$ x \equiv 19 \pmod {25} $
$ x \equiv 24 \pmod {25} $
(d) $g = \gcd(1001,7)=7$ and $g \mid 21$ so there are 7 incongruent solutions.
By Proposition (3.10) we can simplify $7x ≡ 21 \pmod {1001}$ as $x \equiv 3 \pmod {143}$. By inspection $x \equiv 3 \pmod {143}$.
So the 7 incongruent solutions are
$ x \equiv 3 \pmod {1001} $
$ x \equiv 146 \pmod {1001} $
$ x \equiv 289 \pmod {1001} $
$ x \equiv 432 \pmod {1001} $
$ x \equiv 575 \pmod {1001} $
$ x \equiv 718 \pmod {1001} $
$ x \equiv 861 \pmod {1001} $
Solve the following linear congruence equations:
(a) $2x ≡ 25 \pmod 7$
(b) $17x ≡ 3 \pmod 5$
(c) $27x ≡ 33 \pmod {10}$
(d) $128x ≡ 1 \pmod {5}$
(e) $32x ≡ 23 \pmod {21}$
(f) $54x ≡ 52 \pmod {53}$
(a) $g = \gcd(7,2)=1$ and $g \mid 25$ so a solution exists, and there is only one.
We first recognise that $2x \equiv 25 \equiv 4 \pmod 7$. By inspection we can see $x=2$ is a solution.
So the general solution is $$x \equiv 2 \pmod 7$$
(b) $g = \gcd(5,17)=1$ and $g \mid 3$ so a solution exists, and there is only one.
We can simplify $17x \equiv 2x \equiv 3 \pmod 5$. By inspection $x=4$ is a solution.
So the general solution is $$x \equiv 4 \pmod 5$$
(c) $g = \gcd(10,27)=1$ and $g \mid 33$ so a solution exists, and there is only one.
We simplify $27x \equiv 33 \pmod {10}$ to $7x \equiv 3 \pmod {10}$. By inspection $x=9$ is a solution.
So the general solution is $$x \equiv 9 \pmod {10}$$
(d) $g = \gcd(5,128)=1$ and $g \mid 1$ so a solution exists, and there is only one.
We can simplify $128x \equiv 1 \pmod 5$ to $3x \equiv 1 \pmod 5$. By inspection $x=2$ is a solution.
So the general solution is $$x \equiv 2 \pmod 5$$
(e) $g = \gcd(21,32)=1$ and $g \mid 23$ so a solution exists, and there is only one.
We can simplify $32x \equiv 23 \pmod {21}$ to $11x \equiv 2 \pmod {21}$. By inspection $x=4$ is a solution.
So the general solution is $$x \equiv 4 \pmod {21}$$
(f) $g = \gcd(53,54)=1$ and $g \mid 52$ so a solution exists, and there is only one.
We can simplify $54x \equiv 52 \pmod {53}$ to $x \equiv 52 \pmod {53}$. By inspection $x=52$ is a solution.
So the general solution is $$x \equiv 52 \pmod {53}$$
Solve the following congruence equations:
(a) $3x ≡ 1 \pmod 5$
(b) $4x ≡ 2 \pmod 7$
(c) $7x ≡ 0 \pmod 8$
(d) $10x ≡ 5 \pmod {13}$
(e) $8x ≡ 4 \pmod {15}$
(f) $9x ≡ 10 \pmod {16}$
We will use Proposition (3.15) which says the linear congruence $ax ≡ b \pmod n$ has a solution if and only if $g \mid b$ where $g= \gcd (a, n)$. In addition, Proposition (3.16) says there are exactly $g$ solutions, if they exist.
(a) $\gcd(3,5)=1$, and $1 \mid 1$, so a solutions exists, and there is only one.
$3x \equiv 1 \pmod 5$ means $3x = 1 + 5y$ for some integer $y$. Rewriting $x = \frac{1+5y}{3}$. To ensure integer $x$, we can't have $y=0$, however $y=1, x=2$ works. Since there is only one solution, we don't need to find any more pairs of $x,y$.
So the solution is $$x \equiv 2 \pmod 5$$
(b) $\gcd(7,4)=1$ and $1\mid 2$, so a solution exists, and there is only one.
$4x \equiv 2 \pmod 7$ means $4x = 2 + 7y$ for some integer $y$. The pair $y=2, x=4$ is an integer solution. Since there is only one solution, we don't need to find anymore parts of $x,y$.
So the solution is $$x \equiv 4 \pmod 7$$
(c) $\gcd(7,8)=1$ and $1 \mid 0$, so a solution exists, and there is only one.
By inspection the solution is $$x \equiv 0 \pmod 8$$
(d) $\gcd(13,10) = 1$ and $1 \mid 5$, so a solution exists, and there is only one.
$10x \equiv 5 \pmod {13}$ means $10x = 5 + 13y$ for some integer $y$. The pair $y=5, x=7$ is an integer solution. Since there is only one solution, we don't need to find more.
So the solution is $$x \equiv 7 \pmod {13}$$
(e) $\gcd(15, 8) =1$ and $1 \mid 4$, so a solution exists, and there is only one.
$8x \equiv 4 \pmod {15}$ means $8x = 4 + 15y$ for some integer $y$. The pair $y=4, x = 8$ is an integer solution. Since there is only one solution, we don't need to find more.
So the solution is $$x \equiv 8 \pmod {15}$$
(f) $\gcd(16,9)=1$ and $1 \mid 10$, so a solution exists, and there is only one.
$9x \equiv 10 \pmod {16}$ means $9x = 10 + 16y$ for some integer $y$. The pair $y = 5, x= 10$ is an integer solution. Since there is only one solution, we don't need to find more.
So the solution is $$x \equiv 10 \pmod {16}$$
Show that if $a^n ≡ 0 \pmod p$ where $p$ is prime then $a ≡ 0 \pmod p$.
We will use induction on $n$.
Let $P(n)$ be the statement
$a^n \equiv 0 \pmod p \implies a \equiv 0 \pmod p$ for prime $p$.
We need to prove a base case $P(1)$ and an inductive step $P(n) \implies P(n+1)$.
Base Case
The base case is
$a^1 \equiv 0 \pmod p \implies a \equiv 0 \pmod p$ for prime $p$.
The antecedent and the consequent are equivalent statements so the base case is true.
Inductive Step
We assume the induction hypothesis $P(n)$ and aim to show $P(n+1)$, which is
$a^{n+1} \equiv 0 \pmod p \implies a \equiv 0 \pmod p$ for prime $p$.
Noting that $a^{n+1} = a^n \times a$, we have
$$ a^{n+1} = a^n \times a \equiv 0 \pmod p $$
Proposition 3.14 gives us $a^n \equiv 0 \pmod p$ or $a \equiv 0 \pmod p$. Let's consider both cases in turn.
Case 1: $a^n \equiv 0 \pmod p$, which by the induction hypothesis, implies $a \equiv 0 \pmod p$.
Case 2: $a \equiv 0 \pmod p$ is the conclusion we desire.
In both cases we conclude $a \equiv 0 \pmod p$, and so $P(n+1)$ is true.
We have shown by induction that if $a^n ≡ 0 \pmod p$ where $p$ is prime then $a ≡ 0 \pmod p$.
Disprove the following:
(i) If $\gcd (x, n) = 1$ and $x^2 ≡ 1 \pmod n$ then $x ≡ ±1 \pmod n$.
(ii) If $\gcd (x, n) = 1$ and $x^2 ≡ a \pmod n$ then $x ≡ ±a \pmod n$.
We'll do this by counter-example.
(i) Using $x = 2, n = 3$, we have $\gcd(2,3)=1$ and $2^2 \equiv 1 \pmod 3$. But $2 \equiv \pm 1 \pmod 3$ is false.
(ii) Using $x = 3, n = 5$, we have $\gcd(3,5)=1$ and $3^2 \equiv 4 \pmod 5$. But $3 \equiv \pm 4 \pmod 5$ is false.
Find the least non-negative residue $x$ modulo $n$ in the following cases:
(a) $x^2 ≡ 25 \pmod 3$
(b) $x^2 ≡ 100 \pmod {11}$
Also determine the general solution in each case.
(a) We have
$$\begin{align} x^2 & \equiv 25 \pmod 3 \\ \\ x^2 - 25 & \equiv 0 \pmod 3 \\ \\ (x-5) (x+5) & \equiv 0 \pmod 3 \end{align}$$
Proposition 3.14(b) gives us $(x-5) \equiv 0 \pmod 3$ or $(x+5) \equiv 0 \pmod 3$. Let's consider each case in turn.
Case 1: $(x-5) \equiv 0 \pmod 3$ gives us $x = 5 +3t$ for some integer $t$.
Case 3: $(x+5) \equiv 0 \pmod 3$ is $x \equiv 1 \pmod 3$, which gives us $x = 1 +3t$ for some integer $t$.
The least non-negative residue is 1 from the second case with $t=0$.
The general solution is $x = 3t + 3 \pm 2$.
(b) This time we use $10^2 \equiv (-1)^2 \pmod 11$,
$$\begin{align} x^2 & \equiv 100 \pmod {11} \\ \\ x^2 & \equiv 10^2 \pmod {11} \\ \\ & \equiv 1\pmod {11} \\ \\ x^2 -1 & \equiv 0 \pmod {11} \\ \\. (x+1) \times (x-1) & \equiv 0 \pmod {11}\end{align}$$
Proposition 3.14(b) gives us $(x-1) \equiv 0 \pmod {11}$ or $(x+1) \equiv 0 \pmod{11}$. Let's consider each case in turn.
Case 1: $(x-1) \equiv 0 \pmod {11}$ gives us $x = 1 + 11t$ for some integer $t$.
Case 1: $(x+1) \equiv 0 \pmod {11}$ is $x \equiv 10 \pmod {11}$, which gives us $x = 10 + 11t$ for some integer $t$.
The least non-negative residue is 1 from the first case with $t=0$.
The general solution is $x = 11t + \frac{11}{2} \pm \frac{9}{2}$.
Prove Proposition 3.14 (b).
Proposition 3.14(b) states that if $p$ is prime, then $a^2 ≡ b^2 \pmod p \iff a ≡ ±b \pmod p$.
($\implies$)
We first note that $a^2 ≡ b^2 \pmod p$ means, for some integer $k$
$$ \begin{align} kp & = a^2 - b^2 \\ \\ & = (a+b)(a-b) \end{align}$$
Applying Proposition 2.2 to $p \mid (a+b) \times (a-b)$ means either $p \mid (a+b)$ or $p \mid (a-b)$. Let's consider these two cases in turn.
$p \mid (a+b)$ means $a + b \equiv 0 \pmod p$ which is equivalent to $a \equiv -b \pmod p$.
$p \mid (a-b)$ measn $a - b \equiv 0 \pmod p$ which is equivalent to $a \equiv b \pmod p$.
So we have, for prime $p$, $a^2 ≡ b^2 \pmod p \implies a ≡ ±b \pmod p$.
($\impliedby$)
This time we start with $a \equiv \pm b \pmod p$. This gives us two cases to consider, $a \equiv b \pmod p$ and $a \equiv -b \pmod p$. Let's consider these in turn.
$a \equiv b \pmod p$ means $p \mid (a -b)$
$a \equiv -b \pmod p$ means $p \mid (a +b)$
Since at least one of these cases is true, we have $p \mid (a-b) \times (a+b)$, which gives us $p \mid a^2 - b^2$. That is, $a^2 \equiv b^2 \pmod p$.
By showing both implications, we have proved Proposition 3.14(b).
Show that if $x^2 ≡ 0 \pmod p$ where $p$ is prime then $p \mid x$.
$x^2 \equiv 0 \pmod p$ means that $p \mid x \times x$.
Let's recall Proposition (2.2), which says that if $p$ is prime and $p \mid (a × b)$ then $p \mid a$ or $p \mid b$.
Since $p$ is prime, $p \mid x \times x$ means $p \mid x$.
Alternatively, we can use Proposition (3.14) that if $a × b ≡ 0 \pmod p$ where $p$ is prime then $a ≡ 0 \pmod p$ or $b ≡ 0 \pmod p$.
So $x \times x \equiv 0 \pmod p$ means $x = 0 \pmod p$, which means $p \mid x$.
Give three different examples which satisfy
$a × b ≡ 0 \pmod p ⇒ a ≡ b ≡ 0 \pmod p$
where $p$ is prime.
Example 1
$a = 3, b = 3, p = 3$ gives $3 \times 3 \equiv 0 \pmod 3$, and $3 \equiv 3 \equiv 0 pmod 3$.
Example 2
$a = 2, b = 4, p = 2$ gives $2 \times 4 \equiv 0 \pmod 2$, and $2 \equiv 4 \equiv 0 pmod 2$.
Example 3
$a = 25, b = 5, p = 5$ gives $25 \times 5 \equiv 0 \pmod 5$, and $25 \equiv 5 \equiv 0 pmod 5$.
Give three different examples which satisfy the following:
$a × b ≡ 0 \pmod n$ implies $a ≡ 0 \pmod n$ or $b ≡ 0 \pmod n$.
Example 1
$a =2, b =3, n = 2$ gives $2 \times 3 \equiv 0 \pmod 2$, and $2 = 0 \pmod 2$.
Example 2
$a =10, b =3, n = 5$ gives $10 \times 3 \equiv 0 \pmod 5$, and $10 = 0 \pmod 5$.
Example 3
$a =3, b =20, n = 10$ gives $3 \times 20 \equiv 0 \pmod 10$, and $20 = 0 \pmod 10$.
Give three different examples which satisfy the following:
$a × b ≡ 0 \pmod n$ but $a ≢ 0 \pmod n$ and $b ≢ 0 \pmod n$.
Example 1
$a = 2, b = 3, n = 6$ gives $2 \times 3 \equiv 0 \pmod 6$ but $2 \not \equiv 0 \pmod 6$ and $3 \not \equiv 0 \pmod 6$.
Example 2
$a = 2, b = 5, n = 10$ gives $2 \times 5 \equiv 0 \pmod {10}$ but $2 \not \equiv 0 \pmod {10}$ and $5 \not \equiv 0 \pmod {10}$.
Example 3
$a = 3, b = 5, n = 15$ gives $3 \times 5 \equiv 0 \pmod {15}$ but $3 \not \equiv 0 \pmod {15}$ and $5 \not \equiv 0 \pmod {15}$.
Which integers $x$ (general solution) satisfy the following congruences?
(a) $2x ≡ 2 × 1 \pmod 5$
(b) $7x ≡ 7 × 3 \pmod {14})$
(c) $10x ≡ 10 × 12 \pmod {6}$
(d) $8x ≡ 8 × 5 \pmod {48}$
(e) $−3x ≡ 3 × 5 \pmod {21}$
(f) $−12x ≡ 12 × 7 \pmod {108}$
(g) $15x ≡ 0 \pmod 8$
We'll use Proposition (3.10) that if $ac ≡ bc \pmod n$ then $a ≡ b \pmod {\frac{n}{g} }$ where $g= \gcd (c, n)$.
(a) By Proposition (3.10) we have $x \equiv 1 \pmod {\frac{5}{1}}$. That is, $x \equiv 1 \pmod {5}$.
This means $x = 1 + 5t$ for some integer $t$.
(b) By Proposition (3.10) we have $x \equiv 3 \pmod {\frac{14}{7}}$. That is, $x \equiv 1 \pmod {2}$.
This means $x = 1 + 2t$ for some integer $t$.
(c) By Proposition (3.10) we have $x \equiv 12 \pmod {\frac{6}{2}}$. That is, $x \equiv 0 \pmod {3}$.
This means $x = 3t$ for some integer $t$.
(d) By Proposition (3.10) we have $x \equiv 5 \pmod {\frac{48}{8}}$. That is, $x \equiv 5 \pmod {6}$.
This means $x = 5 + 6t$ for some integer $t$.
(e) By Proposition (3.10) we have $-x \equiv 5 \pmod {\frac{21}{3}}$. That is, $-x \equiv 5 \pmod {7}$ or $x \equiv -5 \equiv 2 \pmod {7}$.
This means $x = 2 +7t$ for some integer $t$.
(f) By Proposition (3.10) we have $-x \equiv 7 \pmod {\frac{108}{12}}$. That is, $-x \equiv 7 \pmod {9}$ or $x \equiv -7 \equiv 2 \pmod {9}$.
This means $x = 2 +9t$ for some integer $t$.
This means $x = 8t$ for some integer $t$.
Check whether the following congruences satisfy the rule,
$$ac ≡ bc \pmod n \implies a ≡ b \pmod n$$
(a) $5 × 4 ≡ 5 × 7 \pmod 3$
(b) $9 × 12 ≡ 9 × 8 \pmod 6$
(c) $6 × 11 ≡ 6 × 7 \pmod 8$
(d) $13 × 21 ≡ 13 × 7 \pmod {26}$
(e) $13 × 31 ≡ 13 × 5 \pmod {26}$
(f) $101 × 35 ≡ 101 × 66 \pmod {31}$
(a) Here $a=4, b=7$ and $4 \equiv 7 \pmod 3$ is true.
This is because $4-7 = -3 = (-1) \times 3$.
(b) Here $a=12, b=8$, but $12 \equiv 8 \pmod 6$ is false.
This is because $12 \equiv 0 \pmod 6$.
(c) Here $a=11, b=7$, but $11 \equiv 7 \pmod 8$ is false.
This is because $11 \equiv 3 \pmod 8$.
(d) Here $a=21, b=7$, but $21 \equiv 7 \pmod 26$ is false.
This is because $21 \equiv 21 \pmod 26$.
(e) Here $a=31, b=5$, and $31 \equiv 5 \pmod 26$ is true.
This is because $31 -5 = 26 = (1) \times 26$.
(f) Here $a=35, b=66$, and $35 \equiv 66 \pmod 31$ is true.
This is because $35 -66 = -31 = (1) \times 31$.
This is a test for divisibility by 11. Let a natural number $N$ be written in its decimal format as:
$$N = a_n \; a_{n−1} \; a_{n−2} \; \ldots \; a_2 \; a_1 \; a_0$$
where $a$’s are
the digits of the number.
Let
$$T = a_0 − a_1 + a_2 − a_3 + \ldots + (−1)^n a_n$$
Show that 11 divides $N$ $\iff$ 11 divides $T$.
Let's write $N$ as the sum
$$ N = 10^n a_n + 10^{n-1}a_{n-1} + 10^{n-2}a_{n-2} + \ldots 10^2a_2 + 10^1a_1 + 10^0a_0$$
Since $10 \equiv -1 \pmod {11}$, we can write
$$\begin{align} N & \equiv (-1)^n a_n + (-1)^{n-1}a_{n-1} + (-1)^{n-2}a_{n-2} + \ldots (-1)^2a_2 + (-1)^1a_1 + (-1)^0a_0 \pmod {11} \\ \\ & \equiv a_0 - a_1 + a_2 - a_3 + \ldots + (-1)^n a_n \\ \\ & \equiv T \pmod {11}\end{align}$$
($\implies$) If 11 divides $N$ then $N \equiv 0 \pmod{11}$. The above tells us $T \equiv 0 \pmod{11}$, and so 11 divides $T$.
($\impliedby$) If 11 divides $T$ then $T \equiv 0 \pmod{11}$. The above tells us $N \equiv 0 \pmod{11}$, and so 11 divides $N$.
Prove Proposition (3.9).
Proposition (3.9) is
Let $P (x) = c_0 + c_1x + c_2x^2 + ⋯ + c_{m−1}x^{m−1} + c_mx^m$ be an $m$th degree polynomial, that is $c_m ≢ 0 \pmod n$, where the coefficients $c_k$’s are integers.
If $a ≡ b \pmod n$ then $P (a) ≡ P (b) \pmod n$.
We start with $P(a)$
$$ P (a) = c_0 + c_1a + c_2a^2 + ⋯ + c_{m−1}a^{m−1} + c_ma^m $$
Since $a \equiv b \pmod n$
And so
$$ \begin{align} P (a) & \equiv c_0 + c_1b + c_2b^2 + ⋯ + c_{m−1}b^{m−1} + c_mb^m \pmod n \\ \\ & \equiv P(b) \pmod n \end{align}$$
Which proves Proposition (3.9).
Show that the last two digits of $9^{9^9}$ are 8 and 9.
The last two digits if a number are the last positive residue modulo 100.
Let's first rewrite $9^{9^9}$ as $(10 - 1)^{9^9}$.
Using the binomial theorem, we consider the expansion of $(a+b)^n$, for integer $n$ larger than 1
$$(a+b)^n = a^2K + nab^{n-1} + b^n$$
where the term $a^2K$ contains terms which have $a^2$ as a factor.
Applying this to $(10 - 1)^{9^9}$ we have
$$ \begin{align} (10 - 1)^{9^9} & = 10^2K + (9^9)(10)(-1)^{(9^9-1)} + (-1)^{9^9} \\ \\ & = 10^2K + (9^9)(10) -1 \\ \\ & \equiv 0 + 3874204890 -1 \pmod {100} \\ \\ & = 3874204889 \pmod {100} \\ \\ & \equiv 89 \pmod{100} \end{align} $$
So the last two digits of $9^{9^9}$ are 8 and 9.
Prove the following by induction:
$$ 2^{2n+1} ≡ 9n^2− 3n + 2 \pmod {54} $$
where $n$ is a natural number.
Let $P(n)$ be the statement
$$ 2^{2n+1} ≡ 9n^2− 3n + 2 \pmod {54} $$
We need to prove the base case $P(0)$ and the inductive step $P(n) \implies P(n+1)$.
Base Case
The base case is $P(0)$ which is
$$ 2^{2(0)+1} ≡ 9(0)^2− 3(0) + 2 \pmod {54} $$
This reduces to $2 \equiv 2 \pmod {54}$, which is true.
Inductive Step
To prove $P(n) \implies P(n+1)$ we assume the induction hypothesis $P(n)$ and aim to show $P(n+1)$, which is
$$\begin{align} 2^{2(n+1)+1} & \equiv 9(n+1)^2− 3(n+1) + 2 \pmod {54} \\ \\ 2^{2n + 3} & \equiv 9 n^2 + 15 n + 8 \end{align}$$
Let's start with the $2^{2n + 3}$
$$\begin{align} 2^{2n + 3} & = 2^{2n + 1} \times 2^2 \\ \\ & \equiv (9n^2− 3n + 2) \times 4 \pmod {54} \quad \text{by the induction hypothesis} \\ \\ & \equiv 36 n^2 - 12 n + 8 \pmod{54} \\ \\ & \equiv 9 n^2 + 15 n + 8 + 27n(n - 1) \pmod {54} \\ \\ & \equiv 9 n^2 + 15 n + 8 + 54m \pmod {54} \quad \text{since }n(n-1)=2m \text{ for some }m \\ \\ & \equiv 9 n^2 + 15 n + 8 \pmod {54} \quad \text{since } 5m \equiv 0 \end{align}$$
And so we have shown the inductive step is true.
By induction we have shown that $ 2^{2n+1} ≡ 9n^2− 3n + 2 \pmod {54} $ is true for all natural $n$.
Show that
(i) $x^7 ≡ x \pmod 7$
(ii) $x^7 ≡ x \pmod 6$
(iii) $x^7 ≡ x \pmod {42}$
(i) Any integer modulo 7 will have a residue in the complete residue set $\{0,1,2,3,4,5,6\}$.
We consider each case in turn.
If $x \equiv 0 \pmod 7$ then $x^7 \equiv 0^7 \equiv 0 \equiv x \pmod 7$.
If $x \equiv 1 \pmod 7$ then $x^7 \equiv 1^7 \equiv 1 \equiv x \pmod 7$.
If $x \equiv 2 \pmod 7$ then $x^7 \equiv 2^7 \equiv 128 \equiv 2 \equiv x \pmod 7$.
If $x \equiv 3 \pmod 7$ then $x^7 \equiv 3^7 \equiv 2187 \equiv 3 \equiv x \pmod 7$.
If $x \equiv 4 \pmod 7$ then $x^7 \equiv 4^7 \equiv 16384 \equiv 4 \equiv x \pmod 7$.
If $x \equiv 5 \pmod 7$ then $x^7 \equiv 5^7 \equiv 78125 \equiv 5 \equiv x \pmod 7$.
If $x \equiv 6 \pmod 7$ then $x^7 \equiv 6^7 \equiv 279936 \equiv 6 \equiv x \pmod 7$.
In all possible cases we have $x^7 ≡ x \pmod 7$.
(ii) Any integer modulo 6 will have a residue in the complete residue set $\{0,1,2,3,4,5\}$.
We consider each case in turn.
If $x \equiv 0 \pmod 6$ then $x^7 \equiv 0^7 \equiv 0 \equiv x \pmod 6$.
If $x \equiv 1 \pmod 6$ then $x^7 \equiv 1^7 \equiv 1 \equiv x \pmod 6$.
If $x \equiv 2 \pmod 6$ then $x^7 \equiv 2^7 \equiv 128 \equiv 2 \equiv x \pmod 6$.
If $x \equiv 3 \pmod 6$ then $x^7 \equiv 3^7 \equiv 2187 \equiv 3 \equiv x \pmod 6$.
If $x \equiv 4 \pmod 6$ then $x^7 \equiv 4^7 \equiv 16384 \equiv 4 \equiv x \pmod 6$.
If $x \equiv 5 \pmod 6$ then $x^7 \equiv 5^7 \equiv 78125 \equiv 5 \equiv x \pmod 6$.
In all possible cases we have $x^7 ≡ x \pmod 6$.
(iii) We use the result of exercise 24(c) which says that if $a ≡ b \pmod n$ and $a ≡ b \pmod m$ then $a ≡ b \pmod {m × n}$, provided $\gcd (m, n) = 1$.
Here we have $x^7 \equiv x \pmod 7$ and $x^7 \equiv x \pmod 6$, and also $\gcd(6,7)=1$. So we conclude $x^7 \equiv x \pmod {42}$.
Show that a natural number is divisible by 3 if and only if the sum of the digits is divisible by 3.
A natural number $n$ is of the form
$$ n = (a_0 \times 10^0) + (a_1 \times 10^1) + (a_2 \times 10^2) + \ldots + (a_m \times 10^m) $$
where $m$ is an integer, and $a_i$ are the digits of the number in base 10.
Propositions 3.6 and 3.8 with $10 \equiv 1 \pmod 3$ allow us to reduce this as follows
$$ \begin{align} n & = (a_0 \times 10^0) + (a_1 \times 10^1) + (a_2 \times 10^2) + \ldots + (a_m \times 10^m) \\ \\ & \equiv (a_0 \times 1^0) + (a_1 \times 1^1) + (a_2 \times 1^2) + \ldots + (a_m \times 1^m) \pmod 3 \\ \\ n & \equiv a_0 + a_1 + a_2 + \ldots + a_m \pmod 3 \end{align} $$
($\implies$) If $n$ is divisible by 3, then $n \equiv 0 \pmod 3$. This means the sum of the digits must also be congruent to 0 modulo 0, that is, divisible by 3.
($\impliedby$) If the sum of digits is divisible by 3, then that sum is congruent to 0 modulo 3. That means $n \equiv 0 \pmod 3$, that is, $n$ is divisible by 3.
And so a natural number is divisible by 3 if and only if the sum of the digits is divisible by 3.
Show that 3 divides $4^n− 1$ where $n$ is a natural number.
We will use induction on $n$. Let the statement $P(n)$ be that $3 \mid $4^n-1$.
We need to prove the base case $P(1)$ and the inductive step $P(n) \implies P(n+1)$.
Base Case
The base case $P(1)$ is $3 \mid 4-1$ which is $3 \mid 3$. This is true.
Induction Step
To prove $P(n) \implies P(n+1)$ we assume the induction hypothesis $P(n)$, and show $P(n+1)$. That is, we assume $3 \mid 4^n -1$ and aim to show $3 \mid 4^{n+1}-1$.
$3 \mid 4^n-1$ means there is some integer $k$ such that
$$ 4^n - 1 = 3k $$
We have
$$ \begin{align} 4^{n+1} -1 & = 4(4^n) - 1 \\ \\ & = 4(3k + 1) - 1 \quad \text{induction hypothesis} \\ \\ &= 3(4k + 1) \end{align} $$
And so we have shown $3 \mid 4^{n+1}-1$.
We have shown by induction that 3 divides $4^n - 1$.
Prove that $a^3 − a \equiv 0 \pmod 3$.
Using the Division Algorithm, we'll write $a$ as
$$ a = 3q + r $$
for integers $q,r$ where $0 \le r < 3$.
There are 3 cases for $r$, $r=0$, $r=1$, and $r=2$. Let's consider each in turn,
For $r=0$,
$$ \begin{align} a^3 - a & = 3^3q^3 - 3q \\ \\ & = 3(3^2q^3 - q) \\ \\ & \equiv 0 \pmod {3} \end{align} $$
For $r=1$,
$$ \begin{align} a^3 - a & = (3q+1)^3 - (3q+1) \\ \\ &= 27 q^3 + 27 q^2 + 6 q \\ \\ & = 3(9q^3 + 9q^2 + 2q) \\ \\ & \equiv 0 \pmod {3} \end{align} $$
For $r=2$,
$$ \begin{align} a^3 - a & = (3q+2)^3 - (3q+2) \\ \\ & = 27 q^3 + 54 q^2 + 33 q + 6 \\ \\ & = 3(9 q^3 + 18 q^2 + 11 q + 2) \\ \\ & \equiv 0 \pmod {3} \end{align} $$
So for all cases of $r$, we have $a^3 − a \equiv 0 \pmod 3$.
(a) Prove that if $m \mid n$ and $a ≡ b \pmod n$ then $a ≡ b \pmod m$.
(b) Prove that if $ka ≡ kb \pmod {kn}$ then $a ≡ b \pmod n$ where $k > 0$.
(c) Prove that if $a ≡ b \pmod n$ and $a ≡ b \pmod m$ then $a ≡ b \pmod {m × n}$, provided $\gcd (m, n) = 1$.
(d) Let $a ≡ b \pmod {n_k}$ for $k= 1, 2, 3, \ldots , r$ where $\gcd (n_i,n_j) = 1$ for $i ≠ j$. Prove that $a ≡ b \pmod {n_1 × n_2 × \ldots × n_r}$.
(e) Prove that if $n = p_1^{k_1} × p_2^{k_2} × \ldots × p_m^{k_m}$ where $p_j$’s are distinct primes and $a ≡ b \pmod n$ then $a ≡ b \pmod {p_j}$ for $j= 1, 2, \ldots , m$.
(a) $m \mid n$ means, for some integer $k$
$$ n = km $$
Also $a \equiv b \pmod n$ means, for some integer $j$
$$ a - b = jn $$
Substituting for $n$ we have
$$ a - b = (jk)m $$
which, by definition, is $a \equiv b \pmod m$.
(b) We're given $ka \equiv kb \pmod {kn}$, which by definition means, for some integer $j$
$$\begin{align} ka - kb & = jkn \\ \\ k(a-b) & = k(jn) \\ \\ a - b & = jn \quad \text{for } k>0\end{align}$$
Which, by definition, is $a \equiv b \pmod n$.
(c) We are given $a ≡ b \pmod n$ and $a ≡ b \pmod m$. This means, for some integers $j,k$
$$ a - b = jn $$
$$ a - b = km $$
By Bezout's identity, then for some integers $p,q$
$$ pm + qn = \gcd(m,n) = 1 $$
Multiplying by $a-b$
$$ \begin{align} a-b & = pm(jn) + qn(km) \\ \\ & a - b = (pj + qk)mn \end{align}$$
Which by definition means $a \equiv b \pmod{mn}$ as long as $\gcd(m,n)=1$
(d) We'll do this by induction. Let $P(r)$ be the statement
Let $a ≡ b \pmod {n_k}$ for $k= 1, 2, 3, \ldots , r$ where $\gcd (n_i,n_j) = 1$ for $i ≠ j$. Then $a ≡ b \pmod {n_1 × n_2 × \ldots × n_r}$.
We need to prove the base case $P(2)$, and the inductive step $P(r) \implies P(r+1)$.
The base case $P(2)$ is
Let $a ≡ b \pmod {n_k}$ for $k= 1, 2$ where $\gcd (n_1,n_2) = 1$. Then $a ≡ b \pmod {n_1 × n_2 }$.
We proved this in exercise (c) above.
To prove $P(r) \implies P(r+1)$, we assume the induction hypothesis $P(r)$ and show $P(r+1)$, which is
Let $a ≡ b \pmod {n_k}$ for $k= 1, 2, 3, \ldots , r, r+1$ where $\gcd (n_i,n_j) = 1$ for $i ≠ j$. Then $a ≡ b \pmod {n_1 × n_2 × \ldots × n_r \times n_{r+1}}$.
Let's abbreviate $n_1 \times n_2 \times \ldots \times n_r$ as $A$.
The antecedent conditions of the induction hypotheses hold, namely that $a ≡ b \pmod {n_k}$ for $k= 1, 2, 3, \ldots , r$ where $\gcd (n_i,n_j) = 1$ for $i ≠ j$. This means the consequent holds, namely $a ≡ b \pmod A$.
Given $a \equiv b \pmod {A}$ and $a \equiv b \pmod {n_{r+1}}$, and it is true that $\gcd(A, n_{r+1})=1$ then by exercise (c) we have $a \equiv b \pmod {A \times n_{r+1}}$. Unabbreviating, that is $a ≡ b \pmod {n_1 × n_2 × \ldots × n_r \times n_{r+1}}$.
Why is it true that $\gcd(A,n_{r+1}) = 1$? Well, we are given that $n_{r+1}$ is coprime to all $n_k$ for $k=1, 2, 3, \ldots, r$, and so $n_{r+1}$ shares no common factors with $A = n_1 \times n_2 \times \ldots \times n_r$.
So by induction we have shown the statement to be true for all $r$.
(e) We are given the prime decomposition of $n$ as
$$n = p_1^{k_1} × p_2^{k_2} × \ldots × p_m^{k_m}$$
where $p_j$’s are distinct primes.
We are also given $a ≡ b \pmod n$ which means that for integer $k$
$$ a - b = kn $$
Substituting for $n$
$$ a - b = k \times p_1^{k_1} × p_2^{k_2} × \ldots × p_m^{k_m}$$
Selecting a $p_j$ where $1 \le j \le m$, we factor it out
$$ a - b = \left ( k \times p_1^{k_1} × p_2^{k_2} × \ldots × p_j^{k_m - 1} \times \ldots \times p_m^{k_m} \right ) \times p_j$$
That is,
$$ a - b = m \times p_j$$
where $m$ is an integer, and so by definition
$$ a \equiv b \pmod {p_j} $$
for any $j$ in $1 \le j \le m$.
Note: the author's solution is neater. We're given $a ≡ b \pmod n$ which means $n \mid (a-b)$. Similarly we're given $n = p_1^{k_1} × p_2^{k_2} × \ldots × p_m^{k_m}$ which means $p_j \mid n$. Since $p_j \mid n$ and $n \mid (a-b)$ we have $p_j \mid (a-b)$, which by definition means $a \equiv b \pmod {p_j}$.
Prove that at least one of $k$ consecutive integers is divisible by $k$.
We first consider the case $k=1$. In this case all inetegers are divisible by 1, an so the statement is trivially true.
We now consider the remaining $k \ge 2$.
A sequence of $k$ consecutive integers, beginning at $n$ is
$$ n,\; n + 1, \; n + 2, \; \ldots , \; n + (k - 1) $$
If we write $n = kq + r$ using the Division Algorithm, where $0 \le r < k$, we have
$$ kq + r,\; kq + r + 1, \; kq + r + 2, \; \ldots , \; kq + r + (k - 1) $$
Since $kq \equiv 0 \pmod k$, this sequence modulo $k$ is
$$ \boxed { r, \; r + 1, \; r + 2, \; \ldots , \; r + (k - 1) \pmod k } $$
For a given $r$ in $0 \le r \le k-1$, each element in the sequence is
$$ r + j $$
where $0 \le j \le k-1$.
We'll split $r$ into two cases, $r=0$ and $r \ge 1$.
In the case $r=0$, the first element of the sequence is then $j=0$, that is $0 \pmod k$, which is divisible by $k$.
In the case $r \ge 1$, we ask whether the sequence contains an element such that $r + j = k \equiv 0 \pmod k$. We can see that for any $r$ in the range $1 \le r \le k-1$ there is always a value of $j$ in the range $0 \le j \le k-1$ so that $r + j = k$. See below for a justification.
Because $ k \equiv 0 \pmod k$, each sequence has an element that is divisible by $k$.
So in both cases, there is an element in the sequence that is divisible by $k$.
We have shown that at least one of $k$ consecutive integers is divisible by $k$.
We want to show that for any $r$ in the range $1 \le r \le k-1$ there is always a value of $j$ in the range $0 \le j \le k-1$ such that $r + j = k$. Let's do this by induction on $k$.
Let $P(k)$ be the statement
For any $r$ in the range $1 \le r \le k-1$ there is always a value of $j$ in the range $0 \le j \le k-1$ such that $r + j = k$.
We need to show both the base case $P(k)$ and the inductive step $P(k) \implies P(k+1)$.
The base case is $P(2)$:
For any $r$ in the range $1 \le r \le 1$ there is always a value of $j$ in the range $0 \le j \le 1$ such that $r + j = 2$.
Here $r$ can only be 1, and $j$ can be 0 or 1. If we choose $j=1$, we have $r+k = 1 + 1 = 2$. So the base case is true.
The induction step is $P(k) \implies P(k+1)$. We assume the induction hypothesis $P(k)$, and show $P(k+1)$:
For any $r$ in the range $1 \le r \le k$ there is always a value of $j$ in the range $0 \le j \le k$ such that $r + j = k+1$.
The induction hypothesis tells us that there is an $r$ in the range $[1,k-1]$ and a $j$ in the range $[0,k-1]$ such that $r + j = k$. If we can pick $r$ from the range extended by one $[1,k]$ then we can have $r + j = k+1$. Alternatively, if we pick $j$ from the range extended by one $[0,k]$ then we can have $r + j = k+1$. And so $P(k+1)$ is true.
By induction we have shown that for any $r$ in the range $1 \le r \le k-1$ there is always a value of $j$ in the range $0 \le j \le k-1$ such that $r + j = k$.
Determine the last digit of the following numbers:
(a) $1961^{1961}$
(b) $1023^{1022}$
(c) $2019^{2019}$
(a) We have $1961 \equiv 1 \pmod{10}$ and so by Proposition (3.8)
$$ 1961^{1961} \equiv (1)^{1961} \equiv 1 \pmod {10} $$
So the last digit is 1.
(b) Noting that $1022 =2 \times 511$, we have
$$\begin{align} 1023^{1022} & \equiv (3)^{1022} \pmod {10} \\ \\ & \equiv (3)^{2 \times 511} \pmod {10} \\ \\ & \equiv (3^2)^{511} \\ \\ & \equiv (-1)^511 \\ \\ & \equiv -1 \pmod {10} \\ \\ & \equiv 9 \pmod {10} \end{align}$$
So the last digit is 9.
(c) We have
$$\begin{align} 2019^{2019} & \equiv (-1)^2019 \pmod{10} \\ \\ & \equiv 9 \pmod{10} \end{align}$$
So the last digit is 9.
Determine the last digit of $1! + 2! + 3! + 4! + ⋯ + 1000!$.
We first notice that, for some integer $k$,
$$1! + 2! + 3! + 4! + ⋯ + 1000! = 1! + 2! + 3! + 4! +10k $$
since all the terms including and after 5! include factors 5 and 2, and so are multiples of 10.
Also
$$ 10k \equiv 0 \pmod {10} $$
This means
$$ \begin{align} 1! + 2! + 3! + 4! + ⋯ + 1000! & = 1! + 2! + 3! + 4! +10k \\ \\ & \equiv 1! + 2! + 3! + 4! + (0) \pmod{10} \\ \\ & \equiv 33 \pmod{10} \\ \\ & \equiv 3 \pmod{10} \end{align}$$
So the last digit of $1! + 2! + 3! + 4! + ⋯ + 1000!$ is 3.
Show that $F_5 = 2^{2^5}$ + 1 (Fermat number with $n = 5$) is divisible by 641.
We have
$$ \begin{align} 2^{2^5} & = 2^{32} + 1= (2 ^ 8)^{4} + 1 \\ \\ & \equiv 256^4 + 1 \pmod{641} \\ \\ & \equiv 640 + 1 \pmod{641} \\ \\ & \equiv (-1) + 1\pmod {641} \\ \\ & \equiv 0 \pmod{641} \end{align} $$
We use the following result in the above
$ 2^8 = 256 \equiv 256 \pmod{641} $
$ 256^4 = 4294967296 \equiv 640 \pmod{641} $
This means $F_5$ is divisible by 641, and is not a prime.
Find the remainders in the following cases:
(a) $11^{567}$ is divided by 61
(b) $11^{567}$ is divided by 43
(a) We start with
$$ \begin{align} 11^{567} & = 11^{81 \times7} = (11^7)^{81} \\ \\ & \equiv 50^{81} \pmod{61} \\ \\ & \equiv (50^3)^{27} \pmod{61} \\ \\ & \equiv 11^{27} \pmod{61} \\ \\ & \equiv (11^9)^3 \pmod{61} \\ \\ & \equiv 11^3 \pmod{61} \\ \\ & \equiv 50 \pmod{61} \end{align}$$
We used the following to simplify the above.
$ 11^7 = 19487171 \equiv 50 \pmod {61} $
$ 50^3 = 125000 \equiv 11 \pmod {61} $
$ 11^9 = 2357947691 \equiv 11 \pmod {61} $
$ 11^3 = 1331 \equiv 50 \pmod {61} $
So the remainder after $11^{567}$ is divided by 61 is 50.
(b) We start with
$$ \begin{align} 11^{567} & = 11^{3 \times 27 \times 7} = (11^3)^{27 \times 7} \\ \\ & \equiv (-2)^{27 \times 7} \pmod{43} \\ \\ & \equiv (-2^7)^{27} \pmod{43} \\ \\ & \equiv 1^27 \pmod{43} \\ \\ & \equiv 1 \pmod{43} \end{align}$$
We used the following to simplify the above.
$ 11^3 = 1331 \equiv -2 \pmod {43} $
$ (-2)^7 = -128 \equiv 1 \pmod {43} $
So the remainder after $11^{567}$ is divided by 43 is 1.
Disprove the following statements:
(a) $a^2 ≡ b^2 \pmod n \implies a ≡ b \pmod n$
(b) $a × b ≡ 0 \pmod n \implies a ≡ 0 \lor b ≡ 0 \pmod n$
(c) $ac ≡ bc \pmod n \implies a ≡ b \pmod n$
We disprove the statements with counter-examples.
(a) Choosing $a=6, b=4, n= 10$ gives us
$ 6^2 = 36 \equiv 6 \pmod {10} $
$ 4^2 = 16 \equiv 6 \pmod {10} $
But $6 \equiv 4 \pmod {10}$ is false.
(b) Choosing $a=5, b=2, n=10$ gives us
$ 5 \times 2 = 10 \equiv 0 \pmod {10} $
But $2 \equiv 0 \pmod {10}$ and $5 \equiv 0 \pmod {10}$ are both false.
(c) Choosing $a=3, b=8, c=4, n=10$ gives us
$ ac = 3 \times 4 = 12 \equiv 2 \pmod {10} $
$ bc = 8 \times 4 = 32 \equiv 2 \pmod {10} $
But $3 \equiv 8 \pmod {10}$ is false.
Let $a$ be any integer. Show that the last digit of $a^3$ can be any digit from 0 to 9.
We use the Division Algorithm to write integer $a$ as $a = 10q + r$ where $0 \le r < 10$.
We have
$$ \begin{align} a^3 & = 1000 q^3 + 300 q^2 r + 30 q r^2 + r^3 \\ \\ & \equiv 0 + 0 + 0 + r^3 \pmod {10} \\ \\ & \equiv r^3 \end{align}$$
We consider each case for $r$:
| r | r^3 | r^3 mod 10 |
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| 2 | 8 | 8 |
| 3 | 27 | 7 |
| 4 | 64 | 4 |
| 5 | 125 | 5 |
| 6 | 216 | 6 |
| 7 | 343 | 3 |
| 8 | 512 | 2 |
| 9 | 729 | 9 |
This tells us the last digit of $a^3$ can be any digit from 0 to 9.
Prove that the last digit of a square number can only be 0, 1, 4, 5, 6, or 9.
By the division algorithm, we can write every integer as $n = 10q + r$ where $0 \le r < 10$.
We then have
$$ \begin{align} n^2 & = 100q^2 + 20qr + r^2 \\ \\ & \equiv 0 + 0 + r^2 \pmod {10} \\ \\ & \equiv r^2 \pmod{10} \end{align}$$
We consider each case for $r$:
$r=0$ means $r^2 = 0 \equiv 0 \pmod {10}$
$r=1$ means $r^2 = 1 \equiv 1 \pmod {10}$
$r=2$ means $r^2 = 4 \equiv 4 \pmod {10}$
$r=3$ means $r^2 = 9 \equiv 9 \pmod {10}$
$r=4$ means $r^2 = 16 \equiv 6 \pmod {10}$
$r=5$ means $r^2 = 25 \equiv 5 \pmod {10}$
$r=6$ means $r^2 = 36 \equiv 6 \pmod {10}$
$r=7$ means $r^2 = 49 \equiv 9 \pmod {10}$
$r=8$ means $r^2 = 64 \equiv 4 \pmod {10}$
$r=9$ means $r^2 = 81 \equiv 1 \pmod {10}$
So for any integer, the last digit of its square can only be 0, 1, 4, 5, 6, or 9.