刘汝佳-1数论初步.ppt

2005年浙江省队培训 第1讲 数论初步刘汝佳目录一、基本概念 二、进位制 三、模算术与方程 四、杂题一、基本概念基本概念• 整除与约数、倍数. 注意负数 • 可整除性的基本性质 – 若a|b, a|c, 则a|(b+c) – 若a|b, 那么对所有整数c, a|bc – 若a|b, b|c, 则a|c • 整除关系具有传递性. 它是偏序关系(partial order), 是一个格素数和合数• 如果大于1的正整数p仅有的正因子是1和p, 则称p为素数(prime) • 大于1又不是素数的正整数称为合数 (compound) • 如果n是合数, 则n必有一个小于或等于n1/2 的素因子算术基本定理• 每个正整数都可以惟一地表示成素数的乘积，其 中素数因子从小到大依次出现（这里的“乘积”可 以有0个、1个或多个素因子） • 换句话说, 任意正整数n可以写成n=2a1*3a2*5a3*…, 其中a1,a2,a3等为非负整数 • 这个定理也叫做惟一分解定理它是一个定理而 不是公理！虽然在大多人看来，它是“显然成立” 的，但它的确是需要证明的定理除法和同余• 令a为整数，d为正整数，那么有惟一 的整数q和r，其中0≤r0表示用 在分子xi次，xi1，考虑这个0所在的两个2之间的区间，如 果剩下的都是1（没有0），那么把区间最左边的2进位 – 1，那么1->0，向前一位进1，如果前一位变成2，注意 前一位的前面的区间是否全部都是1，如果那样也要和 1)一样修改; 如果前一位原来就是2，那么跳转3) – 2，那么2->1，再将其前面一位加1即可思考：天平• 有一些砝码, 重量为1, 3, 9, 27, 81…形如 3k, 每个重量砝码只有一个. 任意给一个重 量为m的物体, 把它放在天平左边, 如何把放 置砝码使得天平平衡? 放在左边或者右边都 可 • mi时ei≡0(mod mj) – 则e1a1+e2a2+…+ekak就是一个解, 调整得到 [0,m)内的唯一解（想一想，如何调整）整理一下• 一般线性方程组aixi≡bi(mod ni) – ax≡b(mod n)  x≡b1(mod n1) – x≡b1(mod n1)  x≡b1(mod p1,i) – 用中国剩余定理 • 其他规则同余方程 – 二项方程: 借助离散对数(本身??) – 高次方程: 分解n, 降幂 – 单个多变元线性方程: 消法例题：整数序列• 已知{A1,…,An}、B、P求{X1,…,Xn}使得 • A1X1+…+AnXn = B(mod P)分析• 设g=(A1,A2,…An,P)，若g不整除B则无解， 否则我们可以用递归构造解： – 将A1,…An、P和B全部除以g，此时 ((A1,…An),P)=1， – 若n=1，则直接求X1使得A1X1 mod P=B；否则 – 设(A1,…,An-1)=D，则根据欧几里德算法一定存 在x和y使得ANx + Dy = B(mod p)，可以令Xn=x , 则A1X1+…+An-1Xn-1=B-AnX=Dy(mod p)分析• (A1,…,An-1)=D, 所以(A1,…,An-1,P) = (D,P) | (Dy mod P), 因此完全转化为n-1的情形, 令 B=DY mod P即可四、杂题例题：Fermat vs Pythagoras• 给N(k: i在第1个块中恰好出现过一次, 其他每块也 恰好出现一次(每一块的各行是第一块的一个分 解!)，因此一共恰好出现k次 • 下面证明没有矩形证明• 没有矩形当且仅当任意两行最多只有一个 相同的数. 考虑每两行i, j, 规定i