This article is translated by AI.

1

If $a_1 \equiv b_1(\bmod m), a_2 \equiv b_2(\bmod m)$, then

$$a_1 a_2 \equiv b_1 b_2(\bmod m)$$

Proof: From the hypothesis $a_1 \equiv b_1 \pmod m$ and $a_2 \equiv b_2 \pmod m$, according to the definition of congruence, we know that $m \mid (a_1 - b_1)$ and $m \mid (a_2 - b_2)$. Therefore, there exist integers $k_1, k_2$ such that

$$a_1 - b_1 = mk_1$$

$$a_2 - b_2 = mk_2$$

That is $a_1 = b_1 + mk_1$ and $a_2 = b_2 + mk_2$.

Consider $a_1 a_2 - b_1 b_2$:

$$\begin{align} a_1 a_2 - b_1 b_2 &= (b_1 + mk_1)(b_2 + mk_2) - b_1 b_2 \\ &= b_1 b_2 + b_1 mk_2 + b_2 mk_1 + m^2 k_1 k_2 - b_1 b_2 \\ &= m(b_1 k_2 + b_2 k_1 + mk_1 k_2) \end{align}$$

Since $b_1, k_2, b_2, k_1, m$ are all integers, $b_1 k_2 + b_2 k_1 + mk_1 k_2$ is also an integer. Therefore, $m \mid (a_1 a_2 - b_1 b_2)$. According to the definition of congruence, we have

$$a_1 a_2 \equiv b_1 b_2 \pmod m$$

Q.E.D.

2

If $C \equiv d(\bmod m),(C, m)=1$, then

$$aC \equiv bd(\bmod m)$$

is equivalent to

$$a \equiv b(\bmod m)$$

Proof:($\Longrightarrow$) Assume $a \equiv b \pmod m$. From the hypothesis $C \equiv d \pmod m$. According to the conclusion of the previous question (multiplicative property of congruence), multiplying $a \equiv b \pmod m$ and $C \equiv d \pmod m$, we get:

$$aC \equiv bd \pmod m$$

($\Longleftarrow$) Assume $aC \equiv bd \pmod m$. From the hypothesis $C \equiv d \pmod m$, we know $m \mid (C-d)$, that is $d = C - mk$ holds for some integer $k$. Substitute $d = C - mk$ into $aC \equiv bd \pmod m$:

$$aC \equiv b(C - mk) \pmod m$$

$$aC \equiv bC - bmk \pmod m$$

Since $bmk \equiv 0 \pmod m$, the above equation simplifies to:

$$aC \equiv bC \pmod m$$

This means $m \mid (aC - bC)$, that is $m \mid (a - b)C$.

Because $\gcd(C, m) = 1$, according to Euclid's Lemma, we can get $m \mid (a - b)$. According to the definition of congruence, we have

$$a \equiv b \pmod m$$

In summary, the two congruences are equivalent. Q.E.D.

4

Let prime $p \geqslant 3$, if $a^2 \equiv b^2(\bmod p), p \nmid a$, then $a \equiv b(\bmod p)$ or $a \equiv -b(\bmod p)$ and only one holds.

Proof: From $a^2 \equiv b^2 \pmod p$, we can get $a^2 - b^2 \equiv 0 \pmod p$, that is

$$(a - b)(a + b) \equiv 0 \pmod p$$

Because $p$ is a prime number, according to Euclid's Lemma, we must have $p \mid (a - b)$ or $p \mid (a + b)$.

• If $p \mid (a - b)$, then $a \equiv b \pmod p$.
• If $p \mid (a + b)$, then $a \equiv -b \pmod p$.

Therefore, at least one of $a \equiv b \pmod p$ or $a \equiv -b \pmod p$ holds.

Next prove that only one holds. Assume $a \equiv b \pmod p$ and $a \equiv -b \pmod p$ hold simultaneously. Then $b \equiv -b \pmod p$, that is $2b \equiv 0 \pmod p$. Because $p$ is a prime number and $p \ge 3$, so $\gcd(2, p) = 1$. According to the property of congruence, from $2b \equiv 0 \pmod p$ we can get $b \equiv 0 \pmod p$. Also because $a \equiv b \pmod p$, so $a \equiv 0 \pmod p$, that is $p \mid a$. This contradicts the condition $p \nmid a$.

Therefore, $a \equiv b \pmod p$ and $a \equiv -b \pmod p$ cannot hold simultaneously.

In summary, $a \equiv b \pmod p$ or $a \equiv -b \pmod p$ and only one holds. Q.E.D.

5

Let positive integer

$$a=a_n 10^n+a_{n-1} 10^{n-1}+\cdots+a_0, \quad 0 \leqslant a_i<10$$

Then the necessary and sufficient condition for 11 to divide $a$ is

$$11 \mid \sum_{i=1}^n(-1)^i a_i$$

Proof: Consider the remainder of integer $a$ modulo 11. We note that $10 \equiv -1 \pmod{11}$. According to the property of congruence, for any non-negative integer $i$, we have

$$10^i \equiv (-1)^i \pmod{11}$$

Now consider $a$ modulo 11:

$$\begin{align} a &= a_n 10^n + a_{n-1} 10^{n-1} + \cdots + a_1 10^1 + a_0 \\ &\equiv a_n (-1)^n + a_{n-1} (-1)^{n-1} + \cdots + a_1 (-1)^1 + a_0 (-1)^0 \pmod{11} \\ &\equiv \sum_{i=0}^n a_i (-1)^i \pmod{11} \end{align}$$

Therefore, $a \equiv 0 \pmod{11}$ if and only if $\sum_{i=0}^n (-1)^i a_i \equiv 0 \pmod{11}$.

Q.E.D.

6

Find the criteria for an integer to be divisible by 37, 101.

Solution: Let the decimal representation of integer $N$ be $a_k a_{k-1} \cdots a_1 a_0 = \sum_{i=0}^k a_i 10^i$.

Criterion for divisibility by 37: We note that $1000 = 27 \times 37 + 1$, so $1000 \equiv 1 \pmod{37}$. Group the integer $N$ every three digits from right to left:

$$N = (a_2 a_1 a_0)_{10} + (a_5 a_4 a_3)_{10} \cdot 10^3 + (a_8 a_7 a_6)_{10} \cdot 10^6 + \cdots$$

Let $A_0 = (a_2 a_1 a_0)_{10} = 100a_2 + 10a_1 + a_0$, $A_1 = (a_5 a_4 a_3)_{10} = 100a_5 + 10a_4 + a_3$, and so on. Then $N = A_0 + A_1 \cdot 10^3 + A_2 \cdot (10^3)^2 + \cdots$. Consider $N$ modulo 37:

$$\begin{align} N &\equiv A_0 + A_1 \cdot 1 + A_2 \cdot 1^2 + \cdots \pmod{37} \\ &\equiv A_0 + A_1 + A_2 + \cdots \pmod{37} \end{align}$$

Therefore, a necessary and sufficient condition for an integer to be divisible by 37 is: group it every three digits from right to left, and the sum of the numbers represented by these groups is divisible by 37.

Criterion for divisibility by 101: We note that $100 = 1 \times 101 - 1$, so $100 \equiv -1 \pmod{101}$. Group the integer $N$ every two digits from right to left:

$$N = (a_1 a_0)_{10} + (a_3 a_2)_{10} \cdot 10^2 + (a_5 a_4)_{10} \cdot 10^4 + \cdots$$

Let $B_0 = (a_1 a_0)_{10} = 10a_1 + a_0$, $B_1 = (a_3 a_2)_{10} = 10a_3 + a_2$, and so on. Then $N = B_0 + B_1 \cdot 10^2 + B_2 \cdot (10^2)^2 + \cdots$. Consider $N$ modulo 101:

$$\begin{align} N &\equiv B_0 + B_1 \cdot (-1) + B_2 \cdot (-1)^2 + B_3 \cdot (-1)^3 + \cdots \pmod{101} \\ &\equiv B_0 - B_1 + B_2 - B_3 + \cdots \pmod{101} \end{align}$$

Therefore, a necessary and sufficient condition for an integer to be divisible by 101 is: group it every two digits from right to left, and the alternating sum of the numbers represented by these groups (from right to left, signs are $+ - + - \cdots$) is divisible by 101.

7

Prove: $641 \mid\left(2^{32}+1\right)$.

Proof:

Note that $641 = 5 \cdot 2^7 + 1 = 5^4 + 2^4$.

From $641 = 5 \cdot 2^7 + 1$, we get

$$5 \cdot 2^7 \equiv -1 \pmod{641}$$

Take the 4th power on both sides, we get

$$(5 \cdot 2^7)^4 \equiv (-1)^4 \pmod{641}$$

$$5^4 \cdot 2^{28} \equiv 1 \pmod{641}$$

Also from $641 = 5^4 + 2^4$, we get

$$5^4 \equiv -2^4 \pmod{641}$$

Substitute into the above equation, we get

$$(-2^4) \cdot 2^{28} \equiv 1 \pmod{641}$$

$$-2^{32} \equiv 1 \pmod{641}$$

That is

$$2^{32} \equiv -1 \pmod{641}$$

Therefore, $2^{32} + 1 \equiv 0 \pmod{641}$, i.e., $641 \mid (2^{32}+1)$.

8

If $a$ is an odd number, then $a^{2^n} \equiv 1\left(\bmod 2^{n+2}\right), \quad n \geqslant 1$.

Proof:

Prove by mathematical induction.

Base case: When $n=1$, need to prove $a^{2^1} \equiv 1 \pmod{2^{1+2}}$, i.e., $a^2 \equiv 1 \pmod 8$.

Because $a$ is an odd number, let $a=2k+1$, where $k$ is an integer.

$$a^2 = (2k+1)^2 = 4k^2+4k+1 = 4k(k+1)+1$$

Since $k(k+1)$ must be even, let $k(k+1)=2j$, where $j$ is an integer. Then $a^2 = 4(2j)+1 = 8j+1 \equiv 1 \pmod 8$.

So the proposition holds when $n=1$.

Inductive step: Assume the proposition holds when $n=k$ ($k \ge 1$), i.e., $a^{2^k} \equiv 1 \pmod{2^{k+2}}$.

This means there exists an integer $c$ such that $a^{2^k} = 1 + c \cdot 2^{k+2}$.

Need to prove that the proposition also holds when $n=k+1$, i.e., $a^{2^{k+1}} \equiv 1 \pmod{2^{(k+1)+2}}$, i.e., $a^{2^{k+1}} \equiv 1 \pmod{2^{k+3}}$.

$$\begin{align} a^{2^{k+1}} &= (a^{2^k})^2 \\ &= (1 + c \cdot 2^{k+2})^2 \\ &= 1 + 2 \cdot (c \cdot 2^{k+2}) + (c \cdot 2^{k+2})^2 \\ &= 1 + c \cdot 2^{k+3} + c^2 \cdot 2^{2(k+2)} \\ &= 1 + c \cdot 2^{k+3} + c^2 \cdot 2^{2k+4} \end{align}$$

Because $k \ge 1$, so $2k+4 = (k+3) + (k+1) \ge k+3+2 = k+5$.

Therefore $2^{k+3} \mid c^2 \cdot 2^{2k+4}$.

So

$$a^{2^{k+1}} \equiv 1 + c \cdot 2^{k+3} \pmod{2^{k+3}}$$

$$a^{2^{k+1}} \equiv 1 \pmod{2^{k+3}}$$

The proposition holds when $n=k+1$.

By the principle of mathematical induction, the original proposition holds for all $n \ge 1$.

9

Prove:

$$x=u+p^{s-t} v, \quad u=0,1,2, \cdots, p^{s-t}-1, \quad v=0,1,2, \cdots, p^t-1, \quad t \leqslant s$$

is a complete residue system modulo $p^s$ ($p$ is a prime number).

Proof:

First, calculate the number of possible values of $x$.

$u$ has $p^{s-t}$ possible values. $v$ has $p^t$ possible values.

Therefore, the total number of possible values of $x$ is $p^{s-t} \cdot p^t = p^s$. This is the same as the number of elements in the complete residue system modulo $p^s$.

Next, prove that these values are pairwise incongruent modulo $p^s$.

Assume there exist two sets $(u_1, v_1)$ and $(u_2, v_2)$, where $0 \le u_1, u_2 < p^{s-t}$ and $0 \le v_1, v_2 < p^t$, such that

$$u_1 + p^{s-t} v_1 \equiv u_2 + p^{s-t} v_2 \pmod{p^s}$$

This means

$$(u_1 - u_2) + p^{s-t} (v_1 - v_2) \equiv 0 \pmod{p^s}$$

From this we know $p^s \mid (u_1 - u_2) + p^{s-t} (v_1 - v_2)$.

This also means

$$(u_1 - u_2) + p^{s-t} (v_1 - v_2) \equiv 0 \pmod{p^{s-t}}$$

Because $p^{s-t} (v_1 - v_2) \equiv 0 \pmod{p^{s-t}}$, so

$$u_1 - u_2 \equiv 0 \pmod{p^{s-t}}$$

That is $p^{s-t} \mid (u_1 - u_2)$.

Also because $0 \le u_1, u_2 < p^{s-t}$, so $-(p^{s-t}) < u_1 - u_2 < p^{s-t}$.

The only possibility satisfying $p^{s-t} \mid (u_1 - u_2)$ is $u_1 - u_2 = 0$, i.e., $u_1 = u_2$.

Substitute $u_1 = u_2$ into the original congruence $(u_1 - u_2) + p^{s-t} (v_1 - v_2) \equiv 0 \pmod{p^s}$, we get

$$p^{s-t} (v_1 - v_2) \equiv 0 \pmod{p^s}$$

This means there exists an integer $k$ such that $p^{s-t} (v_1 - v_2) = k \cdot p^s$.

Divide both sides by $p^{s-t}$ (since $t \le s$, $s-t \ge 0$), we get

$$v_1 - v_2 = k \cdot p^s / p^{s-t} = k \cdot p^t$$

This means $p^t \mid (v_1 - v_2)$.

Also because $0 \le v_1, v_2 < p^t$, so $-p^t < v_1 - v_2 < p^t$.

The only possibility satisfying $p^t \mid (v_1 - v_2)$ is $v_1 - v_2 = 0$, i.e., $v_1 = v_2$.

Therefore, if $u_1 + p^{s-t} v_1 \equiv u_2 + p^{s-t} v_2 \pmod{p^s}$, then we must have $u_1 = u_2$ and $v_1 = v_2$.

This shows that the $p^s$ numbers in this set are pairwise incongruent modulo $p^s$.

In summary, this set constitutes a complete residue system modulo $p^s$.

10

1. If $2 \nmid m$, then $2,4,6, \cdots, 2 m$ is a complete residue system modulo $m$;
2. If $m>2$, then $1^2, 2^2, 3^2, \cdots, m^2$ is not a complete residue system modulo $m$.

Proof:

1. The set is $S = \{2k \mid 1 \le k \le m\}$. This set contains $m$ integers.

We need to prove that these $m$ integers are pairwise incongruent modulo $m$.

Assume there exist $1 \le k_1, k_2 \le m$ such that $2k_1 \equiv 2k_2 \pmod m$.

Then $m \mid (2k_1 - 2k_2)$, i.e., $m \mid 2(k_1 - k_2)$.

Because $m$ is odd, $\gcd(2, m) = 1$.

According to the property of congruence, factor 2 can be cancelled, getting

$$k_1 \equiv k_2 \pmod m$$

That is $m \mid (k_1 - k_2)$.

Also because $1 \le k_1, k_2 \le m$, so $|k_1 - k_2| < m$.

The only possibility satisfying $m \mid (k_1 - k_2)$ is $k_1 - k_2 = 0$, i.e., $k_1 = k_2$.

Therefore, the $m$ integers in set $S$ are pairwise incongruent modulo $m$.

Since the set size is $m$, it constitutes a complete residue system modulo $m$.

2. Consider the set $T = \{k^2 \mid 1 \le k \le m\}$.

We need to prove that when $m>2$, the numbers in this set are not pairwise incongruent modulo $m$.

Consider $k=1$ and $k=m-1$. Because $m>2$, so $m-1 \ge 2$, and $1 \ne m-1$. They are both distinct elements in $\{1, 2, \dots, m\}$.

Calculate their squares modulo $m$:

$$1^2 = 1 \equiv 1 \pmod m$$

$$(m-1)^2 = m^2 - 2m + 1$$

Because $m^2 \equiv 0 \pmod m$ and $-2m \equiv 0 \pmod m$, so

$$(m-1)^2 \equiv 0 - 0 + 1 \equiv 1 \pmod m$$

Therefore, we found two distinct integers $1$ and $m-1$ ($1 \le 1, m-1 \le m$) whose squares are congruent modulo $m$.

This means that at least two elements in set $T$ are the same (modulo $m$), so it cannot contain $m$ pairwise incongruent numbers.

So $1^2, 2^2, \cdots, m^2$ is not a complete residue system modulo $m$.

11

If $m_1, m_2, \cdots, m_k$ are pairwise coprime, $x_1, x_2, \cdots, x_k$ pass through the complete residue systems modulo $m_1, m_2, \cdots, m_k$ respectively, then

$$x = x_1+m_1 x_2+m_1 m_2 x_3+\cdots+m_1 m_2 \cdots m_{k-1} x_k$$

passes through the complete residue system modulo $m_1 m_2 \cdots m_k$.

Proof:

Let $M = m_1 m_2 \cdots m_k$.

First, calculate the number of possible values of $x$.

$x_1$ has $m_1$ possible values. $x_2$ has $m_2$ possible values. ... $x_k$ has $m_k$ possible values.

Since the choices of $x_i$ are independent, the total number of values of $x$ is $m_1 m_2 \cdots m_k = M$. This is the same as the number of elements in the complete residue system modulo $M$.

Next, prove that these values are pairwise incongruent modulo $M$.

Assume there exist two sets $(x_1, x_2, \dots, x_k)$ and $(x'_1, x'_2, \dots, x'_k)$, where $x_i, x'_i$ are representatives of the complete residue system modulo $m_i$ respectively, such that

$$x_1+m_1 x_2+m_1 m_2 x_3+\cdots+m_1 \cdots m_{k-1} x_k \equiv x'_1+m_1 x'_2+m_1 m_2 x'_3+\cdots+m_1 \cdots m_{k-1} x'_k \pmod M$$

Denote this congruence as $(*)$.

Because $m_1 \mid M$, the above congruence also implies congruence modulo $m_1$:

$$x_1+m_1 x_2+\cdots+m_1 \cdots m_{k-1} x_k \equiv x'_1+m_1 x'_2+\cdots+m_1 \cdots m_{k-1} x'_k \pmod{m_1}$$

Since $m_1 x_2, m_1 m_2 x_3, \dots$ are all multiples of $m_1$, they are all congruent to 0 modulo $m_1$.

So $x_1 \equiv x'_1 \pmod{m_1}$.

Because $x_1, x'_1$ both come from a complete residue system modulo $m_1$, so $x_1 = x'_1$.

Substitute $x_1 = x'_1$ into $(*)$ and cancel, we get

$$m_1 x_2+m_1 m_2 x_3+\cdots+m_1 \cdots m_{k-1} x_k \equiv m_1 x'_2+m_1 m_2 x'_3+\cdots+m_1 \cdots m_{k-1} x'_k \pmod M$$

Divide both sides by $m_1$ (this is allowed because $M = m_1 (m_2 \cdots m_k)$), we get

$$x_2+m_2 x_3+\cdots+m_2 \cdots m_{k-1} x_k \equiv x'_2+m_2 x'_3+\cdots+m_2 \cdots m_{k-1} x'_k \pmod{m_2 \cdots m_k}$$

Denote this congruence as $(**)$.

Because $m_2 \mid (m_2 \cdots m_k)$, the above congruence also implies congruence modulo $m_2$:

$$x_2 + m_2 x_3 + \dots \equiv x'_2 + m_2 x'_3 + \dots \pmod{m_2}$$

$$x_2 \equiv x'_2 \pmod{m_2}$$

Because $x_2, x'_2$ both come from a complete residue system modulo $m_2$, so $x_2 = x'_2$.

We can continue this process. Assume we have proved $x_1 = x'_1, x_2 = x'_2, \dots, x_{j-1} = x'_{j-1}$.

Substitute these into $(*)$ and cancel the corresponding terms, then divide both sides by $m_1 m_2 \cdots m_{j-1}$, we get

$$x_j+m_j x_{j+1}+\cdots+m_j \cdots m_{k-1} x_k \equiv x'_j+m_j x'_{j+1}+\cdots+m_j \cdots m_{k-1} x'_k \pmod{m_j m_{j+1} \cdots m_k}$$

Consider modulo $m_j$, we get

$$x_j \equiv x'_j \pmod{m_j}$$

Because $x_j, x'_j$ both come from a complete residue system modulo $m_j$, so $x_j = x'_j$.

By induction, we can prove that for all $j=1, 2, \dots, k$, we have $x_j = x'_j$.

Therefore, if two $x$ values are congruent modulo $M$, they must be generated by exactly the same $(x_1, \dots, x_k)$ sequence.

This proves that the $M$ $x$ values generated by different sequences are pairwise incongruent modulo $M$.

In summary, these $x$ values constitute a complete residue system modulo $M$.

13

(1) Find the last digit of $3^{400}$; (2) Find the remainder of $\left(12371^{56}+34\right)^{28}$ divided by 111.

Solution:

(1) $3^{400} \equiv 3^{4 \times 100} \equiv (3^4)^{100} \equiv 1^{100} \equiv 1 \pmod{10}$

So its last digit is 1.

(2) Note that $12371 \equiv 111^2 + 50$, so

$$12371 \equiv 50 \pmod{111}$$

So

$$(12371^{56} + 34)^{28} \equiv (50^{56} + 34)^{28} \pmod{111}$$

We have

$$\begin{align} 50^2 &\equiv 58 \pmod{111}\\ 50^4 &\equiv 34 \pmod{111}\\ 50^8 &\equiv 46 \pmod{111}\\ 50^{16} &\equiv 7 \pmod{111}\\ 50^{32} &\equiv 49 \pmod{111} \end{align}$$

Therefore

$$50^{56} \equiv 50^{32} \times 50^{16} \times 50^8 \equiv 16 \pmod{111}$$

Thus

$$(50^{56} + 34)^{28} \equiv 50^{28} \pmod{111}$$

And

$$50^{28} \equiv 50^{16} \times 50^8 \times 50^4 \equiv 70 \pmod{111}$$

In summary, the remainder is 70.

14

(1) Find the last two digits of $3^{400}$; (2) Find the last two digits of $9^{9^9}$.

Solution:

(1) $\phi(100) = \phi(2^2 \times 5^2) = \phi(2^2) \phi(5^2) = (4-2) \times (25-5) = 40$

From Euler's Theorem we know

$$3^{\phi(100)} = 3^{40} \equiv 1 \pmod{100}$$

Thus

$$3^{400} \equiv (3^{40})^{10} \equiv 1 \pmod{100}$$

So its last two digits are 01.

(2) We have

$$9^9 \equiv 9^{2 \times 4+1} \equiv (9^2)^4 \times 9 \equiv (1)^4 \times 9 \equiv 9 \pmod{40}$$

From Euler's Theorem we know

$$9^{\phi(100)} = 9^{40} \equiv 1 \pmod{100}$$

Therefore

$$9^{9^9} \equiv 9^9 \pmod{100}$$

Perform Euclidean algorithm on 9, 100, we have

$$9^{-1} \equiv 89 \pmod{100}$$

And

$$9^9 \times 9 = 9^{10} \equiv 1 \pmod{100}$$

So

$$9^9 \equiv 9^{-1} \equiv 89 \pmod{100}$$

In summary, its last two digits are 89.

21

For what value of $a$ does $x^3 \equiv a(\bmod 9)$ have a solution.

Solution: Traverse $\mathbb{Z} / 9 \mathbb{Z},$ the equation has a solution if and only if $a \equiv 0, 1, 8 \pmod{9}$.

22

Determine whether the following congruence equations have solutions, and if so, find their solutions:

1. $20 x \equiv 4(\bmod 30)$;
2. $15 x \equiv 25(\bmod 35)$;
3. $15 x \equiv 0(\bmod 35)$.

Solution:

The linear congruence equation $ax \equiv b \pmod m$ has a solution if and only if $\gcd(a, m) \mid b$. If there is a solution, there are exactly $\gcd(a, m)$ incongruent solutions modulo $m$.

1. $20 x \equiv 4 \pmod{30}$.

Calculate $\gcd(20, 30) = 10$.

Because $10 \nmid 4$, the congruence equation has no solution.

2. $15 x \equiv 25 \pmod{35}$.

Calculate $\gcd (15, 35) = 5$.

Because $5 \mid 25$, the congruence equation has a solution, and there are exactly 5 incongruent solutions modulo 35.

The original equation is equivalent to $15 x = 25 + 35 k$ for some integer $k$.

Divide both sides by $\gcd (15, 35)=5$:

$$3 x \equiv 5 \pmod{7}$$

To solve this equation, we need to find the inverse of 3 modulo 7.

Observation shows $3 \times 5 = 15 \equiv 1 \pmod 7$. So the inverse of 3 is 5.

Multiply both sides of the above congruence by 5:

$$5 \cdot (3 x) \equiv 5 \cdot 5 \pmod 7$$

$$15 x \equiv 25 \pmod 7$$

$$x \equiv 4 \pmod 7$$

So the form of the solution is $x = 4 + 7 t$, where $t$ is an integer.

These solutions modulo 35 are: When $t=0$, $x = 4$. When $t=1$, $x = 4 + 7 = 11$. When $t=2$, $x = 4 + 14 = 18$. When $t=3$, $x = 4 + 21 = 25$. When $t=4$, $x = 4 + 28 = 32$. When $t=5$, $x = 4 + 35 = 39 \equiv 4 \pmod{35}$, start repeating.

Therefore, the solutions are $x \equiv 4, 11, 18, 25, 32 \pmod{35}$.

3. $15 x \equiv 0 \pmod{35}$.

Calculate $\gcd (15, 35) = 5$.

Because $5 \mid 0$, the congruence equation has a solution, and there are exactly 5 incongruent solutions modulo 35.

The original equation is equivalent to $15 x = 35 k$ for some integer $k$.

Divide both sides by $\gcd (15, 35)=5$:

$$3 x \equiv 0 \pmod{7}$$

Because $\gcd (3, 7) = 1$, we can cancel 3, getting:

$$x \equiv 0 \pmod 7$$

So the form of the solution is $x = 7 t$, where $t$ is an integer.

These solutions modulo 35 are: When $t=0$, $x = 0$. When $t=1$, $x = 7$. When $t=2$, $x = 14$. When $t=3$, $x = 21$. When $t=4$, $x = 28$. When $t=5$, $x = 35 \equiv 0 \pmod{35}$, start repeating.

Therefore, the solutions are $x \equiv 0, 7, 14, 21, 28 \pmod{35}$.

23

Solve the system of linear congruence equations in two variables

$$\left\{\begin{aligned} x+4 y-29 & \equiv 0 (\bmod 143) \\ 2 x-9 y+84 & \equiv 0 (\bmod 143) \end{aligned}\right.$$

Solution:

Write the system of equations in standard form:

$$\left\{\begin{aligned} x+4 y & \equiv 29 \pmod{143} \quad &(1) \\ 2 x-9 y & \equiv -84 \pmod{143} \quad &(2) \end{aligned}\right.$$

Note that $143 = 11 \times 13$.

We can use the elimination method. Multiply equation (1) by 2:

$$2 x + 8 y \equiv 58 \pmod{143} \quad (3)$$

Subtract equation (2) from equation (3):

$$(2 x + 8 y) - (2 x - 9 y) \equiv 58 - (-84) \pmod{143}$$

$$17 y \equiv 142 \pmod{143}$$

Because $142 \equiv -1 \pmod{143}$, so

$$17 y \equiv -1 \pmod{143}$$

We need to solve this linear congruence equation for $y$. First calculate $\gcd (17, 143)$.

Because $143 = 11 \times 13$, 17 is a prime number, and $17 \ne 11, 17 \ne 13$, so $\gcd (17, 143) = 1$.

This guarantees that the equation has a unique solution. We need to find the inverse of 17 modulo 143.

Use the extended Euclidean algorithm:

$$\begin{align} 143 &= 8 \times 17 + 7 \\ 17 &= 2 \times 7 + 3 \\ 7 &= 2 \times 3 + 1 \end{align}$$

Now substitute back:

$$\begin{align} 1 &= 7 - 2 \times 3 \\ &= 7 - 2 \times (17 - 2 \times 7) \\ &= 7 - 2 \times 17 + 4 \times 7 \\ &= 5 \times 7 - 2 \times 17 \\ &= 5 \times (143 - 8 \times 17) - 2 \times 17 \\ &= 5 \times 143 - 40 \times 17 - 2 \times 17 \\ &= 5 \times 143 - 42 \times 17 \end{align}$$

From $5 \times 143 - 42 \times 17 = 1$, we get $-42 \times 17 \equiv 1 \pmod{143}$.

So the inverse of 17 modulo 143 is $-42 \equiv -42 + 143 = 101 \pmod{143}$.

Multiply both sides of $17 y \equiv -1 \pmod{143}$ by 101:

$$101 \cdot (17 y) \equiv 101 \cdot (-1) \pmod{143}$$

$$y \equiv -101 \pmod{143}$$

$$y \equiv -101 + 143 \equiv 42 \pmod{143}$$

Substitute $y=42$ into equation (1):

$$x + 4 (42) \equiv 29 \pmod{143}$$

$$x + 168 \equiv 29 \pmod{143}$$

Because $168 = 143 + 25 \equiv 25 \pmod{143}$, so

$$x + 25 \equiv 29 \pmod{143}$$

$$x \equiv 29 - 25 \pmod{143}$$

$$x \equiv 4 \pmod{143}$$

Therefore, the solution of the system of equations is $x \equiv 4 \pmod{143}$, $y \equiv 42 \pmod{143}$.

25

Determine whether the following systems of congruence equations have solutions, and if so, find their solutions:

1. $x \equiv 1 (\bmod 4), \quad x \equiv 0 (\bmod 3), \quad x \equiv 5 (\bmod 7)$;
2. $x \equiv 2 (\bmod 4), \quad x \equiv 7 (\bmod 10), \quad x \equiv 1 (\bmod 3)$;
3. $x \equiv 2 (\bmod 3), \quad x \equiv 3 (\bmod 5), \quad x \equiv 5 (\bmod 2)$;
4. $x \equiv 3 (\bmod 8), \quad x \equiv 11 (\bmod 20), \quad x \equiv 1 (\bmod 15)$.

Solution:

Use the Chinese Remainder Theorem (CRT). If the moduli are not coprime, check compatibility first.

1. $x \equiv 1 \pmod 4$, $x \equiv 0 \pmod 3$, $x \equiv 5 \pmod 7$.

Moduli $m_1=4, m_2=3, m_3=7$ are pairwise coprime. So there is a unique solution modulo $M = 4 \times 3 \times 7 = 84$.

$M_1 = M/m_1 = 84/4 = 21$. Solve $M_1 y_1 \equiv 1 \pmod{m_1}$, i.e., $21 y_1 \equiv 1 \pmod 4 \implies y_1 \equiv 1 \pmod 4$. Take $y_1=1$.

$M_2 = M/m_2 = 84/3 = 28$. Solve $M_2 y_2 \equiv 1 \pmod{m_2}$, i.e., $28 y_2 \equiv 1 \pmod 3 \implies y_2 \equiv 1 \pmod 3$. Take $y_2=1$.

$M_3 = M/m_3 = 84/7 = 12$. Solve $M_3 y_3 \equiv 1 \pmod{m_3}$, i.e., $12 y_3 \equiv 1 \pmod 7 \implies 5 y_3 \equiv 1 \pmod 7$. Because $5 \times 3 = 15 \equiv 1 \pmod 7$, take $y_3=3$.

According to CRT, the solution is $x = a_1 M_1 y_1 + a_2 M_2 y_2 + a_3 M_3 y_3 \pmod M$.

$$x \equiv 1 \cdot 21 \cdot 1 + 0 \cdot 28 \cdot 1 + 5 \cdot 12 \cdot 3 \pmod{84}$$

$$x \equiv 21 + 0 + 180 \pmod{84}$$

$$x \equiv 201 \pmod{84}$$

Because $201 = 2 \times 84 + 33$, so $x \equiv 33 \pmod{84}$.

2. $x \equiv 2 \pmod 4$, $x \equiv 7 \pmod{10}$, $x \equiv 1 \pmod 3$.

Moduli 4 and 10 are not coprime, $\gcd (4, 10) = 2$. Need to check compatibility.

$x \equiv 2 \pmod 4 \implies x$ is even. $x \equiv 7 \pmod{10}$. Consider modulo 2: $x \equiv 7 \equiv 1 \pmod 2 \implies x$ is odd.

A number cannot be both odd and even. These two conditions contradict.

Therefore, the system of congruence equations has no solution.

3. $x \equiv 2 \pmod 3$, $x \equiv 3 \pmod 5$, $x \equiv 5 \pmod 2$.

The last congruence can be simplified to $x \equiv 1 \pmod 2$.

The system is $x \equiv 2 \pmod 3$, $x \equiv 3 \pmod 5$, $x \equiv 1 \pmod 2$.

Moduli $m_1=3, m_2=5, m_3=2$ are pairwise coprime. So there is a unique solution modulo $M = 3 \times 5 \times 2 = 30$.

$M_1 = M/m_1 = 30/3 = 10$. Solve $10 y_1 \equiv 1 \pmod 3 \implies y_1 \equiv 1 \pmod 3$. Take $y_1=1$.

$M_2 = M/m_2 = 30/5 = 6$. Solve $6 y_2 \equiv 1 \pmod 5 \implies y_2 \equiv 1 \pmod 5$. Take $y_2=1$.

$M_3 = M/m_3 = 30/2 = 15$. Solve $15 y_3 \equiv 1 \pmod 2 \implies y_3 \equiv 1 \pmod 2$. Take $y_3=1$.

The solution is $x = a_1 M_1 y_1 + a_2 M_2 y_2 + a_3 M_3 y_3 \pmod M$.

$$x \equiv 2 \cdot 10 \cdot 1 + 3 \cdot 6 \cdot 1 + 1 \cdot 15 \cdot 1 \pmod{30}$$

$$x \equiv 20 + 18 + 15 \pmod{30}$$

$$x \equiv 53 \pmod{30}$$

Because $53 = 1 \times 30 + 23$, so $x \equiv 23 \pmod{30}$.

4. $x \equiv 3 \pmod 8$, $x \equiv 11 \pmod{20}$, $x \equiv 1 \pmod{15}$.

Moduli 8, 20, 15 are not pairwise coprime. $\gcd (8, 20)=4$, $\gcd (8, 15)=1$, $\gcd (20, 15)=5$.

Need to check compatibility.

Check $\gcd (8, 20)=4$ from $x \equiv 3 \pmod 8$ and $x \equiv 11 \pmod{20}$. $x \equiv 3 \pmod 8 \implies x \equiv 3 \pmod 4$. $x \equiv 11 \pmod{20} \implies x \equiv 11 \equiv 3 \pmod 4$. These two conditions are compatible.

Check $\gcd (20, 15)=5$ from $x \equiv 11 \pmod{20}$ and $x \equiv 1 \pmod{15}$. $x \equiv 11 \pmod{20} \implies x \equiv 11 \equiv 1 \pmod 5$. $x \equiv 1 \pmod{15} \implies x \equiv 1 \pmod 5$. These two conditions are compatible.

Check $\gcd (8, 15)=1$ from $x \equiv 3 \pmod 8$ and $x \equiv 1 \pmod{15}$. Automatically compatible.

Because all conditions are compatible, the system of equations has a solution.

We can decompose the original system of equations into moduli of prime powers: $x \equiv 3 \pmod 8$$x \equiv 11 \pmod{20} \implies x \equiv 11 \pmod 4$ (already included in $x \equiv 3 \pmod 8$) and $x \equiv 11 \pmod 5 \implies x \equiv 1 \pmod 5$. $x \equiv 1 \pmod{15} \implies x \equiv 1 \pmod 3$ and $x \equiv 1 \pmod 5$ (already exists).

The simplified equivalent system of equations is: $x \equiv 3 \pmod 8$$x \equiv 1 \pmod 3$$x \equiv 1 \pmod 5$

Moduli $m_1=8, m_2=3, m_3=5$ are pairwise coprime. There is a unique solution modulo $M = 8 \times 3 \times 5 = 120$.

$M_1 = M/m_1 = 120/8 = 15$. Solve $15 y_1 \equiv 1 \pmod 8 \implies -y_1 \equiv 1 \pmod 8 \implies y_1 \equiv -1 \equiv 7 \pmod 8$. Take $y_1=7$.

$M_2 = M/m_2 = 120/3 = 40$. Solve $40 y_2 \equiv 1 \pmod 3 \implies y_2 \equiv 1 \pmod 3$. Take $y_2=1$.

$M_3 = M/m_3 = 120/5 = 24$. Solve $24 y_3 \equiv 1 \pmod 5 \implies 4 y_3 \equiv 1 \pmod 5 \implies -y_3 \equiv 1 \pmod 5 \implies y_3 \equiv -1 \equiv 4 \pmod 5$. Take $y_3=4$.

The solution is $x = a_1 M_1 y_1 + a_2 M_2 y_2 + a_3 M_3 y_3 \pmod M$.

$$x \equiv 3 \cdot 15 \cdot 7 + 1 \cdot 40 \cdot 1 + 1 \cdot 24 \cdot 4 \pmod{120}$$

$$x \equiv 315 + 40 + 96 \pmod{120}$$

$$x \equiv 451 \pmod{120}$$

Because $451 = 3 \times 120 + 91$, so $x \equiv 91 \pmod{120}$.

27

Solve the system of congruence equations:

$$2 x \equiv 3 (\bmod 5), \quad 3 x \equiv 1 (\bmod 7).$$

Solution:

First solve each linear congruence equation separately.

First equation: $2 x \equiv 3 \pmod 5$.

We need to find the inverse of 2 modulo 5. $2 \times 3 = 6 \equiv 1 \pmod 5$. The inverse is 3.

Multiply both sides of the equation by 3:

$$3 \cdot (2 x) \equiv 3 \cdot 3 \pmod 5$$

$$6 x \equiv 9 \pmod 5$$

$$x \equiv 4 \pmod 5$$

Second equation: $3 x \equiv 1 \pmod 7$.

We need to find the inverse of 3 modulo 7. $3 \times 5 = 15 \equiv 1 \pmod 7$. The inverse is 5.

Multiply both sides of the equation by 5:

$$5 \cdot (3 x) \equiv 5 \cdot 1 \pmod 7$$

$$15 x \equiv 5 \pmod 7$$

$$x \equiv 5 \pmod 7$$

Now we need to solve the simultaneous system of equations:

$$\left\{\begin{aligned} x & \equiv 4 \pmod 5 \\ x & \equiv 5 \pmod 7 \end{aligned}\right.$$

Moduli $m_1=5, m_2=7$ are coprime. There is a unique solution modulo $M = 5 \times 7 = 35$.

$M_1 = M/m_1 = 35/5 = 7$. Solve $7 y_1 \equiv 1 \pmod 5 \implies 2 y_1 \equiv 1 \pmod 5$. The inverse is 3, so $y_1=3$.

$M_2 = M/m_2 = 35/7 = 5$. Solve $5 y_2 \equiv 1 \pmod 7$. The inverse is 3 ($5 \times 3 = 15 \equiv 1 \pmod 7$), so $y_2=3$.

According to CRT, the solution is $x = a_1 M_1 y_1 + a_2 M_2 y_2 \pmod M$.

$$x \equiv 4 \cdot 7 \cdot 3 + 5 \cdot 5 \cdot 3 \pmod{35}$$

$$x \equiv 84 + 75 \pmod{35}$$

$$x \equiv 159 \pmod{35}$$

Because $159 = 4 \times 35 + 19$, so $159 \equiv 19 \pmod{35}$.

Therefore, the solution of the system of equations is $x \equiv 19 \pmod{35}$.

28

Let $m_1, m_2, \cdots, m_K$ be pairwise coprime, then the necessary and sufficient condition for the system of congruence equations $a_i x \equiv b_i\left (\bmod m_i\right), 1 \leqslant i \leqslant K$ to have a solution is that each congruence equation $a_i x \equiv b_i\left (\bmod m_i\right)$ is solvable.

Proof: Necessity is obvious, prove sufficiency below.

Assume $a_i x \equiv b_i \pmod{m_i}, 1 \leq i \leq k$ are solvable, then

$$(a_i, m_i) \mid b_i$$

Let $d_i = (a_i, m_i)$, $a_i' = \frac{a_i}{d_i}$, $b_i' = \frac{b_i}{d_i}$, $m_i' = \frac{m_i}{d_i}$.

Then we have

$$a_i x \equiv b_i \pmod{m_i} \Leftrightarrow a_i' x \equiv b_i' \pmod{m_i'}$$

Since $(a_i', m_i') = 1$, the equation has a unique solution

$$x \equiv x_{i, 0} \pmod{m_i'}$$

Therefore, the original system of congruence equations is equivalent to

$$\begin{cases} x \equiv x_{1,0} \pmod{m_1'} \\ x \equiv x_{2,0} \pmod{m_2'} \\ \cdots \\ x \equiv x_{k, 0} \pmod{m_k'} \end{cases}$$

For $i, j \in \{1, 2, \cdots, k\}; i \neq j$, take prime $p \mid (m_i', m_j')$, then $p \mid m_i$ and $p \mid m_j$, but $(m_i, m_j) = 1$. So $p$ does not exist.

Therefore

$$(m_i', m_j') = 1, 1 \leq i \neq j \leq k$$

By the Chinese Remainder Theorem, the system of congruence equations has a solution.

29

Let $(a, b)=1, C>0$, prove that there must exist an integer $x$ such that $(a+b x, C)=1$.

Proof: Perform prime factorization on $C$

$$C = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$$

Construct the following system of congruence equations

$$x \equiv d_i \pmod{p_i}, i=1,2,\cdots, k$$

Where,

$$d_i = \begin{cases} 0, & p_i \nmid b \\ -a b^{-1} + 1 \pmod{p_i}, & p_i \mid b \end{cases}$$

Since $p_1, p_2, \cdots, p_k$ are pairwise coprime, by the Chinese Remainder Theorem, it has a unique solution $x_0$.

From the construction of the system of equations, we know

$$a + b x_0 \not\equiv 0 \pmod{p_i}, i=1,2,\cdots, k$$

Therefore

$$(a + b x_0, C) = 1$$

References

• https://zhuanlan.zhihu.com/p/543010816

• https://zhuanlan.zhihu.com/p/544792225

• https://zhuanlan.zhihu.com/p/545595129

• https://zhuanlan.zhihu.com/p/546385318

• https://zhuanlan.zhihu.com/p/547333984

• https://zhuanlan.zhihu.com/p/548061254

Contributors: Ming Wei

Previous pagePDF File Automatically Generate Directory Bookmarks

Next pagePan Chengdong "Number Theory Foundation" Selected Solutions: Chapter 3