组合数学在数论中的应用实例

《组合数学在数论中的应用实例》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、组合数学在数论中的应用实例摘要：本文将组合数学中的容斥原理和递归关系应用到数论中,讨论了数组整除性的判定和整除的计数;Euler函数的计数和质数个数的计数问题。关键词：容斥原理;递归关系;整除;Euler函数;质数我们知道,在组合数学中,容斥原理(又称包含排斥原理)和递归关系是解决组合计数问题的一个重要工具和方法。将这一重要工具和方法应用到数论中,对于数组整除性的判定和整除的计数;Euler函数的计数和质数个数的计数,都会带来很大方便。下面,首先简要介绍容斥原理、常系数线性齐次递归关系的建立和迭代解法,然后给出几个应用实例。1　容斥原理与常系数线性齐次递归关系简介1.

2、1　容斥原理设S是有限集合,AiS　(i=1,2,…,n,n≥2)则　　　　　　　　∪ni=1Ai=(A1+A2+…+An)-(A1∩A2+A1∩A3+…+An-1∩An)+…+(-1)n-1A1∩A2∩…∩An=∑nk=1(-1)k-1∑1≤i1

3、中不具有性质Pi的元素的集合(以上i=1,2,…,n)。对于任意k(1≤k≤n)个正整数i1,i2,…,ik(1≤i1

4、ck是k个常数,且ck≠0,则递归关系　　　　　　　　　　　an=c1an-1+c2an-2+…+ckan-k　(n≥k)称为k阶常系数线性齐次递归关系。称方程　　　　　　　　　　　xk=c1xk-1+c2xk-2+…+ck-1x+ck为此递归关系的特征方程。由代数基本定理,这个k次方程在复数域内有k个根。设q1,q2,…,qt为其全部不同的根,重数分别是r1,r2,…,rt(显然r1+r2+…+rt=k),则此数列的通项为:an=(b11+b12n+…+b1r1nr1-1)qn1+(b21+b22n+…+b2r2nr2-1)qn2+…+(bt1+bt2n+…+btr

5、tnrt-1)qnt其中诸bij(共有k个)是待定系数,只需将数列{an}开始的k项初值代入即可确定出这些系数,从而最终得到数列{an}的通项公式。反之,由数列{an}的通项公式也可求出关于an的递归关系式。2　数列{an}n≥0的整除性的判定和整除的计数整除性的判定是数论中经常遇到的问题。在数论中利用同余理论去解答此类问题是常用的方法之一。本文主要讨论数列{an}n≥0的各项可被某一整数整除的判定问题。利用递归关系的解法,可以给出上述问题的解答。读者可以通过下面的例题举一返三总结出解答此类问题的方法。例1:证明数列{an}n≥0={11n+2+122n+1}的各项能

6、被133整除。证法1:利用数论中的同余理论证明由于133等于两个质数7和19的乘积,因此只要11n+2+122n+1能被7和19整除,则一定能被133整除。通项an可写成为an=11n+2+122n+1=121×11n+12×144n。因为121≡7,144≡11　(mod19),所以11n+2+122n+1≡7×11n+12×11n≡19×11n≡0　(mod19),即1911n+2+122n+1。而121≡2,11≡4,12≡5,144≡4　(mod7),所以11n+2+122n+1≡2×4n+5×4n≡7×4n≡0　(mod7),即711n+2+122n+1。从

7、而得到13311n+2+122n+1。证毕证法2:利用递归关系的解法证明因为　　　　　　　　　an=11n+2+122n+1=121×11n+12×144n,而　　　　　　　　　　　11+144=155,11×144=1584所以x1=11,x2=144是方程x2-155x+1584=0的两个根,从而有递归关系　　　　　　　　　　　an=155an-1-1584an-2　(n≥2)又因为　　　　　　　　a0=121+12=133　　　　　　　　　　　a1=121×11+12×144=3059=133×23a0和a1都能被133整除,由递归关系式可知a