江苏夏令营-初等数论.pptVIP

* * 初等数论（一） 江苏省南菁高级中学　夏建新 2009年江苏省高中数学奥林匹克夏令营 一、奇偶性分析 ⑴奇数±奇数＝偶数；偶数±偶数＝偶数；奇数×奇数＝奇数；…… ⑵奇数的平方都可表示为8m＋1形式；偶数的平方都可表为8m或8m＋4的形式 ⑶任何一个正整数n，都可以写成n＝2ml的形式，其中m为非负整数，l为奇数。 将全体整数分成两类，凡是2的倍数称为偶数，否则称为奇数。有如下性质： 这些性质既简单又明显，然而它却能解决数学竞赛中的一些难题。 1、在一条直线上相邻两点的距离都等于1的4个点上各有一只青蛙，允许任意一只青蛙以其余三只青蛙中的某一只为中心跳到其对称点上。证明：无论跳动多少次后，四只青蛙所在的点中相邻两点之间的距离不能都等于2008。（2008年西部奥林匹克） 如果若干次跳动后，青蛙所在位置中每相邻两只之间的距离都是2008，则要求它们处于具有相同奇偶性的位置上，不可能。 证明：将青蛙放在数轴上讨论。 不妨设最初四只青蛙所在的位置为1、2、3、4。 注意到，处于奇数位置上的青蛙每次跳动后仍处于奇数位置上，处于偶数位置上的青蛙每次跳动后仍处于偶数位置上。 因此，任意多次跳动后，四只青蛙中总有两只处于奇数位置上，另两只处于偶数位置上。 2、如果可以将正整数1 , 2 , 3 ,…,n填在圆周上，使得依顺时针方向任何两个相邻的数之和，都能够被它们的下一个数整除。求n的所有可能值。（1999年环球城市竞赛） 解：考虑n ≥3情形 当n≥3时，如果圆周上有二个连续偶数，则造成这个圆周上的每一个整数都是偶数(不合)。 所以n最多是3，1, 2, 3这个数任意排在圆周上都可以，所以n＝3。 因为圆周上必有一个整数是偶数，而它的逆时针方向的下二个数及顺时针方向的下个数，都必须是奇数。 由于1～n中，奇数的个数最多比偶数的个数多1个，所以圆周上最多只有一个偶数，这样奇数有2个， 3、已知t 为正整数，若2t可以表示成ab±1(其中a, b 是大于1 的整数)，请找出满足上述条件所有可能的t 值。（2008年青少年数学国际城市邀请赛） 解：设正整数t，使得2t＝ab±1，显然a为奇数。 (1) 若b为奇数，则2t＝(a±1)(ab－1　ab－2　…　a＋1) 由于a，b均为奇数，而奇数个奇数相加或相减的结果一定是奇数，所以ab－1　ab－2　…　a＋1也是奇数， 得知2t ＝ab±1＝a±1，故b = 1， 这与b≥2矛盾。 从而只可能ab－1　ab－2　…　a＋1＝1， 综上可知，满足题设的2 的正整数次幂是23，即t＝3。 (2) 若b为偶数，令b＝2m， 则ab≡1(mod 4)。 若2t = ab +1， 则2t = ab +1≡2(mod 4)， 从而t=1，故ab = 21－1 = 1，矛盾。 若2t = ab－1= (am－1)(am +1)， 两个连续偶数之乘积为2的方幂只能是am－1=2，am+1=4， 从而a＝3，b＝2m＝2。2t = ab－1 = 32－1 = 8。 二、质数与合数 大于1的整数按它具有因数的情况又可分为质数与合数两类。 即对任一整数a＞1，有a＝　　　　　　，其中p1＜p2＜…＜pn均为质数，?1、?2、…、?n都是正整数。 另可得：a的正约数的个数为（?1＋1）（?2＋1）…（?n＋1） ⑴算术基本定理：任何一个大于1的整数都可以分解成质数的乘积。如果不考虑这些质因子的次序，则这种分解法是唯一的。 ⑵设n是大于2的整数，如果不大于　的质数都不是n的因子，则n是质数。 4、设S＝{1,2,…,2005}. 若S中任意n个两两互质的数组成的集合中都至少有一个质数，试求 n的最小值.（2005年西部奥林匹克） 解:首先,我们有n≥16。 事实上, 取集合A0＝{1,22,32,52,…,412,432}， 则　　　 ,|A0|＝15, A0中任意两数互质, 但其中无质数, 这表明n≥16. 其次, 我们证明: 对任意　　 ，n＝|A|＝16，A中任两数互质, 则A中必存在一个质数. 利用反证法, 假设A中无质数. 记A＝{a1,a2,…,a16}，分两种情况讨论. 则a1≥p12≥22，a2≥p22≥32，…，a15≥p152≥472＞2005,矛盾. ⑴若　　 , 则a1,a2,…,a16均为合数, 又因为(ai,aj)＝1(1≤i＜j≤16),所以ai与aj的质因数均不相同, 设ai的最小质因数为pi,不妨设p1＜p2＜…＜p16, 由(1),(2)知, 反设不成立, 从而A中必有质数, 即n＝|A|＝16时结论成立. ⑵若1∈A, 则不妨设a16＝1，a1,a2,…,a15均为合数, 同(1)所设,同理有a1≥p12≥22，a2≥p22≥32，…，a15≥p