Last Updated: 2024-03-10 12:17:38 Sunday
-- TOC --
神秘的质数，又称为素数，英文叫Prime Number。
质数有无限个，质数的定义为，在自然数N中，除了1和它本身以外，不再有其它的因数。最小的质数是2。质数只能被1和它自己整除。（所谓素数中的素，可以想象成“没有肉”，没有除了1和它自己之外的其它“菜”）
2任何大于1的正整数，都可以表示成质数的乘积形式，而且这个表达式唯一！
正整数由质数乘积构造而成，质数本身不可再分解。
用公式表达：
\(n=\prod\limits_{i=1}^{m}{p_i^{a_i}}\)
n为大于1的正整数，\(p_i\)为prime number，共有m个不同的prime number，\(a_i\)为\(p_i\)重复的次数。
这个定理的另外一名名称是：算术基本定理。
为什么1不是质数？这是为了让质因数分解唯一这个定理成立。
即，如果1是质数，那么任何质因数分解，都可以随便乘几个1，这样质因数分解就不唯一了！这是数学家们规定的，就像规定0属于自然数一样。
如果1是质数：
\(24 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 1\)
\(24 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 1 \cdot 1 \cdot 1\)
对24的质因数分解，不再唯一。
任意大于2的偶数，都可以写成两个质数之和！
如果两个正整数，除了1以外，没有其它公因子，我们就称这两个数是互质关系（coprime）。比如，17和15没有公因子，所以它们是互质关系。这说明，不是质数也可以构成互质关系。
关于互质关系，可以有以下结论：
- 任意两个质数构成互质关系，比如13和61，11和17。
- 一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10。（如果是倍数，就有除1之外的其它公因子存在）
- 如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和57。
- 1和任意一个自然数是都是互质关系，比如1和99。
- p是大于1的整数，则p和p-1构成互质关系，比如57和56。
- p是大于1的奇数，则p和p-2构成互质关系，比如17和15。（p与p-1由上一条定义）
搞清楚互质关系，就可以理解欧拉函数了。
本文链接：https://cs.pynote.net/math/202110046/
-- EOF --
-- MORE --