数论中的一些公式.doc

数论中的一些公式（转）以下等式或者不等式均可以用数学归纳法予以证明！1 + 3 + 5 + . + (2n - 1) = n21*2 + 2*3 + 3*4 + . + n*(n + 1) = n*(n + 1)*(n + 2) / 31*1! + 2*2! + 3*3! + . + n*n! = (n + 1)! - 112 + 22 + 32 + . + n2 = n*(n + 1)*(2n + 1) / 612 - 22 + 32 -. + (-1)n * n2 = (-1)(n + 1) * n * (n + 1) / 222 + 42 + . + (2n)2 = 2n*(n+1)*(2n+1) / 31/2! + 2/3! + . + n/(n+1)! = 1 - 1/(n+1)!2(n + 1) 1 + (n + 1)2n13 + 23 + 33 + . + n3 = (n*(n + 1) / 2)21/(2*4)+1*3/(2*4*6)+1*3*5/(2*4*6*8)+.+(1*3*5*.*(2n-1)/(2*4*6*.*(2n+2) = 1/2 - (1*3*5*.*(2n+1)/(2*4*6*.*(2n+2)1/(22-1) + 1/(32-1) + . + 1 / (n+1)2 - 1) = 3/4 - 1/(2*(n+1) - 1/(2*(n+2)1/2n = 1*3*5*.*(2n-1) / (2*4*6*.*2n) = n2 , n=4, 5,.2n = 2n + 1, n=3,4,.r0 + r1 + . + rn =0, 0r11*r1 + 2*r2 + . + n*rn =1, 0r11/21 + 2/22 + 3/23 + . + n /2n =1(a(1)*a(2)*.*a(2n)(1/2n) = (a(1) + a(2) + . + a(2n) / 2n, n = 1, 2, . a(i)是正数 注:()用来标记下标cos(x) + cos(2x) + . + cos(nx) = cos(x/2)*(n+1)*sin(nx/2) / sin(x/2), 其中sin(x/2) != 01*sin(x) + 2*sin(2x) + . + n*sin(nx) = sin(n+1)*x) / (4*sin(x/2)2) - (n+1)cos(2n + 1)/2 * x) / (2 * sin(x/2)其中sin(x/2) != 05n - 1能被4整除7n - 1能被6整除11n - 6能被5整除6*7n - 2*3n能被4整除3n + 7n - 2能被8整除n条直线能将平面最多划分为(n2 + n + 2) / 2个区域定义H(k) = 1 + 1/2 + 1/3 + . + 1/k则1 + n/2 =H(2n) 2, 欧拉函数E(N)必定是偶数若gcd(a,b) = 1,则有E(a * b) = E(a) * E(b)若一个数N分解成p1a1 * p2a2 * . * pnan，那么E(N) = p1(a1 - 1) * (p1 - 1) * . * pn(an - 1) * (pn - 1)若N1,不大于N且与N互素的所有正整数的和是1/2 * N * E(N)因子和: 若 k=p1a1*p2a2.*piai F(k) = (p10+.+p1a1)*(p20+.+p2a2)*.*(pi0 + . + piai)没有一个平方数是以2,3,7,8结尾的maxa, b, c - mina, b, c = (|a - b| + |b - c| + |a - c|) / 2ac % m = bc % m 可以得到 a % m = b % m m = m / gcd(m, c)如果a % mi = b % mi (i=1,2,.,n) 并且 l = lcm(m1, m2, ., mn) 则可以得到 a % l = b % lEuler 定理若gcd(a,m)=1, 则a(phi(m) % m = 1 % mFermat小定理p为素数，对任意的a有 ap % p = a % pp为素数 ，对任意的a(ap), a(p-1) % p = 1 % pp为素数 ， 对任意的a，若gcd(p,a)=1, a(p-1) % p = 1 % p一个奇数a的平方减1都是8的倍数任意4个连续整数的乘积再加上1 一定是完全平方数当a是整数时，a(a-1)(2a-1)是6的倍数当a是奇数时, a(a2 - 1)是24的倍数n次代数方程 xn + a1 * x(n-1) + . + an-1*x + an = 0 的系数都是a1, a2, . , an都是整数。如果它有有理数的根，证明这个根一定是整数，而且这个数一定是an的因子。如果不是整数，就一定是无理数。设a,b都是正整数，ab而gcd(a,b) = 1 ,如果存在一个素数p，它能够整除b，但是不能够整除10，则a/b一定不能够化成有限小数。如果b=2a * 5b，其中a,b都是非负整数，则a/b能化成有限小数。设0ab, 且gcd(a,b) = 1, 如果a/b能表示成纯循环小数，则我们有gcd(b, 10) = 1。设0ab, 且gcd(a,b) = 1, 令h是一个最小的正整数，使得10h 与1 关于b同余，那么a/b可以表示成纯循环小数0.d1d2d3.dh。设b是一个正整数且gcd(10, b) = 1，令h是一个最小的正整数，能使得10h 与1 关于b同余，则h能够整除Euler(b)设a, b, b1都是正整数，a 1, gcd(b1, 10) = 1。b = 2c * 5d * b1, 其中c， d都是非负整数，且不同时为0， 令h是一个最小的正整数，使得 10h 与1 关于b1同余, 则当c=d时，我们有a/b = 0.a1a2.aca(c+1).a(c + h) ，而当c d时，我们有a/b = 0.a1a2.ada(d+1).a(d + h) 设0.a1a2.an.不能换成有限小数，也不能化成循环小数，则它不能化成分数。设p是一个素数，m是一个正整数且m=na+b其中a是一个非负整数而b是一个不大于n-1的非负整数。令a=pm, 当b=0的时候，a的开n次方是一个整数，当1= b = n - 1时，a的开n次方不能表示为分数。设p是一个素数，m是一个正整数且m=na+b其中a是一个非负整数而b是一个不大于n-1的非负整数。令a=pm, 当b=0的时候，a的开n次方是一个整数，当1= b = n - 1时，a的开n次方=b+c, 其中b是一个正整数而c是一个无限小数但不是循环小数。设a是一个正整数, 当a的开n次方=b+c中b是一个正整数而0c1时，则a的开n次方不能表示成为分数，并且这时c是一个无限小数但不是循环小数。(4b3 + 3b) / (4b2 + 1) = b + 1 / (2b + 1/2b) = 根号b平方+1 = b + 1 / (2b + 1/(2b + 1 / 2b) = (8b4 + 8b2 + 1) / (8b3 + 4b)b + 1/(2b + 1/(2b + 1/(2b + 1/2b) = 根号b平方+1(16b5 + 20b3 + 5b) / (16b4 + 12b2 + 1) = 根号b平方+1 = (8b4 + 8b2 + 1) / (8b3 + 4b)8*8棋盘2牌的完美覆盖数目为12988816=24 * 9012一张m行n列棋盘有一个b-牌的完美覆盖，当且仅当b是m的一个因子或者b是n的一个因子n阶幻方的幻和为 n*(n2+1) / 2 n阶幻方体的幻和为(n4+n) / 2鸽巢原理： 如果n+1个物体被放进n个盒子，那么至少有一个盒子包含两个或者更多的物体鸽巢原理加强形式： 令q1，q2，.，qn为正整数。如果将 q1+q2+.+qn-n+1 个物体放入n个盒子内，那么，至少第一个盒子至少含有q1个物体，或者第二个盒子至少含有q2个物体，. ，或者第n个盒子至少含有qn个物体给定m个整数a1,a2,.,am，存在整数p和q，0=pq=m,使得a(p+1)+a(p+2)+.+a(m)能够被m整除。通俗的说，就是在序列a1,a2,.,am中存在连续个a，使得这些a的和能被m整除由n2+1个实数构成的序列a1，a2,.,a(n2+1)或者含有长度为n+1的递增子序列，或者含有长度为n+1的递减子序列Ramsey定理：在6个（或更多的）人中，或者有3个人，他们中的每两个人都互相认识；或者有3个人，他们中的每两个人都彼此不认识n个元素的集合的循环r-排列的个数由A(n,r)/r=n!/(r * (n-r)!)给出。特别地，n个元素的循环排列的个数是(n-1)!多重集排列：令S是一个多重集，有k个不同类型的元素，各元素的重数分别为n1,n2,.,nk。设S的大小为n=n1+n2+.+nk。则S的排列数等于n!/(n1!*n2!*.*nk!)多重集的组合：令S为具有k中类型元素的一个多重集，每种元素均具有无限的重复数。则S的r-组合的个数等于 C(r+k-1,r)如果排列P1P2.Pn有 逆序列b1,b2,.,bn，且k=b1+b2+.+bn为逆序数，那么P1P2.Pn可以通过k次连续交换得到12.n利用反射Gray码生成相邻元组1的个数相差1的所有组合生成1,2,.,n的字典序r-组合的算法：从r-组合a1a2.ar=12.r开始当a1a2.ar不等于（n-r+1)(n-r+2).n时,做：i)确定最大的整数k，是的ak + 1=n且ak + 1不等于a1,a2,.arii)用r-组合 a1.a(k-1)(ak + 1)(ak+2).(ak + r - k + 1)替换 a1a2.arC(n,k)=C(n-1,k)+C(n-1,k-1) 1=k=1)通过对等式 (1+x)n=sigma(C(n,k)*xk) k: 0-n 两边就微分，可以得到 sigma(kp * C(n,k) k: 1-n的和sigma(C(n,k)2) = C(2n,n) k: 1-nC(r,0)+C(r+1,1)+.+C(r+k,k) = C(r+k+1,k)C(0,k)+C(1,k)+.+C(n-1,k)+C(n,k)=C(n+1,k+1)Dilworth定理： 令(X,0,j=1,那么, (i)对任意的整数 n= 1, r=1有 = X0,.,Xn-1, = X0,.,Xn-1,Xn+1/. 特别地有 = 注:用该定理可以求连分数的值(2)对于连分数数数列 有递推关系: Pn = XnPn-1+Pn-2; Qn = XnQn-1+Qn-2; 定义: P-2 = 0; P-1 = 1; Q-2 = 1; Q-1 = 0; 所以: P0 = X0; Q0 = 1; P1 = X1X0+1; Q1 = X1; 特别地:当 Xi=1 时, Pn, Qn为Fbi数列(3)对于连分数数数列 当n= 1时，我们有PkQk-1 = Pk-1Qk = (-1)k 当n=2时， 我们有