1、数论简介数论简介带余除法带余除法 带余除法定理设 a 和 b 为整数， b 0，则存在惟一的整数 q 和 r 使得 a = qb + r， 0 r 0， c 0, 整除有如下性质1. 若 c | b， b | a, 则 c | a；2. 若 b | a，则 bc | ac；3. 若 c | a， c | b，则对任意整数 m， n 有c |ma + nb。模运算模运算 设 n是一正整数 ,a是整数 ,若a=qn+r, 0rn, 则 a mod n=r 若 (a mod n)=(b mod n),称为 a,b模 n同余，记为 ab mod n 称与 a模 n同余的数的全体为 a的同余类，记为 a
2、， a称为这个同余类的代表元素 模运算模运算 同余的性质若 n|(a-b)，则 ab mod n(a mod n) (b mod n), 则 ab mod nab mod n ，则 ba mod nab mod n ， bc mod n ，则 ac mod n 求余运算 a mod n将 a映射到集合 0,1, ,n-1,求余运算称为模运算模运算模运算 模运算的性质(a mod n)+(b mod n) mod n=(a+b) mod n(a mod n)-(b mod n) mod n=(a-b) mod n(a mod n)(b mod n) mod n=(ab) mod n模运算模运算
3、例： Z8=0,1,2,3,4,5,6,7,模 8加法和乘法 0 1 2 3 4 5 6 70 0 1 2 3 4 5 6 71 1 2 3 4 5 6 7 02 2 3 4 5 6 7 0 13 3 4 5 6 7 0 1 24 4 5 6 7 0 1 2 35 5 6 7 0 1 2 3 46 6 7 0 1 2 3 4 57 7 0 1 2 3 4 5 6 0 1 2 3 4 5 6 70 0 0 0 0 0 0 0 01 0 1 2 3 4 5 6 72 0 2 4 6 0 2 4 63 0 3 6 1 4 7 2 54 0 4 0 4 0 4 0 45 0 5 2 7 4 1 6 36 0 6 4 2 0 6 4 27 0 7 6 5 4 3 2 1
