数学竞赛中的数论问题(2)

设k?abbaba?a?b，可见k是a的倍数，同样k?，k是b的倍a,ba,ba,ba,b????????数，即k是a,b的公倍数，则存在正整数m使k?m?a,b?，有

ab?m?a,b???a,b?， ?a,b?得 ab?q?a,b???a,b??a,b?

与①矛盾，所以，q??a,b?，得证?a,b???a,b??ab．

ab?a,b??qk?注 也可以由1?m?，得q??a,b?，与q??a,b?矛盾．

ab?a,b??a,b?q两步ab?q?a,b?,ab??a,b?k可以交换吗？

定理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?．

6

推论 若?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． 证明 因为?a,p?|p，所以，素数p的约数只有两种可能：?a,p??1,?a,p??p．但

a不能被p整除，?a,p??p，得?a,p??1．

推论 若p是一个素数，a是任意一个整数，则?a,p??1或?a,p??p． （5）若?a,b??1，则存在整数s,t，使as?bt?1．（定理4推论） （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为正整数． ?m证明 据（6），由?a,b??1可得a,b?1． 同样，由a,b?1可得a,b??m??mn??1．

定理6 设a是大于1的整数，则a的除1之外的最小的正约数q必是素数，且当a是合数时，q?a．

7

1?q1?q，证明 用反证法，假设q不是素数，则存在正整数数q1，使q1|q，但q|a，

故有q1|a，这与q是a的除1之外的最小正约数矛盾，故q是素数．

当a是合数时，设a?a1q，则a1也是a的一个正约数，由q的最小性得q?a1，从而

q2?a1q?a，开方得q?a．

定理7 素数有无穷多个，2是唯一的偶素数．

证明 假设素数只有有限多个，记为p1,p2,?,pn，作一个新数

??pn?1?1． p?p1?p2?若p为素数，则与素数只有 n个p1,p2,?,pn矛盾．

若p为合数，则必有pi??p1,p2,?,pn?，使pi|p，从而pi|1，又与pi?1矛盾． 综上所述，素数不能只有有限多个，所以素数有无穷多个．

2是素数，而大于2的偶数都是合数，所以2是唯一的偶素数．

注：这个证明中，包含着数学归纳法的早期因素：若假设有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． （3）若a?b?c?d，且e|a,e|b,e|c，则e|d． （4）若cb，ba，则ca． 证明 （定义法）由cb，ba，有 b?q1c,a?q2b， 得 a??q1q2?c，

8

即 ca．

（5）若ca，则bcab．

（6）若ca，cb，则对任意整数m,n，有cma?nb． 证明 （定义法）由ca，cb，有 a?q1c,b?q2c， 得 ma?nb??mq1?nq2?c， 即 cma?nb．

（7）若?a,b??1，且abc，则ac．

证明 由?a,b??1知存在整数s,t，使as?bt?1，有

a?cs???bc?t?c，

因为aa，abc，所以a整除等式的左边，进而整除等式的右边，即ac．

注意 不能由abc且a?|b得出ac．如64?9，但6?|4且6?|9． （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?由a为素数得?a,b??1,?a,c??1，由互素的性质（6）|b且a?|c，得?a,bc??1，再由a为素数得a?|bc，与abc矛盾．

注意 没有a为素数，不能由abc推出ab或ac．如64?9，但6?|4且6?|9．

9

定义6 对于整数a,b,c，且c?0，若c(a?b)，则称a,b关于模c同余，记作

|?a?b?，则称a,b关于模c不同余，记作aa?b(modc)；若c?定理9（同余的性质）设a,b,c,d,m为整数，m?0, （1）若a?b(modm)且b?c(modm)，则a?c(modm)； 证明 由a?b(modm)且b?c(modm)，有 a?b?mq1,b?c?mq2，

b(modc)．

a?c?m?q1?q2?，

得a?c(modm)． （2）若a?bm(odm)且c?d(modm)，则a?c?b?dm(odm)且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).

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,,均为整数，且 kkk10

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数学竞赛中的数论问题(2)在线全文阅读。