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

证明 用容斥原理．设S 1,2,（i 1,2

,n ，记Ai为S中能被pi整除的数所组成的集合

，用Ai表示Ai中元素的个数，有 ,k）

Ai

n

，Aipi

Aj

n,pipj

,A1A2Ak

np1p2

pk

．

易知，S 1,2, A1由容斥原理得

,n 中与n互素的正整数个数为

Ak，

A2

A1

A2Ak S Ai

Aj

1 i k

Ai

1 i j k

k

AiA2

Aj

1 i j m k

Am

1 A1

Ak

1

k

n

1 i k

nnn

pi1 i j kpipj1 i j m kpipjpm

111 pi1 i j kpipj1 i j m kpipjpm

1 1 .

pk

np1p2

k

pk1

pk

n 1

1 i k

1

p1p2

1 1

n 1 1

p1 p2

注 示意n 3的容斥原理．

1

推论 对素数p有 p p 1, p p p．

定理17 整系数不定方程ax by c（ab 0）存在整数解的充分必要条件是

a,b c．

证明 记d a,b ．

（1）必要性（方程有解必须满足的条件）．若方程存在整数解，记为

x x0,

，则

y y0,

ax0 by0 c，

由d|a,d|b， 有d|ax0 by0，得证 a,b |c．

（2）充分性（条件能使方程有解）．若d|c，可设c de由于形如ax by的数中有最小正数ax0 by0满足

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新工程科技数学竞赛中的数论问题(20)全文阅读和word下载服务。