数学竞赛中的数论问题
定理4 a,b是两个不同时为0的整数，若ax0?by0是形如ax?by（x,y是任意整数）的数中的最小正数，则
（1）ax0?by0|ax?by；（2）ax0?by0??a,b?．
证明 （1）由带余除法有ax?by??ax0?by0?q?r，0?r?ax0?by0， 得 r?a?x?qx0?x?b?y?qy0??ax0?by0，
知r也是形如ax?by的非负数，但ax0?by0是形如ax?by的数中的最小正数，故r?0，即ax0?by0|ax?by． （2）由（1）有ax0?by0|a?1?b?0?a，ax0?by0|a?0?b?1?b，
得ax0?by0是a,b的公约数．另一方面，a,b的每一个公约数都可以整除ax0?by0，所以ax0?by0是a,b的最大公约数，ax0?by0??a,b?．
推论 若?a,b??1，则存在整数s,t，使as?bt?1．（很有用）
定理5 互素的简单性质： （1）?1,a??1．（2）?n,n?1??1．（3）?2n?1,2n?1??1． （4）若p是一个素数，a是任意一个整数，且a不能被p整除，则?a,p??1． 推论 若p是一个素数，a是任意一个整数，则?a,p??1或?a,p??p． （6）若?a,b??1,?a,c??1，则?a,bc??1．
证明 由?a,b??1知存在整数s,t，使as?bt?1．有 a?cs??bct?c，得 ?a,bc???a,c??1． （7）若?a,b??1，则?a?b,a??1，?a?b,b??1， ?a?b,ab??1．
证明 ?a?b,a????b,a???b,a??1，?a?b,b???a,b??1，由（6）?a?b,ab??1． （8）若?a,b??1，则a,bm?n??1，其中m,n为正整数． ?mmn证明 据（6），由?a,b??1可得a,b?1．同样，由a,b?1可得a,b?1．
m?????定理7 素数有无穷多个，2是唯一的偶素数．
??pn?1?1． 证明 假设素数只有有限多个，记为p1,p2,?,pn，作一个新数 p?p1?p2?若p为素数，则与素数只有 n个p1,p2,?,pn矛盾．
若p为合数，则必有pi??p1,p2,?,pn?，使pi|p，从而pi|1，又与pi?1矛盾． 综上所述，素数不能只有有限多个，所以素数有无穷多个． 2是素数，而大于2的偶数都是合数，所以2是唯一的偶素数．
1
注：这个证明中，包含着数学归纳法的早期因素：若假设有n个素数，便有n?1个素数．（构造法、反证法）
定理8（整除的性质）整数a,b,c通常指非零整数 （1）1a，?1|a；当a?0时，a|a，a|0．
（2）若ba，a?0，则b?a;若ba，b?a，则a?0;若ab?0，且ba,ab，则a?b．
证明 由ba，a?0，有a?bq，得a?bq?b．逆反命题成立“若ba，b?a，则a?0”; 由b?a且b?a得a?b，又ab?0，得a?b． （7）若?a,b??1，且abc，则ac．
证明 由?a,b??1知存在整数s,t，使as?bt?1，有a?cs???bc?t?c， 因为aa，abc，所以a整除等式的左边，进而整除等式的右边，即ac．
（8）若?a,b??1，且ac,bc，则abc．
证明 由?a,b??1知存在整数s,t，使as?bt?1，有acs?bct?c，
又由ac,bc有c?aq1,c?bq2代入得ab?q2s??ab?q1t??c，所以abc．
注意 不能由ac且bc得出abc．如不能由630且10|30得出60|30． （9）若a为素数，且abc，则ab或ac．
证明 若不然，则a?|b且a?|c，由a为素数得?a,b??1,?a,c??1，由互素的性质（6）得?a,bc??1，再由
|bc，与abc矛盾． a为素数得a?|?a?b?，定义6 对于整数a,b,c，且c?0，若c(a?b)，则称a,b关于模c同余，记作a?b(modc)；若c?则称a,b关于模c不同余，记作ab(modc)．
定理9（同余的性质）设a,b,c,d,m为整数，m?0,
若a?b(modm)且c?d(modm)，则a?c?b?d(modm)且ac?bd(modm)．
证明 由a?b(modm)且c?d(modm)，有a?b?mq1,c?d?mq2， ① 对①直接相加 ，有?a?c???b?d??m?q1?q2?，得 a?c?b?d(modm).
对①分别乘以c,b后相加，有ac?bd??ac?bc???bc?bd??m?cq1?bq2?，得 ac?bd(modm)． （3）若a?b(modm)，则对任意的正整数n有a?b(modm)且an?bn(modmn).
2
nn（4）若a?b(modm)，且对非零整数k有k(a,b,m)，则
ab?m???mod?． kk?k?证明 由a?b(modm)、，有 a?b?mq，又k(a,b,m)，有
abm,,均为整数，且 kkkab?m?abm??q，得 ??mod?．
kk?k?kkk定理10 设a,b为整数，n为正整数， （1）若a?b，则?a?b?a?bn?n?．
?b2n?1?．
an?bn??a?b??an?1?an?2b?an?3b2???abn?2?bn?1?．
（2）若a??b，则?a?b?a?2n?1a2n?1?b2n?1??a?b??a2n?2?a2n?3b?a2n?4b2???ab2n?3?b2n?2?．
（3）若a??b，则?a?b?a?2n?b2n?．
a2n?b2n??a?b??a2n?1?a2n?2b?a2n?3b2???ab2n?2?b2n?1?．
定义7 设n为正整数，k为大于2的正整数, a1,a2,?,am是小于k的非负整数，且a1?0．若 n?a1km?1?a2km?2???am?1k?am，则称数a1a2?am为n的k进制表示．
定理11 给定整数k?2，对任意的正整数n，都有唯一的k进制表示．如
n?a110m?1?a210m?2???am?110?am，0?ai?9,a1?0（10进制） n?a12m?1?a22m?2???am?12?am．0?ai?1,a1?0（２进制）
定理12 （算术基本定理）每个大于1的正整数都可分解为素数的乘积，而且不计因数的顺序时，这种表示是
唯一的
n?p11p22?pk???k，其中p1?p2???pk为素数，?1,?2,?,?k为正整数． （分解唯一性）
???k定理13 若正整数n的素数分解式为 n?p11p22?pk则n的正约数的个数为
d?n???a1?1??a2?1???ak?1?，
pk?k?1?1p1?1?1?1p2?2?1?1????． n的一切正约数之和为 S?n??p1?1p2?1pk?1证明 对于正整数n?p11p22?pk m?p11p22?pk???k???k，它的任意一个正约数可以表示为
，0??i??i ， ①
由于?i有0,1,2,?,?i共?i?1种取值，据乘法原理得n的约数的个数为d?n???a1?1??a2?1???ak?1?．
3
考虑乘积p1?p1???p1?01?1??p02?p21???p2?2??pk0?pk1???pk?k， ??展开式的每一项都是n的某一个约数（参见①），反之，n的每一个约数都是展开式的某一项，于是，n的一切约数之和为S?n??p?p???p10111??1???p0k?pk???pk1?1?pk?k?1?1p1?1?1?1p2?2?1?1?????．
p1?1p2?1pk?1注 构造法．
定义8 （高斯函数）对任意实数x，?x?是不超过x的最大整数．亦称?x?为x的整数部分，?x??x??x??1． 定理14 在正整数n!的素因子分解式中，素数p作为因子出现的次数是 ??n??n??n????p2???p3???． p??????证明 由于p为素数，故在n!中p的次方数是1,2,?,n各数中p的次方数的总和（注意，若p不为素数，这
句话不成立）．在1,2,?,n中，有??n??n??n??n?2个的倍数；在个的倍数的因式中，有个的倍数；在ppp?p2??p2???p??????p???个p的倍数的因式中，有?2?n?3p个的倍数；?，如此下去，在正整数n!的素因子分解式中，素数p作为因子出3??p?现的次数就为??n??n??n????p2???p3???．注 省略号其实是有限项之和． p??????定理15 （费玛小定理）如果素数p不能整除整数a，则pap?p?1?1?．
证明2 改证等价命题：如果素数p不能整除整数a，则a?a?modp?． 只需对a?1,2,?,p?1证明成立，用数学归纳法． （1）a?1，命题显然成立．
（2）假设命题对a?k?1?k?p?1?成立，则当a?k?1时，由于p|Cp?i?1,2,?,p?1?，故有
i ?k?1??k?Cpkp1pp?1p?1???Cpk?1 ?kp?1?k?1?modp?．（用了归纳假设）
这表明，命题对a?k?1是成立． 由数学归纳法得a?a?modp?．
p又素数p不能整除整数a，有?a,p??1，得pa?p?1?1?．
定义9 （欧拉函数）用??n?表示不大于n且与n互素的正整数个数． 定理16 设正整数n?p11p22?pk???k，则 ??n??n?1???1??1??1?1??1??． ????p1??p2??pk?推论 对素数p有??p??p?1,?p．
???p???p??1．
4
第二讲 数论题的范例讲解
（12）?2n??0?mod4?,?2n?1??1?mod4?,?2n?1??1?mod8?． （13）任何整数都可以表示为n?2m222?2k?1?．
b1,b2,?,b7是它们的一个排列，例1-1（1986，英国）设a1,a2,?,a7是整数，证明?a1?b1??a2?b2???a7?b7?是偶数．（a1,a2,?,a7中奇数与偶数个数不等）
例1-2 ?的前24位数字为??3.14159265358979323846264，记a1,a2,?,a24为该24个数字的任一排列，求证?a1?a2??a3?a4???a23?a24?必为偶数．
（暗藏3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4中奇数与偶数个数不等）
例2 能否从1,2,?,15中选出10个数填入图的圆圈中，使得每两个有线相连的圈中的数相减（大数减小数），所得的14个差恰好为1,2,?,14？
解 考虑14个差的和S，一方面
S?1?2???14?105为奇数．
另一方面，每两个数a,b的差与其和有相同的奇偶性 a?b?a?b(mod2)，因此，14个差的和S的奇偶性与14个相应数之和的和S的奇偶性相同，由于图中的每一个数a与2个或4个圈中的数相加，对S的贡献为2a或
//4a，从而S/为偶数，这与S为奇数矛盾，所以不能按要求给图中的圆圈填数．
评析：用了计算两次的技巧．对同一数学对象，当用两种不同的方式将整体分为部分时，则按两种不同方式所
求得的总和应是相等的，这叫计算两次原理成富比尼原理．计算两次可以建立左右两边关系不太明显的恒等式．在反证法中，计算两次又可用来构成矛盾．
例3 有一大筐苹果和梨分成若干堆，如果你一定可以找到这样的两堆，其苹果数之和与梨数之和都是偶数，问最少要把这些苹果和梨分成几堆？
解 （1）4堆是不能保证的．如4堆的奇偶性为：（反例） （奇奇），（偶偶），（奇偶），（偶奇）．
（2）5堆是可以保证． 因为苹果和梨数的奇偶性有且只有上述4种可能，当把这些苹果和梨分成5堆时，必有2堆属于同一奇偶性，其和苹果数与梨数都是偶数．
例
,xn,?x4 有n个数x1,x2?1n,，它们中的每一个要么是1，要么是?1．若x2x????3n?x1x2??xn1x?x，求证x4|n． n01?证明 由xi??1,?1?，有xixi?1??1,?1?，再由x1x2?x2x3?????xn?1xn?xnx1?0， 知n个xixi?1中有一半是1，有一半是?1，n必为偶数，设n?2k．现把n个xixi?1相乘，有
??xn?1xn?xnx1?x1x2???xn?1xn?1， (?1)(?1)?x1x2?x2x3?
5
kk2222