数论算法学习初步

今天开始学习一下算导上的数论算法，做一点笔记。

一些符号约定：

d|a 表示d整除a， 模n的等价类 [a]_n= {a+kn: k属于Z}， 模n的完全剩余系则是这些等价类的集合 Z_n ={[a]_n:0≤a≤n-1}

，每个等价类都用最小的非负元素来表示则有 Z_n={0,1,..,n-1}

公约数和最大公约数

a和b的公约数d的定义: d|a 且 d|b。

重要性质： d是a和b公约数 → d|(a+b)且d|(a-b)。可以推广到a和b的线性组合d | (ax+by)，x,y是整数。

gcd(a,b)表示最大公约数。定义gcd(0,0) = 0（可以使得基本性质普遍成立

基本性质，比较简单，略

定理：a和b不全为0，gcd(a,b)是{ax+by: x,y 属于Z}中的最小元素。

证明思路：最小元素用s表示，证明s≥gcd(a,b) 和 gcd(a,b)≥s。

1）gcd(a,b)≥s。 只需证明s是a和b的公约数，q = a/s， a%s = a - qs = a - q(ax+by) = a(1-qx) + b(-qy)。

a%s是a和b的线性组合，s又是线性组合最小的正数，0≤a%s<s → a%s = 0，也就是说s | a。同样可以证明 s | b。

2）s≥gcd(a,b)。s是a和b的线性组合，由公约数的重要性质，gcd(a,b)|s，且s>0 → gcd(a,b)≤s

推论: 1.gcd(a,b)是线性组合，所以a和b的任意公约数d，满足d | gcd(a,b)

        2.gcd(an,bn) = n gcd(a,b)。 gcd(an,bn) = min({anx+bny: x,y 属于整数}) = n min({anx+bny: x,y 属于整数}) = n gcd(a,b)

        3.对于任意整数n, a和b，如果n|ab且gcd(a,n) = 1,则 n | b。

（这个证明是我自己想哒，可能有不严谨的地方。k = ab/n，gcd(a,n) = ax + ny = 1 ，两边乘上k ，akx + aby = ab/n，kx + by = b/n。左边一定是个整数，得到 b/n是整数，所以n | b。我觉得把a，b，n分解了也可以证明，但是似乎没怎么用上定理

互质数

gcd(a,b) = 1称a和b为互质数。

定理：整数a,b,p， gcd(a,p) = 1 且 gcd(b,p) = 1，那么 gcd(ab,p) = 1。

证明思路：利用之前的结论拆成线性组合做运算 （拆成线性组合对证明太有用辣

ax + py = 1, bx′ + py′ = 1, 两式相乘整理ab(xx′) + p(ybx′ + y′ax + pyy′) = 1。找到ab 和 p的最小正线性组合辣。

两两互质，n₁, n₂ , ... , n_k,  对于任意i ≠ j, 有 gcd(n_i,n_j) = 1，称n₁, n₂ , ... , n_k两两互质

持续更新...

数论算法学习初步

原文：http://www.cnblogs.com/jerryRey/p/4892549.html