初等数论

初等数论是数论的一个分支，主要研究整数及其性质，使用的工具通常不涉及高级数学（如复分析或代数结构）。其研究内容简单明了，但其中包含许多深刻的问题和定理。

初等数论的主要内容

1. 整数的基本性质

• 整除性：
  定义：如果存在整数 k，使得 a = b * k，则称 b 整除 a，记作 b | a。
  性质：
  • 如果 b | a 且 b | c，则 b | (a + c) 和 b | (a - c)。
  • 如果 b | a，则 b | (a * c) 对任意整数 c 都成立。

2. 素数与合数

• 素数：
  只有 1 和它本身作为约数的整数，像 2, 3, 5, 7 等。

• 合数：
  能够被除了 1 和它本身之外的其他整数整除的数，如 4, 6, 8, 9 等。

• 素数定理：
  素数的分布具有一定规律，尽管不能通过简单的公式列出所有素数，但素数的密度随数字增大而减小。

3. 最大公约数与最小公倍数

最大公约数 (gcd)：

两个数的最大公约数是能同时整除这两个数的最大整数，记作 gcd(a, b)。

• 步骤 1： 列出 12 和 18 的所有约数：

  • 12 的约数：1, 2, 3, 4, 6, 12
  • 18 的约数：1, 2, 3, 6, 9, 18

• 步骤 2： 找出 12 和 18 的公共约数：

  • 公共约数：1, 2, 3, 6

• 步骤 3： 选择最大的公共约数：

  • 最大公约数：gcd(12, 18) = 6

• 最小公倍数 (lcm)：
  两个数的最小公倍数是能被这两个数同时整除的最小整数，记作 lcm(a, b)。

4. 同余与模运算

• 同余：
  如果两个数在除以某个数 m 后，得到相同的余数，则称这两个数在模 m 下同余，记作 a ≡ b (mod m)。

• 模运算：
  模运算是对整数进行除法操作后，保留余数的运算。在加法、减法、乘法和除法中都可以进行模运算。

5. 欧拉函数与互素性

• 欧拉函数：
  欧拉函数 φ(n) 计算的是小于 n 且与 n 互素的正整数的个数。若 a 与 n 互素，则 φ(n) 等于所有小于 n 且与 n 互素的整数的个数。

• 互素性：
  两个数 a 和 b 互素，当且仅当 gcd(a, b) = 1。

6. 费马小定理与应用

• 费马小定理：
  如果 p 是素数，且 a 是整数，且 a 与 p 互素，则有 a^(p-1) ≡ 1 (mod p)。

初等数论的应用

• 分数化简：
  初等数论的基本理论（如 gcd）广泛应用于分数的化简过程，通过求 gcd 可以找到分子分母的最大公约数，从而简化分数。

• 密码学：
  初等数论在密码学中有着重要作用，特别是在公钥加密系统中，例如 RSA 算法依赖于大整数的因数分解问题。

• 数的性质分析：
  初等数论可以用于对数的性质进行分析，比如素数的分布、同余方程的解等。