数论基本算法 数论 基本算法系列

数论基本算法 本文将详细介绍数论的基本概念和算法，包括可除性、素数、公约数、最大公约数、模运算等。 1. 可除性 在数论中，一个整数能被另一个整数整除的概念是中心概念，记号 d|a（读作“d 除 a”）意味着对某个整数 k，有 a = kd。0 可被每个整数整除。如果 a>0 且 d|a，则|d|≤|a|。如果 d|a，则我们也可以说 a 是 d 的倍数。如果 a 不能被 d 整除，则写作 dFa。如果 d|a 并且 d≥0，则我们说 d 是 a 的约数。 2. 素数与合数 对于某个整数 a>1，如果它仅有平凡约数 1 和 a，则我们称 a 为素数（或质数）。素数具有许多特殊性质，在数论中举足轻重。例如，2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59 等都是素数。不是素数的整数 a>1 称为合数。例如，因为有 3|39，所以 39 是合数。 3. 定理 1：素数有无穷个 证明：假设素数只有有限的 n 个，从小到大依次排列为 p1,p2,...,pn，则 x = (p1·p2·...·pn)+1 显然是不能被 p1,p2,...,pn中的任何一个素数整除的，因此 x也是一个素数，这和只有 n 个素数矛盾，所以素数是无限多的。 4. 除法定理 对任意整数 a 和任意正整数 n，存在唯一的整数 q 和 r，满足 0 < r ≤ n，并且 a = qn + r。这个定理是整数的基本定理之一。 5. 模运算 我们定义了一个整数除以另一个整数的余数的概念后，就可以很方便地给出表示同余的特殊记法。如果 (a mod n)=(b mod n)，就写作 a ≡ b (mod n)，并说 a 和 b 对模 n 是相等的。 6. 公约数与最大公约数 如果 d 是 a 的约数并且也是 b 的约数，则 d 是 a 与 b 的公约数。例如，24 与30 的公约数为 1,2,3 和 6。注意，1 是任意两个整数的公约数。公约数的一条重要性质为：如果 d 是 a 和 b 的公约数，那么 d 也是 ab 的公约数。 本文还介绍了其他一些基本概念和算法，如整数的模运算、同余、等价类、公约数和最大公约数等，都是数论的基础知识。