引言

“数学是科学的皇后，数论是数学的皇后。“
——卡尔·弗里德里希·高斯

数论（英语：Number theory） 是纯粹数学的分支之一，主要研究整数的性质。被誉为“最纯”的数学领域。
——From 中文Wiki·数论

初等数论意指使用不超过高中程度的初等代数处理的数论问题，最主要的工具包括整数的整除性与同余。
——From 中文Wiki·初等数论

回顾小学、初中的学习，很多时候都是在与集合与在该集合上的运算打交道：

• 小学：我们主要研究自然数集/有理数集和运算（加减乘除）
• 中学：我们主要研究实数集中的各种运算（可把函数与映射等等单元操作或多元操作称为运算）
• 甚至上到大学，我们学习的高数也是一样的

初等数论是研究数的规律，特别是整数性质的数学分支。
在计算机中没有真正实数存在，所以整数的研究在计算机中至关重要，有了初等数论的一些性质，我们就可以用更优秀的复杂度（经常是$ O(1) $）解决问题
——By zm

回想小学就接触到的思考题，很多都是研究集合内元素的规律和运算——也就是说，我们早就接触到数论了，只是没有以严格的数学定义来研究它。而现在，让我们来一窥数学皇后之美吧！

质数与质因数

按照数论的定义，正整数可以分为质数（素数）和合数，其中质数的定义是： 在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数

为什么是1呢？如果1是质数又会怎样呢？这要牵涉到唯一分解定理了：

每个大于1的自然数，要么本身就是质数，要么可以写为2个或以上的质数的积，而且这些质因子按大小排列之后，写法仅有一种方式

例如：
$ 24 = 2 \times 2 \times 2 \times 3 $
$ 68 = 2 \times 2 \times 17 $

假如1是质数，唯一分解定理就不成立了。这体现了数学定义的严谨性：公理给出制约，制约创造结构

gcd与lcm

我们定义最大公约数为gcd，最小公倍数为lcm。例如:

$ gcd(24, 32) = 8 $， 可简记作 $ 8 = d(24, 32) $

$ lcm(24, 32) = 96 $

欧几里得算法

gcd.cpp

1
2
3
4
5
6
7
8
9

// 欧几里得算法(Euclid algorithm)  最大公约数
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); }  // 递归


int gcd2(int a, int b) {  // 迭代 
    int t;
    while (b) { t = a; a = b; b = t%b; }
    return a;
}

欧几里得算法拓展

唯一分解定理

lcm.cpp

1
2

// 最小公倍数；先除后乘防溢出
int lcm(int a, int b) { return a / gcd(a, b) * b; }

素数筛

1
2
3
4
5
6
7
8
9

const int MAXN = 1e6;
bool vis[MAXN];

void init_prime(int n) {
    vis[0] = 1, vis[1] = 1;
    int m = sqrt(n+0.5);
    for (int i = 2; i <= m; i++) if (!vis[i])
        for (int j = i*i; j <= n; j += i) vis[j] = true;
}

同余

费马小定理

$ 如果a是质数， \forall (a, p) \equiv 1, x^{p-1} \equiv 1 \pmod p $

群论

书单推荐

From zm

• 数学女孩1
• 数学女孩2
• 初等数论及其性质
• 算法数论
• 数学女王的邀请——初等数论入门

计数与概率基础

杨辉三角与二项式定理

离散概率初步

其他数学专题

递推

数学期望

连续概率

附录

参考文献

版权信息

本文原载于https://blog-allenwu233.netlify.app/，复制请保留原文出处