type
Post
status
Published
date
May 3, 2026
slug
maths
summary
tags
算法
category
icon
password
一、整除 (Divisibility)
1. 定义
对于整数 （），若存在整数 使得 ，则称 a 整除 b，记作 。
若 a 不能整除 b，记作 。
2. 基本性质
性质 | 内容 |
传递性 | 若 且 ，则 |
线性组合性 | 若 且 ，则对任意整数 ，有 |
线性组合性证明思路：
- 由 和 ，存在整数 使得
- 则
- 因此
二、同余 (Congruence)
1. 定义
给定正整数 ，若整数 满足 ，即 能被 整除，则称 a 与 b 对模 m 同余，记作：
2. 同余的基本性质
性质 | 内容 |
自反性 | |
对称性 | 若 ，则 |
传递性 | 若 且，则 |
加法保持性 | 若，，则 |
乘法保持性 | 若 ，，则 |
三、欧拉函数 (Euler’s Totient Function)
1. 前置概念：互质
两整数 的 最大公约数 时，称 n 与 m 互质（互素）。
2. 定义
表示 1 到 n 之间与 n 互质的整数个数。
3. 重要性质
性质 | 公式 |
素数情形 | 若 p 为素数，则 |
积性函数 | 若 ，则 |
通用公式 | 若 |
四、算术基本定理 (Fundamental Theorem of Arithmetic)
又称 唯一分解定理：每一个大于 1 的自然数 n，要么本身是素数，要么可以唯一地写成一系列素数的乘积（不考虑顺序）。
标准分解式
其中 均为素数，a_i 为正整数。
五、约数和公式
若 ，则 n 的所有约数之和为：
或写成：
约数和公式及其证明
定理
设正整数 n 的标准分解式为：
则 n 的所有正约数之和为：
证明
第一步：分析约数的结构
由算术基本定理，n 的任意正约数 d 必具有形式：
其中指数满足：
关键观察：每个约数的各个素因子指数是独立选取的。
第二步：约数和的多重求和
所有约数之和可表示为：
第三步：分离变量（核心技巧）
由于求和变量相互独立，可将多重求和分解为乘积：
原理：这是分配律的逆向运用——每个括号选取一项相乘，恰好遍历所有可能的约数。
第四步：等比数列求和
对每个括号使用等比数列求和公式 ：
第五步：合并结果
因此：
示例验证
以 为例：
直接列举：约数为 1, 2, 3, 4, 6, 12，和为 28
公式计算：
推广：约数个数公式
类似地，约数个数（记 ）：
证明：每个指数 有 种选择（从 到 ），由乘法原理即得。
总结表格
函数 | 公式 | 关键思想 |
约数和 | 分离变量 + 等比求和 | |
约数个数 | 乘法原理 |
知识脉络图
- 作者:wzy
- 链接:https://wzyblogs.us.ci//article/maths
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
