Number Theory Basics and Properties of Integers | 数论基础与整数性质

📚 Number Theory Basics and Properties of Integers | 数论基础与整数性质

Number theory is one of the oldest and most beautiful branches of mathematics. At its heart lies the study of integers and their properties. In this article, we will explore divisibility, prime numbers, GCD and LCM, the Euclidean algorithm, modular arithmetic, and more — all essential tools for exams and further study.

数论是数学中最古老、最迷人的分支之一，其核心在于研究整数及其性质。本文将系统讲解整除性、素数、最大公约数与最小公倍数、欧几里得算法、同余等核心概念，这些内容在考试和后续学习中都非常重要。

1. Divisibility and Basic Properties | 整除性及其基本性质

An integer a is said to divide an integer b (written a | b) if there exists an integer k such that b = a k. For example, 3 | 15 because 15 = 3 × 5. On the other hand, 4 ∤ 10 since 10 is not a multiple of 4.

如果一个整数 a 能整除整数 b（记作 a | b），即存在整数 k 使得 b = a k。例如，3 | 15，因为15 = 3 × 5；而4不能整除10，因为10不是4的倍数。

Key properties of divisibility include:

整除性有以下重要性质：

If a | b and b | c, then a | c (transitivity).
如果 a | b 且 b | c，则 a | c（传递性）。
If a | b and a | c, then a | (b + c) and a | (b – c).
如果 a | b 且 a | c，则 a | (b + c) 且 a | (b – c)。
If a | b, then a | mb for any integer m.
如果 a | b，则对任意整数 m，有 a | mb。

These properties form the foundation for solving many problems involving factors and multiples.

这些性质是解决因数、倍数相关问题的基础。

2. The Division Algorithm and Quotient-Remainder Form | 带余除法与商余形式

For any integers a and b with b > 0, there exist unique integers q and r such that a = b q + r and 0 ≤ r < b. Here q is the quotient and r is the remainder. This is called the Division Algorithm.

对于任意整数 a 和 b（b > 0），存在唯一的整数 q 和 r，使得 a = b q + r，且 0 ≤ r < b。其中 q 称为商，r 称为余数。这就是带余除法。

For example, when 23 is divided by 5, we have 23 = 5 × 4 + 3, so the quotient is 4 and the remainder is 3.

例如，用5除23时，23 = 5 × 4 + 3，所以商为4，余数为3。

This form is especially useful in modular arithmetic and in proving results about integers, such as showing that every integer is either even or odd.

这种形式在同余运算以及证明整数性质时特别有用，例如可以说明每个整数不是偶数就是奇数。

3. Prime Numbers and Composite Numbers | 素数（质数）与合数

A prime number is a positive integer greater than 1 that has exactly two distinct positive divisors: 1 and itself. For example, 2, 3, 5, 7, 11 are prime numbers. A composite number is a positive integer greater than 1 that is not prime, meaning it has more than two positive divisors.

素数是大于1且恰好只有两个不同正因数的正整数，即1和它本身。例如2、3、5、7、11都是素数。合数是大于1且不是素数的正整数，意味着它有超过两个正因数。

Note that 1 is neither prime nor composite. The number 2 is the only even prime number.

注意，1既不是素数也不是合数。2是唯一的偶素数。

The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be represented uniquely as a product of prime numbers, up to the order of the factors. For example, 360 = 2³ × 3² × 5.

算术基本定理指出，每个大于1的整数都可以唯一地分解为素数的乘积（不考虑因数的顺序）。例如，360 = 2³ × 3² × 5。

Prime factorization is a powerful tool for finding GCD, LCM, and solving problems about divisibility.

质因数分解是求最大公约数、最小公倍数以及解决整除问题的重要工具。

4. Greatest Common Divisor (GCD) | 最大公约数

The greatest common divisor of two or more integers is the largest positive integer that divides each of them without leaving a remainder. For instance, the GCD of 12 and 18 is 6.

两个或多个整数的最大公约数是能整除每一个整数且不产生余数的最大正整数。例如，12和18的最大公约数是6。

One method to find the GCD is to use prime factorization. Take the smallest power of each common prime factor.

求最大公约数的一种方法是使用质因数分解，取所有公共质因子的最小幂次。

gcd(72, 108) = 2² × 3² = 36

Another efficient method is the Euclidean algorithm, which we will discuss next.

另一种高效方法是欧几里得算法，我们将在下一节讨论。

5. The Euclidean Algorithm | 欧几里得算法

The Euclidean algorithm is a systematic way to compute the GCD of two integers. It is based on the fact that gcd(a, b) = gcd(b, r), where r = a mod b (the remainder when a is divided by b).

欧几里得算法是计算两个整数最大公约数的系统方法。它基于这样一个事实：gcd(a, b) = gcd(b, r)，其中 r = a mod b（a除以b所得的余数）。

Let us find gcd(252, 198):

我们用欧几里得算法求 gcd(252, 198)：

252 = 198 × 1 + 54
198 = 54 × 3 + 36
54 = 36 × 1 + 18
36 = 18 × 2 + 0

The last nonzero remainder is 18, so gcd(252, 198) = 18. This algorithm is fast and avoids the need to factor large numbers.

最后一个非零余数是18，因此 gcd(252, 198) = 18。该算法效率很高，而且无需对大数进行因式分解。

6. Least Common Multiple (LCM) | 最小公倍数

The least common multiple of two or more integers is the smallest positive integer that is divisible by each of the given integers. For example, the LCM of 4 and 6 is 12.

两个或多个整数的最小公倍数是能被每个给定整数整除的最小正整数。例如，4和6的最小公倍数是12。

There is an important relationship between GCD and LCM: for positive integers a and b,

最大公约数和最小公倍数之间有一个重要关系：对于正整数 a 和 b，

a × b = gcd(a, b) × lcm(a, b)

This formula provides a quick way to find the LCM once the GCD is known. For instance, if gcd(12, 18) = 6, then 12 × 18 = 6 × lcm(12, 18), so lcm(12, 18) = 36.

这个公式在已知最大公约数时提供了一种快速求最小公倍数的方法。例如，由于 gcd(12, 18) = 6，所以 12 × 18 = 6 × lcm(12, 18)，即 lcm(12, 18) = 36。

7. Modular Arithmetic and Congruence | 模运算与同余

Modular arithmetic is a system of arithmetic on integers where numbers “wrap around” upon reaching a certain value, called the modulus. For a positive integer n, we say that a is congruent to b modulo n, written a ≡ b (mod n), if n divides (a – b).

模运算是一种整数运算系统，在达到某个称为模数的值后数字会“循环回绕”。对于正整数 n，如果 n 能整除 (a – b)，则称 a 与 b 模 n 同余，记作 a ≡ b (mod n)。

For example, 17 ≡ 5 (mod 12) because 17 – 5 = 12, and 12 is divisible by 12. On a clock, 17:00 is the same as 5:00.

例如，17 ≡ 5 (mod 12)，因为17 – 5 = 12，且12能被12整除。在时钟上，17点与5点相同。

Congruence satisfies properties similar to equality:

同余具有与等式类似的性质：

If a ≡ b (mod n) and c ≡ d (mod n), then a + c ≡ b + d (mod n).
如果 a ≡ b (mod n) 且 c ≡ d (mod n)，则 a + c ≡ b + d (mod n)。
If a ≡ b (mod n) and c ≡ d (mod n), then a c ≡ b d (mod n).
如果 a ≡ b (mod n) 且 c ≡ d (mod n)，则 a c ≡ b d (mod n)。

Modular arithmetic is widely used in cryptography, computer science, and problem solving.

模运算在密码学、计算机科学以及解题中被广泛使用。

8. Special Divisibility Rules | 常用整除判定法则

Divisibility rules provide quick mental shortcuts for checking whether a number is divisible by small integers.

整除判定法则为我们提供了快速判断一个数能否被某些小整数整除的心算捷径。

Divisor \| 除数	Rule \| 判定法则	Example \| 示例
2	Last digit is even	1,346 ends with 6, so divisible by 2
2	末位数字是偶数	1346的末位是6，能被2整除
3	Sum of digits is divisible by 3	2+4+3=9, so 243 is divisible by 3
3	各位数字之和能被3整除	2+4+3=9，因此243能被3整除
5	Last digit is 0 or 5	725 ends with 5, so divisible by 5
5	末位数字是0或5	725的末位是5，能被5整除
9	Sum of digits is divisible by 9	1+8+9=18, so 189 is divisible by 9
9	各位数字之和能被9整除	1+8+9=18，因此189能被9整除
11	Alternating sum of digits is divisible by 11	(1-2+1-6) = -6, not divisible by 11, so 1216 is not
11	奇偶位数字交替和能被11整除	(1-2+1-6) = -6，不能被11整除，所以1216不行

These rules are useful in both quick checks and in examination questions.

这些法则在快速检验和考试题目中都非常有用。

9. Prime Factorization and Its Applications |

Published by TutorHao | Mathematics Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

Number Theory Basics and Properties of Integers | 数论基础与整数性质