初等数论基础

整除性与同余关系

• 整除性: 当一个整数 a 可以被另一个整数 b 整除时，我们记作 b | a。这意味着 a 是 b 的倍数，即存在整数 k 使得 a = bk。
• 同余关系: 如果两个整数 a 和 c 除以另一个整数 b 的余数相同，则称 a 和 c 模 b 同余，记作 a ≡ c (mod b)。同余关系是整数集合上的等价关系，它将整数划分为不同的剩余类。

数论中的重要定理

• 欧拉定理: 对于任意互质的正整数 a 和 n，有 a^φ(n) ≡ 1 (mod n)，其中 φ(n) 是欧拉函数，表示小于等于 n 且与 n 互质的正整数个数。
• 费马小定理: 是欧拉定理的一个特例。对于任意质数 p 和与 p 互质的整数 a，有 a^(p-1) ≡ 1 (mod p)。
• 威尔逊定理: 一个自然数 n 是质数当且仅当 (n-1)! ≡ -1 (mod n)。

最大公约数与欧几里得算法

• 最大公约数 (GCD): 两个或多个整数的公约数中最大的一个称为它们的最大公约数。
• 欧几里得算法: 一种高效求解最大公约数的算法，也称为辗转相除法。
• 扩展欧几里得算法: 不仅可以求出最大公约数，还能找到满足 ax + by = gcd(a, b) 的整数解 (x, y)。

模逆元与应用

• 模逆元: 对于整数 a 和模数 n，如果存在整数 x 使得 ax ≡ 1 (mod n)，则称 x 是 a 关于模 n 的逆元。
• 应用: 模逆元在密码学、编码理论和计算机算法设计中有着广泛的应用，例如 RSA 加密算法、求解线性同余方程等。