nq 1

pq



pn 1
p

q

.
证明留作练习。
注：对0< 1,易证

pn
pq



pn 1
Hale Waihona Puke pq 事实上，pn ＝ pn 1 1
pq pq pq
由于0 1 1 , pn 1 pn pn 1 1
，p}使得a
n＝m
。显然
k
n=#sl | sl mk , s 1, 2, , l {1，2， ，p},
其中＃ 表示集合 中元素的个数。由于
sl

m k

s

m k l
从而对于任意固定的l满足s

m k l
的正整数s的个数为

m l
k

再由任意不同的l1和l2
即n，G nF 1, F 2, .
反之，若m F 1, F 2, ，由于F 0＝0，
存在非负整数使得F k m F k 1，即
m＝F k a，其中1 a F k 1 F k 1＝f k 1 f k
称它们关于正整数集互补。－－－1959美国普特南竞赛题
关于求正整数集的补集有以下一般的结果。
设f n为正整数集到自身的不减函数，且lim f n＝ nx
对任意正整数n，令
f * n #k | k为正整数且f k n
由于f (n)为不减函数（f(n) f(n+1,n)）,从而
k使得f k n，即
r 1 k n
1
显然1 k n ,即f* n是小于 n 的最大的k。
n 1
r 1

f
* (n)

r
n
1
,当
r
n 不是整数 1

r
n
1
1, 当
r
n
1
是整数
由于k
q 1 1 n 1 q 2
2
4
f * n q 1即
f
*

n


q,当n q2
q
1,当n

q
s,0 s 2 s,q
q s
2q
.
可以证明
f
*

n



1 2

n



n



n
n

,
其中 n 表示最接近 n的整数.
pn 1
p

q

当
pn 1 不是整数时，则 pq
pn 1 pq


pn 1
p
q

1
即令m＝
ppnq1，则 m 1
pn 1 0. pq
m 1 p q pn 1 1.
m 1 pn pq
代数 数论 几何 组合的解题技巧
1. 从 2007 年联赛加试第三题谈起――正整数子集的补集。 2. Pull 方程及应用 3. 复数与多项式 4. 多项式的构造与应用
设P＝{1，2，3，4，5}，对任意k P和正整数m，
记f

m，k
5
＝

m
k

1
,
i＝1 i 1
求证对任意正整数n，存在k P和正整数m，使得f m，k ＝n。
mk q n l
j
j
当j

k，l时，则m
k j
，n
l j
均为无理数，则
m
k j
＝
n

l j

。
当j＝k但j l 此时k l ，显然m k ＝m，n l 是无理数，
j
j

n
l j
＝m＝
解：1 r为无理数1959年普特南赛题
an

n

r
n 1

r
r
1
n
.
(2).r是有理数。不妨设r＝ p ，其p，q均为正整数且p>q 1.令 q
fn rn n r 1 n.对于任意正整数n，则f* n是最大的非负整数
{1，2，
，p}和任意正整数s1和s
都有
2
s1l１

s2
。于是
l２
n
p l＝1
m
ｋ l


f
m, k
证明二：令bn

p j＝1

n j
,
证明

b1, b2 , b3,
2
是正整数列。不妨设1 2 p。显然a1＝1，


l
n
l
n


k,k l
k

n
k
1l
k
1 .
于是
f
* n

l
n
l
n

.
所求
an

n
l
n
l
n

,
n
1, 2,3,
若正整数m，k和l，j使得mk＝l j，则必须且只须m＝l，k＝j。 于是M是由两两不同元素组成的无穷数集。易证M可以按由小到大
的顺序排成一个无穷数列：
a1, a2 , a3, , an ,
1
证明一：计算数列1的项数n。任意给定正整数n，an M，
即存在唯一的正整数m和k
{1，2，
上题是下题的特殊情况：
已知给定正数1，
，
2
，
，设
p
k j
k

j 都是无理数，
记f
m，k
p
＝
j＝1
m
k j
。求证对于任意正整数n，存在
k {1，2， ，p}，和正整数m，使得f m，k ＝n。
证明：证明的关键是想到集合M＝mk|m＝1，2， ，k＝1，2， ，p
取n＝f k a，则G n n f * n＝f k a k＝F k a＝m
练习: f* * ?证明你的结论。
例1。设r>1，从正整数列中删去rn | n 1, 2,3, 所得之数列记为
a n , 求 a n 的通项公式。
n

nq
, nq
nq p q k
k
0
r 1 p q p q
pq
nq ( p q)k 1
k nq 1. pq
于是f
* (n)


nq 1
p

q

.
可以证明an

n
f * (n)
n


nq 1
p

q

f* (n) max{k | k为正整数且f(k)<n}
即对于n若k满足
f k n f k 1
则k f * n.显然f * 1＝0，f * m＝0 f n m,n
可以证明f * n为正整数集到非负整数集的不减函数且 lim f * n＝ 。 n
f k n f k 1
1
即n f k a,其中1 a f k 1 f k
由1可知f * n＝k。于是
G n n f * n＝f k a k＝F k a
F k G n F k f k 1 f k F k+1
b1＝1。
p
任取正整数s，则bs＝
j＝1
ａ sj

p
，bs+1＝

j＝1
ａ

s+1
j
。设a
s＝m
k，a
s+1＝n
。
l
由1的定义可知mk和nl之间不存在M中的数，即不存在正整数q和
j{1，2， ，p}使得
mk q j nl
即
由于kl k k 1l
n l n kl k 1 k 1 kl
l n l n k.
又当n k 1l k 1时， n l n k 1l k 1 l k 1l k 1 k 1l
l n l n k 1
f

md


m

m


1

1

m
,
m

1,
2,
3,
f m,２ m m 1 m , m 1, 2,3,
记x＝1，y＝1 1 ，则x，y为无理数且 1 1 ＝1。则

xy
xm | m＝1，2，3， ，ym | m＝1，2，3， 合起来恰好组成正整数列，
可以证明n f n | n 1, 2,3, 和n f * n | n 1, 2,3,
关于正整数集互补。(Lamher Moser)
证：记F n n f n,G n n f * n.不妨设f 0＝0。对任意正整数
n，有非负整数k使得
pq pq pq pq pq pq


pn 1
p
q



pn
pq

当 pn 1 是整数时，由 pq