奇妙P进制

奇妙PPPP进制内容摘要：在日常生活中我们运用的都是十进制，却都忽略了其他进制的妙用。我们对p进制进行了深入的探究，发现P进制在同余、证明存在性问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 、构造、组合问题等方面有着奇妙的用法，可以让我们从奇特的角度，出奇兵，解决难题关键字：p进制同余2进制卢卡斯定理正文：在平时的运用中，我们使用以及习惯使用的整数通常是十进制的。例如给定这样的一个数A，其各位上的数字分别记为ma，1-ma，2-ma，……，0a，可以简记为A=01-mmaaa…（其中0am≠），于是我们很自然地把A 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示为关于10的m次的多项式，即A=01111101010aaaammmm+⋅+……+⋅+⋅−−于是我们可以根据上面的10进制的表示法，来类推出A的P进制表示：给定一个自然数P（P进制的基），可将任意正整数的P进制表示成下述形式：A=01111PPPaaaammmm+⋅+……+⋅+⋅−−，其中0a1-m2,10i}1-P2,1{0ami≠……=……∈，，，，，，，，而m为十进制数。我们把A在P进制下的表示简记为A=P01-mmaaa）（…而对于P进制，我们日常生活以及解题中并不是十分常用，我们只习惯于十进制的加减乘除，却忽略了其他进制下数的独特性质。例如下面一个找出毒药的例子：试验室里有243瓶试剂，而其中有一瓶是毒药，现在有5只小白老鼠，每只老鼠可以喝多瓶毒药，但毒药的药效需要一天才能发作，问至少可以用几天一定可以找出那瓶毒药。这个例子当我们用平日里的十进制来思考的时候，会发现毫无头绪，而且总是需要试验次数总是非常多。其实我们发现它里面隐含了一个非常关键的信息，就是24353=，于是我们不妨转换思想，从三进制的角度来想想这个问题。于是问题就迎刃而解了。我们将243个药瓶从0开始编号，编委0~242，并将其全部转换成三进制下的表示，于是就是3.333322222)10(,)2(,)1(,)0(）（……，我们再将不足5位的三进制数前面添上0凑足五位。将1~5号小白鼠分别对应03，13，23，33，43数位，第一天他们分别喝掉自己位数上数字为0的药剂，第二天喝掉自己位数上数字为1的药剂，第三天喝掉自己位数上数字为2的药剂。如果有第i只小白老鼠死在了第j天（3}2{1j}{1,2,3,4,5i，，，∈∈），那么有毒试剂在三进制表示下1i3−位上的数字就是j-1，由于5只老鼠试遍的每个位数的所有情况，于是3天之后，我们就可以确定有毒试剂在三进制的表示，于是便可以确定有毒的试剂。从这个例子发现，P进制的性质的确十分独特他可以通过进制的转换，来改变数位上的数字的变化幅度，从而来减少试验的次数。从而逐步缩小范围，确定药剂的编号。于是，我们展开了对p进制的一系列的研究，探索他的神秘，发现了P进制与许多的问题都有所联系一、PPPP进制与同余的联系我们发现了，对于一些同余方程的求解，或者一些某些数对于素数的阶，有非常妙的用法。但是这只是仅限一些特殊的数，并非对所有数字都可以适用的。我们先来看一道第5届IMO的题目：（1）求所有的正整数n，使得12n−能被7整除（2）证明：对任何正整数n，12n+不能被7整除这道题其实不难，尤其是第一小题的话，许多同学大概一眼就可以看出）（7mod123≡，而且3就是2模7的阶，所以所有的正整数就是kn3=+∈Zk而第二小题只要利用第一题的性质，对n进行模3的分类讨论即可。n=3k+∈Zk)7(mod2111212k3n≡+≡+=+n=3k+1+∈Zk)7(mod31212121k3n≡+≡+=++n=3k+2+∈Zk)7(mod51412122k3n≡+≡+=++于是对任意的正整数n，12n+不能被7整除下面我们从2进制的角度来看这道题，将12n−与7全部转换成2进制表示，7=2111）（）（个�������nn111111112……=−，于是我们在二进制表示下用7去除12n−，于是很显然的发现，当且仅当后者位长是前者倍数的时候获被除数为0的时候才有所求结论，所以应有kn3=+∈Zk同样的对于12n+，我们同样可以将其准换为2进制）（位�����1nn01100012+……=+，下面开始进行二进制除法()2211000000111）（……()2100100……111100011121000）（于是我们可以发现，施行每步除法所得于是皆为1，在注意到末位的1，故施行最后一步除法时被除单元只是可能三种情况：21001）（2101）（211）（皆不能被2111）（整除。题目证完了，但是我们确因此发现了题目中2进制除法总结出的规律，与上面模 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 的分类有其曲同工之妙，当然对于简单的数字，很显然自然是上面的模分析比较快，2进制显得有些大材小用，但是我们发现，在一些较大的数（当然不能过大）中，列竖式却要比模分析要快，而且计算更简便，因为2进制下的1、0变换十分简单。例如：求）（49mod12n≡的最小的正整数n。我们要是模分析的话，由）（7mod123≡，与欧拉定理）（49mod1267≡×就要计算62，212，十分的麻烦，而且计算量大。在这样情况下，我们不妨用上面的方法，尝试着做一下2进制除法，来找2关于49的阶。()211000149=设n是满足题设的最小的整数，）（个�������nn111111112……=−下面做2进制除法2111111111111111111111），，，，，（()2110001()210111110100111001110111010111110001110001110001100110111000111100111000110001111100011011011110001101010111000110010011100011100011100010虽然长，但是计算非常简单，免去了反复运算十位数乘法的大量的运算量，可以准确的找出2关于49的阶（计算1的个数即可）。下面还有一道利用进制除法做的题，简单而且快捷。证明：当2n≥时Fermat数12Fn2n+=的末位数都是7题目等价于）（10mod712n2≡+，这道题当然可以用数论知识来做，利用同余的性质来证明。但是用2进制来想想，他的方法也是非常奇妙的。10=()21010⎟⎟⎠⎞⎜⎜⎝⎛…=+=+���������位122n0000011000000012Fnn，经过列竖式试除两步后，我们发现余数为()210，于是就有循环，因此，每次去除4个零而不改变余数，于是由）（4mod312n≡−我们可以知道，在经过有限次操作之后，会得到210001）（，由210001）（除以()21010，即可得余数为()2111，即12Fn2n+=的末位数都是7。二、PPPP进制对于集合构造以及数的构造的妙用。对于许多涉及存在性的命题，我们通常是通过构造来解答这一类的问题，而如何在千变万化的数字中，构造出那个一个数或者一组数，P进制给了我们一个思路。对构造题，不妨多从P进制的角度上入手，会有一片新的天地。首先，有一个非常简单的结论：p为奇数，⎭⎬⎫⎩⎨⎧−…………+−+−∈21p1023p21pai，，，，，，那么A=01111PPPaaaammmm+⋅+……+⋅+⋅−−可以表示从21p1m−−+到21p1m−+的所有整数。我们先证明不存在两组不同的{}01mmaaa，，，……−与{}01mma'a'a'，，，……−，使得A=A’若不然，则有)(mod'AAp≡即01111PPPaaaammmm+⋅+……+⋅+⋅−−≡01111'P'P'P'aaaammmm+⋅+……+⋅+⋅−−（modp）于是）（pmod'00aa≡，由⎭⎬⎫⎩⎨⎧−…………+−+−∈21p1023p21pai，，，，，，于是00'aa=。由此我们可以得到，12111211PPaPPa’’’aaaammmmmmmm+……+⋅+⋅=+……+⋅+⋅−−−−−−同理可得11aa’=，于是我们就可以得到{}01mmaaa，，，……−={}01mma'a'a'，，，……−，矛盾!命题成立。很显然，21pA21p-1m1m−≤≤−++，而由于⎭⎬⎫⎩⎨⎧−…………+−+−∈21p1023p21pai，，，，，，于是A一共有1mp+各不同的值，而21p1m−−+到21p1m−+一共有1mp+个整数，所以A=01111PPPaaaammmm+⋅+……+⋅+⋅−−可以表示从21p1m−−+到21p1m−+的所有整数。于是有了这个结论，我们对一些构造的题目都可以迎刃而解。例如（IMO-28预选题）找出8个正整数，，，，821nnn……使他们有下列性质：对于每个整数k，，1985k1985≤≤−有8个整数821aaa，，，……，其中每个ia都属于集合{}1,0,1−，使得inak81ii∑==。这道题，用上面的结论可以说是秒杀，取13−=iin,于是k可以表示32802138−=−−到32802138=−的所有值，比求证的结论还要强。再来看看2009年的联赛题，为二试第三题，可以说是到一道难题。但是其实从P进制的想思路，确实柳暗花明。下面给出笔者用P进制所给的解答。设k，l是给定的两个正整数，证明存在无穷多个正整数m使得kmC与l互素。首先证明一个引理，即卢卡斯定理。设a，b为正整数，且b＞a，p是素数，设()p01mmbbbb……=−，()p01mmaaaa……=−（若a不足m+1位则在前面添上0），定义1C0n=，0Cab=（若a＞b）则）（pmodCCCC001-m1-mmmabababab……⋅⋅≡证明：由）（）（modpx1x1pp+≡+知）（）（）（）（）（）（modpx1x1x1x1x101-m1-mmm01m1mmmbbpbpbpbpbb+⋅……⋅+⋅+≡+=++……+⋅+⋅−−于是考察两边ax前的系数，可得）（pmodCCCC001-m1-mmmabababab……⋅⋅≡由卢卡斯定理我们可以推出，n，m为正整数，m＞n，则nmC被P整除的充要条件是m-n在p进制表示下发生借位。由算术基本定理，t21t21pppl∂∂∂……=，1p＜1p＜3p……＜tp，+∈∂……∂∂Zt21，设d是k在1p，2p……tp进制下最大位数，令m=()kppph1dt21+……⋅+，h∈+N于是m-k在1p，2p……tp进制下不发生借位，于是1,Ckm=）（ipt2,1i，，……=存在无穷多个正整数m使得kmC与l互素三、pppp进制是组合中的奇招对于一些策略题，我们利用p进制，可以找出最优方法，就像开头的那个例子一样。现有1990堆石头，块数分别为1,2，……1990，进行如下操作，每次可选择任意多堆，从其中每堆拿走同样多的石块，问要把所有石块拿走，最少要从做多少次？由于0123456789102022202020222221990⋅+++⋅+⋅+⋅+++++=，且把1,2，……1989也写成2进制的形式，操作如下：第一次，在够取的堆中取走1024210=块石头；第二次在够取的堆中取走51229=块，……，最后取走仅剩下1快的那些堆石头，总共11次。因为含一块石头的堆，故必有取一块石头的操作，如余下的操作取走都是超过2快的，则恰有2快的堆无法取走，故2次操作对多去1+2=3快，……，10次操作最多取走1023块，因而1990堆石头至少要进行11次操作。通过对p进制的探究，我们发现了p进制在许多问题中的奇妙应用，为解决许多 数学 数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划 问题提供了新的思路，新的方法，尽管探究的过程有些困难，但同时也充满了趣味，在日后的学习中，我们仍要勇于发现问题，探究问题，做到精益求精，相信我们将会有更加有趣的发现。