定理

唯一分解定理

定义

每个大于$1$的自然数, 要么本身就是质数, 要么可写为$2$个或以上质数积, 且质因子排列顺序唯一

• $N = \prod_{i=1}^k p_i^{a_i}$ ($p_1< p_2 < …< p_k<N$且均为质数)

例, $6936=2^3317^2, 1200=2^435^2$

• 若 $N = \prod_{i=1}^k p_i^{a_i}$, 其因数有 $\prod_{i=1}^{k} (a_i+1)$ 个

证明

对于$p_1$部分来说, 分以下情况,

• 包含$0$个$p_1$时, $N$ 的因数$x_1 = p_2^{a_2}\cdots p_k^{a_k}$

• 包含$1$个$p_1$时, $N$ 的因数$x_2 = p_1^{1}p_2^{a_2}\cdots p_k^{a_k}$

$\cdots$

• 包含$a_1$个$p_1$时, $N$ 的因数$x_{a_1} = p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$

$p_1$部分总因数个数为$(a_1 + 1)$,

$p_2$部分总因数个数为$(a_2 + 1)$

$\cdots$

$p_i$部分总因数个数为$(a_i + 1)$

• $N$的因数个数为 $\prod_{i=1}^{k} (a_i + 1)$

例, $24 = 2 ^ 3 * 3 ^ 1$, 因数有$(3 + 1) * (1 + 1) = 8个$

求100!因数个数

#include<stdio.h>

typedef long long ll;

const int n = 100;

int main(void){
    int b[101] = {0};
    int x;
    for (int i = 1; i <= n; i++) {
        x = i;
        for (int j = 2; j * j <= x; j++) {
            // 当j是x的素因子时
            while (x % j == 0) {
                // m[j]表示素因子j的指数
                b[j]++;
                x /= j;
            }
        }
        // 若x不为1说明其为素数
        if (x != 1) {
            b[x]++;
        }
    }

    ll sum = 1;
    for(int i = 1;i <= n ;i++){
        if(b[i]){
            sum *= b[i];
        }
    }
    printf("%lld\n", sum);
    return 0;
}

同余定理

正整数$m$, 若整数$a$, $b$满足$a-b$能够被$m$整除, 即$(a-b)/m$得到整数

则称整数$a$与$b$对模$m$同余, 记作

$a≡b(mod$   $m)$

对模$m$同余是整数的一个等价关系

$a≡b(mod$  $m)$ 等价 $a\%m = b\%m$

例如, $26≡2(mod 12)$

$a≡b(mod$  $m)$ 等价 $a^{p}≡b^{p} (mod$  $m)$

费马小定理定义

若 $p$ 为质数, 则$a^{p}≡a(mod$  $p)$, 即 $a^{p-1}≡1(mod$  $p)$

费马小定理通常用来检验一个数是否是素数, 是素数的必要非充分条件

满足费马小定理检验的数未必是素数, 这种合数叫做卡迈克尔数($Carmichael Number$)

最小卡迈克尔数是$561$

对于质数 $p$

• $n$  $mod$  $m = 0$, 则$\varphi(n \times p) = \varphi(n) \times p$

• $n$  $mod$  $m \ne 0$, 则$\varphi(n \times p) = \varphi(n) \times (p-1)$