1、初等数论（一） 江苏省南菁高级中学 夏建新 2009年江苏省高中数学奥林匹克夏令营一、奇偶性分析 奇数 奇数偶数；偶数 偶数偶数；奇数 奇数奇数； 奇数的平方都可表示为 8m 1形式；偶数的平方都可表为 8m或 8m 4的形式 任何一个正整数 n，都可以写成 n 2ml的形式，其中 m为非负整数， l为奇数。将全体整数分成两类，凡是 2的倍数称为偶数，否则称为奇数。有如下性质：这些性质既简单又明显，然而它却能解决数学竞赛中的一些难题。1、在一条直线上相邻两点的距离都等于 1的 4个点上各有一只青蛙，允许任意一只青蛙以其余三只青蛙中的某一只为中心跳到其对称点上。证明：无论跳动多少次后，四只青蛙所
2、在的点中相邻两点之间的距离不能都等于2008。（ 2008年西部奥林匹克） 如果若干次跳动后，青蛙所在位置中每相邻两只之间的距离都是 2008，则要求它们处于具有相同奇偶性的位置上，不可能。 证明：将青蛙放在数轴上讨论。不妨设最初四只青蛙所在的位置为 1、 2、 3、 4。注意到，处于奇数位置上的青蛙每次跳动后仍处于奇数位置上，处于偶数位置上的青蛙每次跳动后仍处于偶数位置上。因此，任意多次跳动后，四只青蛙中总有两只处于奇数位置上，另两只处于偶数位置上。2、如果可以将正整数 1 , 2 , 3 , ,n填在圆周上，使得依顺时针方向任何两个相邻的数之和，都能够被它们的下一个数整除。求 n的所有可能
3、值。（ 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年青少年数学国际城市邀请赛） 解：设正整数
4、t，使得 2t ab1，显然 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， 则 ab1(mod 4)。若 2t = ab +1， 则 2t = ab +12(mod 4)，从而 t=1，故 ab = 21 1 = 1，矛盾。若 2t = ab 1= (a
5、m 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、 设
6、 S 1,2, ,2005. 若 S中任意 n个两两互质的数组成的集合中都至少有一个质数，试求 n的最小值 .（ 2005年西部奥林匹克） 解 :首先 ,我们有 n16。事实上 , 取集合 A0 1,22,32,52, ,412,432，则 ,|A0| 15, A0中任意两数互质 , 但其中无质数 , 这表明 n16.其次 , 我们证明 : 对任意 ， n |A| 16， A中任两数互质 , 则 A中必存在一个质数 .利用反证法 , 假设 A中无质数 . 记 A a1,a2, ,a16，分两种情况讨论 .则 a1p1222， a2p2232， ， a15p152472 2005,矛盾 . 若
7、, 则 a1,a2, ,a16均为合数 ,又因为 (ai,aj) 1(1i j16),所以 ai与 aj的质因数均不相同 ,设 ai的最小质因数为 pi,不妨设 p1 p2 p16,由 (1),(2)知 , 反设不成立 , 从而 A中必有质数 , 即 n|A| 16时结论成立 . 若 1 A, 则不妨设 a16 1， a1,a2, ,a15均为合数 ,同 (1)所设 ,同理有 a1p1222， a2p2232， ，a15p152472 2005,矛盾 .综上 , 所求的 n最小值为 16. 5、证明：对所有的非负整数 n， 1至少是 2n 3个质数（不一定互不相同）的乘积。（ 2007第 36届美国数学奥林匹克）证明： 当 n 0时， 1 8 23，结论成立 假设当 n k时结论成立，即 1至少是 2k3个质数的乘积，当 n k 1时，只需证明，对 m N*，记 x 72m 1， 是一个合数（这样， 1至少是 2k 3 2 2(k 1) 3个质数的乘积）
