思考的乐趣第二季第005课：质数、合数与整除

什么是质数？ / What is a Prime Number?

质数是指大于\(1\)的、能且只能被\(1\)和它本身整除的自然数。换句话说，质数没有其他的因子。

Prime numbers are natural numbers greater than \(1\) that can only be divided by \(1\) and themselves. In other words, prime numbers have no other factors.

什么是因子？ What's a factor?

因子是指能够整除给定数的自然数。例如，\(6\) 的因子有 \(1, 2, 3, 6\)。

A factor is a natural number that divides a given number exactly. For example, the factors of \(6\) are \(1, 2, 3, 6\).

什么是合数？ / What is a Composite Number?

合数是指大于 \(1\) 的自然数，除了 \(1\) 和它本身外，还能被其他自然数整除。

Composite numbers are natural numbers greater than 1 that can be divided by numbers other than 1 and themselves.

合数的例子 / Examples of Composite Numbers

以下是一些合数及其因数：

\(4\): \(1, 2, 4\)
\(26\): \(1, 2, 13, 26\)
\(36\): \(1, 2, 3, 4, 6, 9, 12, 18, 36\)
\(54\): \(1, 2, 3, 6, 9, 18, 27, 54\)
\(60\): \(1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60\)

埃拉托斯特尼筛法 / Sieve of Eratosthenes

埃拉托斯特尼（约公元前276—前194）是古希腊学者，以测地球周长闻名。他提出了一种寻找质数的系统方法，即“筛法”。思想简单：从最小的质数 \(2\) 开始，依次把它的倍数划去；然后找到下一个未被划去的数 \(3\)，继续划去它的倍数；不断重复，剩下的数就是质数。

Eratosthenes (c. 276–194 BCE), also known for measuring Earth’s circumference, introduced a systematic way to find prime numbers—the “sieve.” Start with the smallest prime \(2\), cross out its multiples, then move to the next uncrossed number \(3\) and cross out its multiples, and so on. The numbers that remain unmarked are precisely the primes.

质数的分布 / Distribution of Prime Numbers

质数的分布并不均匀，随着数字的增大，质数的间隔似乎在增加。让我们一起观察一下这种分布情况。

The distribution of prime numbers is not uniform; as numbers get larger, the gaps between primes seem to increase. Let’s take a look at this distribution.

算术基本定理 / Fundamental Theorem of Arithmetic

算术基本定理的表述如下：

每个大于\(1\)的整数 \(N\) 要么是质数，要么可以唯一地表示为质数的乘积（不考虑乘积的顺序）。

\[ N = p_1^{k_1} p_2^{k_2} \ldots p_m^{k_m} \]

举例来看, for example:

\(12 = 2^2 \times 3^1\)
\(30 = 2^1 \times 3^1 \times 5^1\)
\(2,232 = 2^3 \times 3^2 \times 31^1\)

The Fundamental Theorem of Arithmetic states that

Every integer \(N\) greater than 1 is either a prime number itself or can be uniquely represented as a product of prime numbers (up to the order of the factors).

\[ N = p_1^{k_1} p_2^{k_2} \ldots p_m^{k_m} \]

为什么1不是质数 / Why 1 is Not a Prime Number

在历史上，\(1\) 确实曾被认为是质数，但现代数学对质数的定义要求其有且仅有两个正因数：1 和它本身。这一调整和算术基本定理的表述密切相关。

In history, \(1\) was once considered a prime number, but modern mathematics defines prime numbers as having exactly two positive divisors: \(1\) and itself. This adjustment is closely related to the statement of the Fundamental Theorem of Arithmetic.

如果我们允许 \(1\) 是质数，那么在算术基本定理的表述中就会出现问题，因为 \(1\) 可以被任意次方的 \(1\) 乘积表示，这样就不再是唯一的分解了。

If we allow \(1\) to be a prime number, then the statement of the Fundamental Theorem of Arithmetic would encounter issues, as \(1\) could be represented as a product of \(1\) raised to any power, thus losing its uniqueness in factorization.

\[ 12 = 1^2 \times 2^2 \times 3^1 = 1^{10,000}\times 2^2 \times 3^1 \]

美是引导数学发展的重要动力 / Beauty is an Important Driving Force in the Development of Mathematics

数学不仅仅是逻辑和计算，它还蕴含着深刻的美感。许多数学家在追求真理的过程中，常常被数学对象的对称性、简洁性和优雅性所吸引。这种美感驱动着他们不断探索更深层次的数学结构和理论。

Mathematics is not just about logic and computation; it also contains profound beauty. Many mathematicians are often attracted by the symmetry, simplicity, and elegance of mathematical objects in their pursuit of truth. This sense of beauty drives them to explore deeper mathematical structures and theories.

整除规则 / Divisibility Rules

接下来的这一部分，我们将从头推导一些常见的整除规则，同时介绍与整除有关的一些定理。

In the following section, we will derive some common divisibility rules from scratch and introduce some theorems related to divisibility.

两个整数 \(a\) 和 \(b\) 如果满足 \(a \mid b\)，则表示 \(a\) 整除 \(b\) 或者说 \(b\) 是 \(a\) 的倍数，即存在一个整数 \(k\) 使得 \(b = ak\)。举个例子，\(6 \mid 18\) 因为 \(18 = 6 \times 3\)。

Two integers \(a\) and \(b\) are said to be divisible if \(a \mid b\), which means that \(b\) is a multiple of \(a\), and there exists an integer \(k\) such that \(b = ak\). For example, \(6\) divides \(18\) because \(18 = 6 \times 3\).

如何表达“有相同的余数”？ / How to express "having the same remainder"?

有相同的余数这个概念在数学中有着重要的地位。我们可以用同余符号来表示这个关系： \[ a \equiv b \mod c \] 这表示 \(a\) 和 \(b\) 除以 \(c\) 的余数相同，即 \(c\) 整除 \(a-b\)。举个例子，如果 \(a = 10\)，\(b = 22\)，而 \(c = 6\)，那么有 \[10\mod 6 = 4\] 和 \[22 \mod 6 = 4\] 所以 \[10 \equiv 22 \mod 6 \Leftrightarrow 6 | (10-22)\] 我们在后续的课程里会更加深刻地学习同余的结构。

Having the same remainder is an important concept in mathematics. We can use the congruence symbol to express this relationship: \[ a \equiv b \mod c \] This means that \(a\) and \(b\) leave the same remainder when divided by \(c\), or equivalently, \(c\) divides \(a-b\). For example, if \(a = 10\), \(b = 22\), and \(c = 6\), then \[10\mod 6 = 4\] and \[22 \mod 6 = 4\] therefore \[10 \equiv 22 \mod 6\ \Leftrightarrow 6 | (10-22)\]. We will study the structure of congruences more deeply in subsequent lessons.

反证法 / Proof by Contradiction

反证法是一种常用的数学证明方法。其基本思路是：假设要证明的结论是错误的，然后通过推理得出一个矛盾，从而证明原结论是正确的。

Proof by contradiction is a common method of mathematical proof. The basic idea is to assume that the conclusion to be proved is false, and then derive a contradiction through reasoning, thereby proving that the original conclusion is true.

Q7: 证明不存在正整数 \(a, b\) 使得 \(a^2 - b^2 = 10\) / Prove that there are no positive integers \(a, b\) such that \(a^2 - b^2 = 10\).

用反证法证明：不存在正整数 \(a\) 和 \(b\)，使得 \(a^2 - b^2 = 10\)。

Use proof by contradiction to show that there are no positive integers \(a\) and \(b\) satisfying \(a^2 - b^2 = 10\).

提示 / Hint：把左边因式分解为 \((a-b)(a+b) = 10\)，然后分析 \(a-b\) 和 \(a+b\) 的奇偶性。

Hint: Factor the left side as \((a-b)(a+b) = 10\), then analyze the parity of \(a-b\) and \(a+b\).

什么是命题? / What is a Proposition?

命题是一个可以被判断为真或假的陈述。例如，“\(n\) 是偶数”是一个命题，因为它对于任何整数 \(n\) 都可以被判定为真或假。

A proposition is a statement that can be judged as true or false. For example, " \(n\) is even" is a proposition because it can be determined to be true or false for any integer \(n\).

充分条件、必要条件与充要条件 / Sufficient, Necessary, and Iff Conditions

两个命题 \(A\) 和 \(B\) 之间的关系有三种：

\(A\) 是 \(B\) 的充分条件：如果 \(A\) 为真，则 \(B\) 必为真。
\(A\) 是 \(B\) 的必要条件：如果 \(B\) 为真，则 \(A\) 必为真。
\(A\) 是 \(B\) 的充要条件：\(A\) 和 \(B\) 同时为真或同时为假。

The relationships between two propositions \(A\) and \(B\) can be classified into three types:

\(A\) is a sufficient condition for \(B\): If \(A\) is true, then \(B\) must be true.
\(A\) is a necessary condition for \(B\): If \(B\) is true, then \(A\) must be true.
\(A\) is a necessary and sufficient condition for \(B\): \(A\) and \(B\) are either both true or both false.

生活中的例子 / Everyday Examples

充分条件："天在下雨"是"地面是湿的"的充分条件。下雨了地面一定湿，但地面湿不一定是因为下雨——也可能有人在浇花。

Sufficient condition: "It is raining" is a sufficient condition for "the ground is wet." If it rains, the ground must be wet; but wet ground doesn't necessarily mean it rained — someone might be watering the flowers.

必要条件："有氧气"是"火能燃烧"的必要条件。火要燃烧就一定需要氧气，但有氧气不一定就有火。

Necessary condition: "There is oxygen" is a necessary condition for "fire can burn." Fire requires oxygen, but having oxygen doesn't automatically mean there is fire.

充要条件："今天是星期六或星期天"和"今天是周末"是充要条件。两者表达的是完全相同的意思，一个为真则另一个一定为真，一个为假则另一个一定为假。

Necessary and sufficient condition: "Today is Saturday or Sunday" and "today is a weekend day" are equivalent. They mean exactly the same thing — one is true if and only if the other is true.

Q8: 判断命题之间的关系 / Determine the Relationships Between Propositions

设三个与整除相关的命题：

命题 \(P\colon 4\mid n\)
命题 \(Q\colon n\) 为偶数
命题 \(R\colon 4\mid n^2\)

Suppose we have three propositions related to divisibility:

Proposition \(P\colon 4\mid n\)
Proposition \(Q\colon n\) is even
Proposition \(R\colon 4\mid n^2\)

请判断 \(P\) 与 \(Q\)、\(Q\) 与 \(R\) 之间分别是充分、必要还是充要条件的关系。

Determine whether the relationship between \(P\) and \(Q\), and between \(Q\) and \(R\), is sufficient, necessary, or necessary and sufficient.

Q12 欧几里得对质数有无穷多的证明/ Euclid's Proof of the Infinitude of Primes

欧几里得是古希腊数学家，他是人类历史上最重要的数学家之一。他最杰出的工作在几何学，但是他也为数论的研究做出了重要贡献。在他的著作《几何原本》中，欧几里得给出了一个著名的证明，表明质数的数量是无限的。

Euclid is a Greek mathematician who is one of the most important mathematicians in human history. His work in geometry is particularly notable, but he also made significant contributions to number theory. In his work "Elements," Euclid presented a famous proof showing that there are infinitely many prime numbers.

欧几里得证明的基本思路 / Basic Idea of Euclid's Proof

欧几里得的证明基于反证法。他假设质数的数量是有限的，并列出所有的质数 \(p_1, p_2, p_3, \ldots, p_n\)。然后，他构造了一个新的数 \(Q\)，定义为所有这些质数的乘积加 \(1\)： \[ Q = p_1 p_2 \ldots p_n + 1 \] 这个新数 \(Q\) 要么是质数，要么有质数因子。但无论哪种情况，它都与已知的质数列表相矛盾，从而得出结论：质数的数量是无限的。

Euclid's proof is based on contradiction. He assumes that there are only finitely many primes and lists all of them. Then, he constructs a new number \(Q\) defined as the product of all these primes plus \(1\): \[ Q = p_1 p_2 \ldots p_n + 1 \] This new number \(Q\) is either prime itself or has prime factors, but in either case, it contradicts the known list of primes, leading to the conclusion that there are infinitely many primes.

用韦恩图表示质因数分解 / Representing Prime Factorization with Venn Diagrams

韦恩图是一种有效的工具，可以直观地表示集合之间的关系。在质因数分解中，我们可以将一个整数的质因数视为集合中的元素，然后用韦恩图来表示这些元素之间的关系。

Venn diagram can be used to represent the prime factorization of an integer. Each prime factor can be represented as a separate circle, and their intersections can show the multiplicity of each factor.

例如，对于整数 \(60\)，它的质因数分解为

For \(60\), its prime factorization is

\[2\times 2\times 3\times 5=2^2\cdot 3\cdot 5\]

用韦恩图表示最大公约数与最小公倍数 / Representing gcd and lcm with Venn Diagrams

让我们用韦恩图来表示 \(60\) 和 \(72\) 的质因数分解。

Let's represent the prime factorization of \(60\) and \(72\) using a Venn diagram.

Venn diagram for gcd and lcm of 60 and 72

在韦恩图中，两个圆的交集部分可表示两个数的公共质因子；它们的乘积自然也是两个数字的因子——最大公约数。图中，\[gcd(60, 72)=\color{#e53935}{2^2\cdot 3}=\color{black}{12}\] 就是这两个数的最大公约数。另一方面，两个圆的并集部分表示两个数的所有质因子；它们的乘积自然也是两个数字的因子——最小公倍数。图中，\[lcm(60, 72)=\color{#e53935}{2^2\cdot 3}\cdot \color{#8e24aa}{2\cdot 3}\cdot \color{#1e88e5}{5}=\color{black}{360}\] 就是这两个数的最小公倍数。

In the Venn diagram, the intersection of the two circles represents the common prime factors of the two numbers, and their product is naturally a factor of both numbers—the greatest common divisor (gcd). In the diagram, \[gcd(60, 72)=\color{#e53935}{2^2\cdot 3}=\color{black}{12}\] is the greatest common divisor of the two numbers. On the other hand, the union of the two circles represents all the prime factors of the two numbers, and their product is naturally a factor of both numbers—the least common multiple (lcm). In the diagram, \[lcm(60, 72)=\color{#e53935}{2^2\cdot 3}\cdot \color{#8e24aa}{2\cdot 3}\cdot \color{#1e88e5}{5}=\color{black}{360}\] is the least common multiple of the two numbers.

互质：没有交集 / Coprime: No Intersection

定义：若 \(\gcd(a,b)=1\)，称 \(a\) 与 \(b\) 互质。用韦恩图看，两数的质因子没有任何公共部分（交集为空）。示例：\(35=\color{#1e88e5}{5\cdot 7}\)，\(48=\color{#8e24aa}{2^4\cdot 3}\)，没有公共质因子，因此 \(\gcd(35,48)=\color{#e53935}{1}\)。

Definition: Two integers \(a,b\) are coprime if \(\gcd(a,b)=1\). In a Venn view, their prime-factor sets have no overlap (empty intersection). Example: \(35=\color{#1e88e5}{5\cdot 7}\) and \(48=\color{#8e24aa}{2^4\cdot 3}\) share no common prime factors, so \(\gcd(35,48)=\color{#e53935}{1}\).

Q13: 用韦恩图求最大公约数与最小公倍数 / Use Venn Diagrams to Find gcd and lcm

用韦恩图的方法，求 \(\gcd(180, 252)\) 和 \(\operatorname{lcm}(180, 252)\)。

Use the Venn diagram method to find \(\gcd(180, 252)\) and \(\operatorname{lcm}(180, 252)\).

提示 / Hint：先做质因数分解：\(180 = 2^2 \times 3^2 \times 5\)，\(252 = 2^2 \times 3^2 \times 7\)。把公共的质因子放在交集里，其余的分别放在两个圆各自的部分。

Hint: Start with prime factorizations: \(180 = 2^2 \times 3^2 \times 5\) and \(252 = 2^2 \times 3^2 \times 7\). Place the common prime factors in the intersection, and the remaining factors in each circle's exclusive region.

Q14: gcd 与 lcm 的乘积关系 / The Product Relationship Between gcd and lcm

已知 \(\gcd(a,b) = 12\)，\(\operatorname{lcm}(a,b) = 360\)。

用韦恩图解释为什么 \(a \times b = \gcd(a,b) \times \operatorname{lcm}(a,b)\) 恒成立。
求 \(a \times b\) 的值。
\(a\) 和 \(b\) 分别可能是多少？找出所有可能的组合。

Given \(\gcd(a,b) = 12\) and \(\operatorname{lcm}(a,b) = 360\):

Use a Venn diagram to explain why \(a \times b = \gcd(a,b) \times \operatorname{lcm}(a,b)\) always holds.
Find the value of \(a \times b\).
What are all possible pairs \((a, b)\)?

Q17: 证明 \(\log_2 3\) 不是有理数 / Prove that \(\log_2 3\) is irrational.

用反证法证明：\(\log_2 3\) 不是有理数。

Use proof by contradiction to show that \(\log_2 3\) is not a rational number.

提示 / Hint：假设 \(\log_2 3 = \dfrac{p}{q}\)（其中 \(p, q\) 为正整数），则 \(2^p = 3^q\)。左边只含质因子 \(2\)，右边只含质因子 \(3\)——这与算术基本定理（质因数分解的唯一性）矛盾。

Hint: Assume \(\log_2 3 = \dfrac{p}{q}\) where \(p, q\) are positive integers, so \(2^p = 3^q\). The left side has only prime factor \(2\), while the right side has only prime factor \(3\) — this contradicts the Fundamental Theorem of Arithmetic (the uniqueness of prime factorization).

思考的乐趣第二季第005课：质数、合数与整除课堂讲义

这节课学什么 / What You Will Learn in This Lesson

质数与合数 / Prime and Composite Numbers

什么是质数？ / What is a Prime Number?

什么是因子？ What's a factor?

100以内的质数 / Prime Numbers Less Than 100

什么是合数？ / What is a Composite Number?

合数的例子 / Examples of Composite Numbers

埃拉托斯特尼筛法 / Sieve of Eratosthenes

质数的分布 / Distribution of Prime Numbers

算术基本定理 / Fundamental Theorem of Arithmetic

每个大于\(1\)的整数 \(N\) 要么是质数，要么可以唯一地表示为质数的乘积（不考虑乘积的顺序）。

Every integer \(N\) greater than 1 is either a prime number itself or can be uniquely represented as a product of prime numbers (up to the order of the factors).

为什么1不是质数 / Why 1 is Not a Prime Number

美是引导数学发展的重要动力 / Beauty is an Important Driving Force in the Development of Mathematics

整除规则 / Divisibility Rules

Q1: 证明 \(2\) 的倍数相加减依然是 \(2\) 的倍数 / Prove that the sum or difference of two multiples of \(2\) is still a multiple of \(2\).

Q2: 证明 \(k\) 的倍数相加减依然是 \(k\) 的倍数 / Prove that the sum or difference of two multiples of \(k\) is still a multiple of \(k\).

Q3: 证明 \(p | ab\) 那么 \(p | a\) 或 \(p | b\) / Prove that if \(p\) divides \(ab\), then \(p\) divides \(a\) or \(p\) divides \(b\).

Q4: 如果 \(p|a\) 且 \(p|b\) 那么 \(p^2 | ab\) / If \(p\) divides \(a\) and \(p\) divides \(b\), then \(p^2\) divides \(ab\).

Q5: 如果 \(a, b\) 除以 \(c\) 余数相同， 那么 \(c | (a-b)\) / If \(a\) and \(b\) leave the same remainder when divided by \(c\), then \(c\) divides \(a-b\).

如何表达“有相同的余数”？ / How to express "having the same remainder"?

Q6: 证明若 \(n^2\) 是 \(p\) 的倍数，那么 \(n\) 也是 \(p\) 的倍数 / Prove that if \(n^2\) is a multiple of \(p\), then \(n\) is also a multiple of \(p\).