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

（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．

mn

（8）若 a,b 1，则a,b 1，其中m,n为正整数． m

证明 据（6），由 a,b 1可得a,b 1． mmn

同样，由a,b 1可得a,b 1．

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

合数时，q

证明 用反证法，假设q不是素数，则存在正整数数q1，使q1|q，但q|a，1 q1 q，故有q1|a，这与q是a的除1之外的最小正约数矛盾，故q是素数．

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

q2 a1q

a，开方得q

定理7 素数有无穷多个，2是唯一的偶素数． 证明 假设素数只有有限多个，记为p1,p2, p p1p2

,pn，作一个新数

pn 1 1．

,pn矛盾．

若p为素数，则与素数只有 n个p1,p2,若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，且b,a，则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，

即 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．

|b得出ac．如64 9，但6 |4且6 |9． 注意 不能由abc且a

（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．

|b且a |c，证明 若不然，则a 由a为素数得 a,b 1, a,c 1，由互素的性质（6）|bc，与abc矛盾． 得 a,bc 1，再由a为素数得a

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

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

a b(modc)；若c | a b ，则称a,b关于模c不同余，记作

a

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

c b d（2）若a b(modm)且c d(modm)，则a

证明 由a b(modm)且c d(modm)，有

m(odm)且ac bd(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). （4）若a b(modm)，且对非零整数k有k(a,b,m)，则

n

n

ab m

mod ． kk k

证明 由a b(modm)、，有 a b mq， 又k(a,b,m)，有

abm

,,均为整数，且 kkk

abm

q， kkk

得

ab m mod ． kk k

定理10 设a,b为整数，n为正整数，

nn

（1）若a b，则 a b a b．

an bn a b an 1 an 2b an 3b2

（2）若a b，则 a b a

abn 2 bn 1 ．

2n 1

b2n 1 ．

ab2n 3 b2n 2 ．

a2n 1 b2n 1 a b a2n 2 a2n 3b a2n 4b2

（3）若a b，则 a b a

2n

b2n ．

ab2n 2 b2n 1 ．

a2n b2n a b a2n 1 a2n 2b a2n 3b2

定义7 设n为正整数，k为大于2的正整数, a1,a2,,am是小于k的非负整数，且

a1 0．若

n a1km 1 a2km 2 则称数a1a2

am 1k am，

am为n的k进制表示． n a110m 1 a210m 2 n a12m 1 a22m 2

定理11 给定整数k 2，对任意的正整数n，都有唯一的k进制表示．如

am 110 am，0 ai 9,a1 0（10进制） am 12 am．0 ai 1,a1 0（２进制）

定理12 （算术基本定理）每个大于1的正整数都可分解为素数的乘积，而且不计因数的顺序时，这种表示是唯一的

n p11p2其中p1 p2

2

pk k，

, k为正整数． （分解唯一性）

pk为素数， 1, 2,

证明1 先证明，正整数n可分解为素数的乘积

n p1p2pm． ①

如果大于1的正整数n为素数，命题已成立．

当正整数n为合数时，n的正约数中必有一个最小的，记为p1，则p1为素数，有

n p1a1，1 a1 n．

如果a1为素数，命题已成立．当a1为合数时，a1的最小正约数p2为必为素数，有

n p1a1 p1p2a2，1 a2 a1 n．

这个过程继续进行下去，由于n为有限数，而每进行一步ai就要变小一次，于是，经过有限次后，比如m次，n就变为素数的乘积

n p1p2

pm．

下面证明分解式是唯一的．假设n还有另一个分解式 n q1q2则有 p1p2

qt， ② pm q1q2

qt． ③

,pm中的

因为等式的右边能被q1整除，所以左边也能被q1整除，于是q1整除p1,p2,某一个pi，但pi为素数，所以pi与q1相等，不妨设pi为p1，有

p1 q1．

把等式③两边约去p1 q1，得 p2p3

pm q2q3qt．

再重复上述步骤，又可得p2 q2，p3 q3， ，直到等式某一边的因数被全部约完，这时，如果另一边的因数没有约完，比如右边没有被约完（m t），则有

1 qm 1qm 2但qm 1,qm 2,

qt． ④

qt 1，这表明等式④不

,qt均为素数，素数都大于1，有qm 1qm 2

可能成立，两个分解式的因数必然被同时约完，即分解式是唯一的． 将分解式按pi的递增排列，并将相同的pi合并成指数形式，即得

n p1 1p2 2

其中p1 p2

pk k．

, k为正整数．

pk为素数， 1, 2,

证明2 用第二数学归纳法证明

n p1p2pm，p1 p2 pm．

（1）当n 2，因为2为素数，命题成立．

（2）假设命题对一切大于1而小于n的正整数已成立． 这时，若n为 …… 此处隐藏：3014字，全部文档内容请下载后查看。喜欢就下载吧 ……