初等数论再学习

桃扇骨 2023-08-17 16:38 87阅读 0赞

1、最大公约数的两组性质

$(a, b) = (b, a % b)$。怎么用？可以用来求 gcd。可以作为 gcd 的一个重要的性质，比如 $(a, b) = (a, ax + b)$。

$\\exists x, y, (a, b) = ax + by$。怎么用？可以将 (a, b) 表示成 a 和 b 的线性组合。也可以求出满足 ax + by = (a, b) 的 x 和 y。

$(a, b) = 1, (a, c) = 1$，可以得到 $(a, bc) = (b, ac) = (c, ab) = 1$。在证明欧拉函数的积性时用到。

2、欧拉定理

$(a, m) = 1, a ^ \{\\phi(m)\} \\equiv 1 \\pmod m$。怎么证？先考虑一个既约剩余系，将它乘上 a，仍然是一个既约剩余系。因为由同余的消去率知道得出的数字两两不同，而且 $(x, m) = 1, (a, m) = 1$，所以 $(ax, m) = 1$。然后这两个剩余系的乘积应该相等，再将相同的部分直接消去，得证。

拓展欧拉定理，可以解决四阶超幂在模意义下的值。

3、欧拉函数的相关性质

积性怎么证？即证 ab 的既约剩余系是 \{bxi + ayj | 1 <= i <= phi(a), 1 <= j <= phi(b)\}。先证 bxi + ayi 两两不同，因为 b(xi - xj) = a(yj - yi)，分别对 a, b 取同余，xi equiv xj, yi equiv yj，即 xi = xj, yi = yj，矛盾。再证 bxi + ayi 与 ab 互质，因为 (a, xi) = 1, (a, b) = 1，所以 (a, bxi) = 1，所以 (a, bxi + ayi) = 1，同理 (b, bxi + ayi) = 1，所以 (ab, bxi + ayi) = 1。

$\\phi(ab) = \\phi(a) \\phi(b) d / \\phi(d)$。快速计算乘积的欧拉函数值。

4、

转载于:https://www.cnblogs.com/Sdchr/p/11406547.html