tceic.com
学霸学习网 这下你爽了
相关标签
当前位置:首页 >> 数学 >>

初等数论若干定理及其应用


初等数论的若干定理及其应用

初等数论的若干定理及其应用
1. 几个初等数论的重要定理
若 a,b ? 1 ,则存在整数 u,v ,使得 au ? bv ? 1 。

定理 1

?

?

证明:略。 定理 2 (欧拉定理)若 a, m ? 1 ,则 a

?

?

? ?m ?

? 1?mod m ? 。

首先证明下面这个命题: 对于集合 Z m ? x i 1 ? x i ? m, x i , m ? 1, i ? 1, (即 m 的一 2,? ,? m , 个化简剩余系, 或称简系, 或称缩系) , 考虑集合 S ? ax i mod m i ? 1, 2,? ,? m , 则 S ? Zm 。

?

?

?

? ??

? ?

?

? ??

证明: 1)

由 于

?a, m ? ? 1



?x , m ? ? 1
i

, 则

?ax , m ? ? 1
i

, 因 此

ax i ?mod m ? ? Z m
2)

?x i , x j ? Z m , i ? j







xi ? x j





ax i ?mod m ? ? ax j ?mod m ?。所以 S ? Z n ,从而有 Z n ? S 。
? ?m ?
i ?1

欧拉定理的证明: 由上述命题知 ? x i ?
? ?m ? ? ?m ?
i ?1

? ?m ?
i ?1

? ?ax ?mod m ?? ,
i

显然

?
i ?1

xi ?

? ?ax ?mod m ?? ?
i

? ?m ? ? 1 ? xi 。 即m a a ? ?m ? ? x i ?mod m ? ,
i ?1

? ?m ?

?

?

? ?m ?
i ?1



? ? ?m ? ? ? ? xi ,m ? ? 1 ? ? ? i ?1 ?
? ?m ?

所以, a

? 1?mod m ? 。

1

初等数论的若干定理及其应用 设 p 为质数,且 a, p ? 1 ,则 a

推论 1

?

?

p ?1

? 1?mod p?

证明:显然 ? p ? p ? 1 ,由欧拉定理结论显然。 定理 3 (费尔玛小定理)对于任意质数 p 及任意整数 a 有 a
p

? ?

? a ?mod p?

证明: 1 )若 a, p ? 1 ,由推论 1 ,知 a 2 )若 a, p ? 1 ,则 p a ,从而 a

?

?

p ?1

? 1?mod p? ,从而 a p ? a ?mod p?

?

?

p

? a ? 0?mod p?

定理 4

(威尔逊定理)设 p 为质数,则 p ? 1 ! ? ?1 mod p

?

?

?

?

证明:往证: p p ? 1 ! ? 1 。 当 p ? 2, 3 时,显然结论显然。 当 p ? 5 的奇质数时,记 A ? 2, 3,? , p ? 2 , B ? k 1 ? k ? p ? 1 设 a ? A ,记 Ba ? ka mod p 1 ? k ? p ? 1 。 对于 ka ? B , 因为 a, p ? 1, k , p ? 1 , 所以 ka, p ? 1 ,从而 ka mod p ? B , 即

?

?

?

?

?

?

?

? ?

?

? ?

?

?

?

?

?

?

Ba ? B

又,对于 1 ? i ? j ? p ? 1 ,显然 ai mod p ? aj mod p 所以 Ba ? p ? 1 ,故

?

?

?

?
? ?

Ba ? B

由此,对于 a ? A ,存在 k a ( 1 ? k a ? p ? 1 ) ,使得 ak a ? 1 mod p 成立。 显然 1) k a ? 1 , 2) k a ? p ? 1 , 3) k a ? a 。

否则 1 ) a ? 1 mod p 矛盾 2 ) a p ? 1 ? ?a ? p ? a ? 1 mod p 矛盾 3) a
2

?

?

?

?

?

?

? 1?mod p? , 即 ?a ? 1??a ? 1? ? 0?mod p? , 从 而 p a ? 1 或

p a ? 1 ,这与 a ? A 矛盾。
2

初等数论的若干定理及其应用 即对于 a ? A ,存在 k a ? A ? a ,使得 ak a ? 1 mod p 成立。 从而对于 A 中的 p-3 (偶数)个数,可组成 成立着 ak a ? 1 mod p ,所以 故

??

?

?

p ? 3 个数对 ?a, k a ? , 2

?

?

?a
a? A

? 1?mod p ?

? p ? 1? ! ? ? p ? 1?? a
a? A

? p ? 1 ? ?1?mod p?

定理 3 可进一步表述为 p 为质数的充分必要条件是 p ? 1 ! ? ?1 mod p 。 定理 5 (中国剩余定理)设 m1 , m2 ,? , m k 是两两互素的正整数,那么对于任意整

?

?

?

?

数 a1 , a 2 ,? , a k ,一次同余方程组 x ? a i mod m i , 1 ? i ? k 必有解,且解可以 写为: x ?

?

?

? M N a ?mod m ? , 其 中 m
i ?1 i i i

k

?

?m
i ?1

k

i

, Mi ?

m ,以及 Ni 满足 mi

M i N i ? 1?mod m i ? , 1 ? i ? k ( N i 为 M i 关于模 m i 的逆)
证明:因为 m1 , m2 ,? , m k 是两两互素,所以 m i , M i

?

? ? 1 ,从而存在 a,b ? Z , ? ?

成立着 am i ? bM i ? 1 ,取 N i ? b ,则 M i N i ? ?am i ? 1 ? 1 mod m i 。 令x ?

? M N a ?mod m ? ,
i ?1 i i i

k

( 1)

当 i ? j 时, m i M j 所以 x ?

?MNa
i ?1 i i

k

i

? M i N i a i ? a i ?mod m i ? , 1 ? i ? k

即( 1 )是一次同余方程组 x ? a i mod m i , 1 ? i ? k 的解。 往证:一次同余方程组 x ? a i mod m i ,1 ? i ? k 的任一解 y 均可表示为( 1 ) 的形式。 显然 y ? a i mod m i , 1 ? i ? k , y ? x ? 0 mod m i , 1 ? i ? k ,其中

?

?

?

?

?

?

?

?

x 如( 1 ) , mi y ? x , 1 ? i ? k
又 m1 , m2 ,? , m k 两两互素,所以 m y ? x

3

初等数论的若干定理及其应用

即y ? x ? 定理 6

? M N a ?mod m ?。
i ?1 i i i

k

( 拉 格 朗 日 定 理 ) 设 p 是 质 数 , n 是 非 负 整 数 , 多 项 式

f ?x ? ? a n x n ? ? a1 x ? a0 是 一 个 模 p 为 n 次 的 整 系 数 多 项 式 ( 即
,则同余方程 f ? x ? ? 0?mod p? 至多有 n 个解(在模 p 有意义的情 a n ? 0?mod p? ) 况下) 。 证明:利用数学归纳法证明 1 ) 当 n ? 0 时 , f x ? a 0 , 而 a 0 ? 0 mod p , 所 以 同 余 方 程

??

?

?

f ?x ? ? 0?mod p? 无解。
当 n ? 1 时, f x ? a1 x ? a0 ,而 a1 ? 0 mod p ,且 p 是质数, 所以 a1 , p ? 1 ,进而存在唯一的 b ( mod p ) ,成立着 故 同余方程

??

?

?

?

?

a1 b ? 1?mod p?

a1 x ? a0 ? 0?mod p? ,存在唯一解 x ? ?a0 b?mod p? 。

2 ) 假设当 n ? k 时,命题成立。往证:当 n ? k 时,命题也成立。 反证法:假设,此时同余方程 f x ? 0 mod p 解的个数多于 k 个 不妨,设 0 ? x0 ? x1 ? ? ? x k ? 1 ? x k ? p ? 1 满足

??

?

?

f ?x i ? ? 0?mod p? , 0 ? i ? k
而 f x ? f x0

??

? ? ? ?x

? x0 ?g?x ? ,

因为 ?f ? k ,所以 ?g ? k ? 1 及

?x
?x

i

? x0 ?g?x i ? ? f ?x i ? ? f ?x0 ? ? 0?mod p?,
? x0 , p? ? 1 , 1 ? i ? k g ?x i ? ? 0?mod p? , 1 ? i ? k

i

所以

即 次数为 k-1 的多项式 g x ,至少存在 k 个解,矛盾。 故 命题得证。 定理 7 若 l 为 a 关于摸 m 的阶,s 为某一正整数,满足 a
s

? ?

? 1?mod m ? ,则 s 必为 l

的倍数。
4

初等数论的若干定理及其应用 证明:不妨 l ? 1 ,因为 l 为 a 关于摸 m 的阶,则 a l ? 1 mod m , 且对于 1 ? k ? l , a
k

?

?

? 1?mod m ?
s

( 1)

设 s ? pl ? q , 0 ? q ? l ,则 a 由( 1 )知, q ? 0 。 命题得证。 引理1

? al

? ?a
p

q

? a q ? 1?mod m ?

已知 p 为形如 4q ? 1 为质数,整数 a, b ,满足: p a

?

2

? b 2 ,则 p a, p b 。

?

证明:反证法:若 a, p ? 1, b, p ? 1 ,因为 p a 可设 a
2

?

?

?

?

?

2

? b2

?

? j ?mod p? , b 2 ? ? j ?mod p? ,则
? ?
? ?

a p ? 1 ? a 2 2q ? 1 ? j 2q ? 1 ?mod p? , b p ? 1 ? b 2 2q ? 1 ? ? j 2q ? 1 ?mod p? ,


a p ? 1 ? b p ? 1 ? 1?mod p?,所以 1 ? ?1?mod p? ,而 p ? 3 ,矛盾。

二次同余
模为素数 p 的二次同余式 x 定理 8
2

? a?mod p?,?a, p? ? 1

(欧拉判别条件)设 p 为奇素数, a, p ? 1 ,则
p ?1 2

?

?

1 ) a 是模 p 的平方剩余的充分必要条件是 a

? 1?mod p ? ; ? ?1?mod p ?。

2 ) a 是模 p 的平方非剩余的充分必要条件是 a 证明: 1 ) x
p

p ?1 2

? ? x ? x? x 2 ? ?

? ?

p ?1 2

? a

p ?1 2

? ? p ?1 ? ? a 2 ? 1? x , ? ? ? ? ? ? ? ?
2 p ?1 2

若 a 是模 p 的平方剩余,即 x 又,对于任意整数 x , x 所以
p

2

?

? a?mod p? ,则 ?x ? x ?mod p? ,

? a

p ?1 2

?mod p?,

a

p ?1 2 p ?1 2

? 1?mod p ? 。 ? 1?mod p ? ,及对于任意整数 x , x p ? x ?mod p? ,
p ?1 2

反之,若 a 则 x

? ?
2

p ?1 2

? a

?mod p?,记 y

? x 2 ,n ?
5

p ?1 2

初等数论的若干定理及其应用

由y

n

? a n ? ? y ? a ?? y k a n ? 1 ? k ,
k ?0

n ?1

若 y ? a mod p ,则

?

?

n ?1

k ?0

?y

k

a n ? 1 ? k ? 0?mod p ? ,对于任意的 y 。

由拉格朗日定理,得 a ? 0 mod p ;这与 a, p ? 1 矛盾。 故

?

?

?

?

x 2 ? a?mod p?

2 ) 因为 a, p ? 1 , p 为奇素数,

?

?

? p ?1 ?? p ? 1 ? 2 ? 由欧拉定理,知 a ? 1 ?? a 2 ? 1 ? ? a p ? 1 ? 1 ? 0?mod p ? ? ?? ? ? ?? ?
所以

? p ?1 ? ? p ?1 ? 2 ? ? p a ? 1 或 p ? a 2 ? 1? ? ? ? ? ? ? ? ?
p ?1 2

由 1 )知, a 是模 p 的平方非剩余的充分必要条件是 a

? ?1?mod p ?。

推论 2

设 p 为形如 4q ? 1 质数,则二次同余方程 x

2

? ?1?mod p? 有解。

证明: p ? 4q ? 1 ,

p ?1 p ?1 ? 2q , ?? 1? 2 ? 1 ,由定理 7 ,结论显然。 2
2

推论 3

设 p 为形如 4q ? 1 质数,则二次同余方程 x

? ?1 mod p ? ,?? ? 1? 有解。

?

?

证明: ? p

? ??
?

p ? ? 1 ? p ? 1? ? 4qp? ? 1
? ?

考 察 x

? p?

? ? ? 1 ? ?x 2 ?2qp ? ?? 1?2qp ? ?x 2 ? 1?Q?x ?

, Q x

? ?

为 次 数

4qp ? ? 2 的多项式
若x
2

? ?1 mod p ? 无解,而对于任意整数 x ?

?

?

? p ? ? 1 ? 0?mod p ? ?
?

则对于任意整数 Q x ? 0 mod p

??

?

?

?,显然 p
? ?

?

? 4qp ? ? 1 ? 2

由拉格朗日定理,知 Q x 的系数 ? 0 mod p 故 二次同余方程 x
2

? ?

?

?,矛盾。 ( Q ? x ? 的系数为 1 或 -1 )

? ?1 mod p ? ,?? ? 1? 有解。

?

6

初等数论的若干定理及其应用

2.

若干典型问题
已知正整数 k ? 2 , p1 , p2 ,? , pk 为奇质数 ,且 a, p1 p2 ? pk

问题1 证: a

?

? ? 1 ,试

? p1 ? 1?? p2 ? 1??? pk ? 1?

? 1 有不同于 p1 , p2 ,? , pk 的奇质因数。

证明:当 a ? 1 时,结论显然。不妨 a ? 2 , 因为 p1 , p2 ,? , pk 为奇质数,记 p i ? 2ui ? 1 , ui ? 1 , u ?

?u
i ?1

k

i





? ?p
k i ?1

i

? 1? ? 2 k u

记b ? a

u

a

? p1 ? 1?? p2 ? 1??? pk ? 1?

? 1 ? b 2 ? 1 ? ?b ? 1?? b 2 ? 1
k

k ?1 i ?0

?

i

?

对于 0 ? i ? j ? k ? 1 , b

?

2i

? 1, b 2 ? 1 ? b 2 ? 1, 2 ? 1或2
2i

j

? ?

i

?

对于 0 ? i ? k ? 1 , b ? 1, b 所以,对于 b ? 1 , b
2i

?

? 1 ? ?b ? 1, 2? ? 1 或 2

?

? 1 ?0 ? i ? k ? 1? 这 k ? 1 个数,任意两个数中除了可

能有公因子2,没有其他公因子。 考察 b ? 1 , b
2i

? 1 ?0 ? i ? k ? 1? ,这 k ? 1 个数

⑴ 若 a 是偶数,有 b ? 2m ,此时这 k ? 1 个数是两两互质的奇数。 如果 b ? 4 ,这 k ? 1 个数中,每个数的奇质因数异于其他数的奇质因数。 如果 b ? 2 ,此时, a ? 2 , u ? 1 , p1 ? p2 ? ? ? pk ? 3 , 显然 b
2

? 1 ? 22 ? 1 ? 5 ? 3 。
? 4m?m ? 1? ? 1 ? 1 mod 2 3
2i

⑵ 若 a 是奇数, a ? 3 ,有 b ? 2m ? 1 , m ? 1 , b ? 3 此时 b
2

?

?

当 1 ? i ? k ? 1 时, b

b2 ? 1 ? 5 是奇数,记为 v i ? 1 。 ? 1 mod 2 ,且 2
3

?

?

i

① 若 u 是偶数,显然

b ?1 au ? 1 ? ? 5 是奇数,记为 v1 。 2 2
7

初等数论的若干定理及其应用 若b ? 1 ? a
u

ⅰ)

? 1 有异于 2 的质因数 v 0 ,则 v 0 , v1 ,? , v k ,是两两互质

的奇数,从而至少有 k ? 1 不同的奇质因数。 ⅱ) 若a
u

? 1 无异于 2 的质因数,则 a u ? 2 r ? 1?r ? 3?
u

此 时 必 有 r ? 3, u ? 2 。 (事实上, a

? u ?? u ? ? 1 ? ? a 2 ? 1 ?? a 2 ? 1 ? 2 r , 又 ? ?? ? ? ?? ?

u u u ? u ? ? a 2 ? 1, a 2 ? 1 ? ? 2 , 所 以 , a 2 ? 1 ? 2, a 2 ? 1 ? 2 r ? 1 , 进 而 ? ? ? ?

a ? 3, u ? 2, r ? 3 。 )

不妨 p1 ? 5, pi ? 3 2 ? i ? k ,显然, 3 而3
4?2

?

?

?

4?2

?1 a

?? ?

p1 ? 1 ?? p2 ? 1 ?? ? pk ? 1 ?

?1

?

? 1 ? ?3 ? 1??3 ? 1? 3 2 ? 1 3 4 ? 1 ? 2 5 ? 5 ? 41,
? 1 有质因子 41 ,异于 3 , 5 。

?

??

?

所以 a

? p1 ? 1?? p2 ? 1??? pk ? 1?

② 若 u 是奇数, u ? 3 ,

b ? 1 ? a u ? 1 ? ?a ? 1?? ?? 1? a i ,记为 v1 ?
i i ?0

u ?1

? ?? 1? a
i i ?0 i

u ?1

i



b ? 1 ? a u ? 1 ? ?a ? 1?? a i ,记为 v 0 ?
i ?0

u ?1

?a
i ?0

u ?1



因为 b ? 1, b ? 1 ? a

?

? ?

u

? 1, a u ? 1 ? ?a ? 1, a ? 1? ? 2

?

所以 v 0 , v1 ,? , v k ,是两两互质的奇数,从而至少有 k ? 1 不同的奇质因数。 综上所述, a

? p1 ? 1?? p2 ? 1??? pk ? 1?

? 1 有不同于 p1 , p2 ,? , pk 的奇质因数。 证毕。

注:问题 1 的条件 a, p1 p2 ? pk 结论不是必需的。

?

? ? 1 在证明的过程中没有用到。该条件对于问题的

问题 2

对于自然数 n ,如果对于任何整数 a ,只要 n a

n

? 1 ,就有 n 2 a n ? 1 ,则称

n 具有性质 P 。 1 ) 求证:每个素数 n 都具有性质 P 。 2) 求证:有无穷多个合数也具有性质 P 。 证明: 1 )设 n 是素数,满足 n a
n

? 1 ,即 a n ? 1?mod n? ,又 a n ? a ?mod n?

8

初等数论的若干定理及其应用 所以 a ? 1 mod n ,进而 a i ? 1 mod n 而

?

?

?

?
n ?1 i ?1

n ?1 ? a n ? 1 ? ?a ? 1?? a i ? ?a ? 1??n ? i ?0 ?

? ?a

i

? ? 1? ?

?

因此

n2 a n ? 1

即 素数 n 具有性质 P 。 2 ) 取 n=2p , p 为奇素数,若 n a 显然, a 是奇数, a 因为 n a
n
2

n

? 1 ,往证: n 2 a n ? 1

? 1?mod 4 ?,从而 4 a n ? 1

? 1 ,所以 p a p ? 1 a p ? 1
p

?

??

?
?

①若 p a 又

? ?

p 2 2 n ,必有 p a ? 1 ,则 p a ? 1 ? 1 ,由 1 )

?

?

?4, p ? ? 1 ,
2

所以 n a

2

n

?1

②若 p a

p

? 1 ,即 a p ? ?1?mod p? ,又 a p ? a?mod p?

?

所以 a ? ?1 mod p , a

?

?

i

? ?? 1? ?mod p?
i
p ?1? i

a

p

? 1 ? ?a ? 1?? ?? 1?
i ?0 p ?1? i

p ?1

ai

? ?? 1?
i ?0

p ?1

ai ?

? ?? 1?
i ?0

p ?1

p ?1? i

?? 1?

i

? p ? 0?mod p ?

因此 p a

2

p

? 1 ,故 n 2 a n ? 1

综合①②,命题得证。 问题3 求 所 有 整 数 n ? 2 , 满 足 : 对 所 有 的 整 数 a, b , 且

?a, n? ? ?b, n? ? 1,a

? b?mod n? 的充分必要条件是 ab ? 1?mod n?

解:根据题意,对于满足 a, n ? 1 条件的 a ,必有 a

?

?

2

? 1?mod n?
2

( 1)

如果 n 是素数,记为 p ,则若 a 满足 a, p ? 1 ,必有 a

?

?

? 1?mod p? 。

因此,p ? 5 。 否则, 如果 p ? 5 , 则 p ? 2, p ? 1 , 但 p ? 2 所以

?

?

?

?

2

? 4?mod p?。

p ? 2, 3
9

初等数论的若干定理及其应用 若 p 为 n 的素因子,则 p ? 2, (否则,设 n 有素因子 p ? 5 ,记 n ? p ? q , 3。

? ? 1,? p,q ? ? 1 ,考察同余方程组: x ? 1?mod q ?, x ? 2 mod p ? 。这样的 x 一
定存在(根据中国剩余定理) , 且 x,q ? 1, x, p

?

?

?

?

?

?

? ? 1 , 则 ?x , p q ? ? 1 , 但
?

x 2 ? 1 mod p ? q , 否 则 , 若 x 2 ? 1 mod p ? q , 则 x 2 ? 1 mod p ? , 与 x ? 2 mod p ? 矛盾)
因此

?

?

?

?

?

?

?

?

n ? 2k3l

因为 5, n ? 1 ,所以 5 故

?

?

2

? 1?mod n?

n ? 2, 3, 4, 6, 8, 12, 24
n

问题4

求所有这样的正整数 n,满足存在整数 m,使得 2

? 1 是 m 2 ? 9 的因子。

探索过程:

1) n=1,m 为任意整数都有 2 2) n=2 , m=3 ,则有 2 3) n=3 , 2
n

?

n

? 1 m2 ? 9

??

?

?

n

? 1 m2 ? 9

??

?

?1, ?2, ?3?mod 7? , m 2 ? 0, 1, 4, 2?mod 7? , ? 1 ? 7 , m ? 0,

m 2 ? 9 ? 2, 3, 6, 4?mod 7? ,则 m 2 ? 9 ? 0 mod 2 n ? 1
4) n=4 ,

?

?
3
2

2 n ? 1 ? ?2 ? 1??2 ? 1? 2 2 ? 1

m 2 ? 9 ? 9 26 ? 1 ,

?

?

? , 取 m ?3?2 , 则 ?2 ? 1? ?m ? 9? , ?2 ? 1??m ? 9? , 所 以
2 2

?

?2

n

? 1 m2 ? 9


??

?


5) n=5

2 n ? 1 ? 31

m ? 0, ?1, ?2, ?3,? , ?15?mod 31?



m 2 ? 0, 1, 4, 9, 14, 25, 5, 18, 2, 19, 7, ?2, 20, 14, 10, 14?mod 31?
则m
2

? 9 ? 0 mod 2 n ? 1

?

?
2

6) n=6 , n=7 ,对于任意 m ,都有 m 7) n=8 , 2
n

? 9 ? 0 mod 2 n ? 1

?

?

? 1 ? ?2 ? 1??2 ? 1? 2 2 ? 1 2 4 ? 1 , 取 m ? 3 ? 13 , 则
10

?

??

?

初等数论的若干定理及其应用

m 2 ? 9 ? 9 132 ? 1 ? 3 2 ? 2 ? 5 ? 17 ,所以 2 n ? 1 m 2 ? 9
由上述探索过程,可猜测: 满足 存在整 数 m, 使 得 2n ? 1 是 m
2

?

?

?

??

?

? 9 的因子成立的 n 应具有这样的形式

n ? 2 k ?k ? 0, 1, 2,?? 。
解 满足 存在整 数 m, 使 得 2n ? 1 是 m
2

? 9 的因子成立的 n 应具有这样的形式

n ? 2 k ?k ? 0, 1, 2,?? ,其他的 n ,则不成立。
现证明上述结论,首先,证明:满足存在整数 m,使得 2 n ? 1 是 m 立的 n 应具有这样的形式 n ? 2
k
2

? 9 的因子成

?k

? 0, 1, 2,?? 。
r

反证法:若 n 不具有形式 2 ,则 n 可表示为 2 s , r ? N , s ? 3 为奇数,
k

?2

s

? 1 2 n ? 1 m 2 ? 9 , 2 s ? 1 ? ?1?mod 4 ? ,

??

??

?

2 s ? 1 具有形如 p ? 4u ? 1 的素因子 ?u ? 2? ,
因为 p m

?

2

? 9 ,由引理,知 p 3 ,这与 p ? 4u ? 1 ?u ? 2? 矛盾。
k

?

再证:对于 n ? 2 子。

?k

? 0, 1, 2,?? ,必存在整数 m ,使得 2 n ? 1 是 m 2 ? 9 的因

当 k=0,1时,显然。 不妨 k ? 2 , 此时, 2
n

? 1 中形如 p ? 4u ? 1 的素因子,只有 3 。事实上,这样的素因子 p ,
p ?1

满 足 : p 2

?

? 1 ( 费 尔 马 小 定 理 ), 因 此 , p 2 n, p ? 1 ? 1 , 而
, 4u ? 2 ? 2 , u=1 , p=3 。 且 2 n ? 1 ? 0?mod 9? ( 否 则 , 若

?

??

?

?

?n, p ? 1? ? ?2

k

?

2 n ? 1?mod 9? , ? ?9? ? 6 ,则 6 n 矛盾)
因此, 2
n

? 1 可表示为 3? ,其中 ? 的素因子具有形式 p ? 4u ? 1
2

寻找 s ,使得 ? s 令2
n k

? 1。
?

? 1 ? 3? p i i ,其中 p i 为形如 4u ? 1 的素数,构造同余方程组
i ?1

11

初等数论的若干定理及其应用

x ? x i mod p i i ?i ? 1, 2,? , k ? ,其中 p i i x i2 ? 1 ,这样的 x i 一定存在(根据
?
?

?

?

推论3) 。 根据中国剩余定理,同余方程组的解存在。 令 s ? x , m ? 3 s ,则有 2
n

? 1m2 ? 9 。

问题5

a 3 ? b3 证明:每个正有理数能被表示成 3 的形式,其中 a, b, c, d 是正整数。 c ? d3 p ? Q ? ,其中 p, q ? N ? , ? p, q ? ? 1 q

证明:对于任意正有理数

在两数 3

q 2q x ,3 之间,必存在有理数 ? Q ? ,其中 x, y ? N ? , ?x, y ? ? 1 , p p y
3

满足:

3

q x ? ? p y
3

2q 。 即 p
3

q x3 2q p x3 ,1 ? ? 3 ? ? 2 p p q y3 y

令 A ? px , B ? qy ,则 B ? A ? 2 B 因为

?A ? B ? ? ?2 A ? B ? , A ? B ?A ? B ?3 ? ?2 B ? A?3
3 3

所以

p y 3 ? A ? B ? ? y 3 ?2 A ? B ? ? 3 3 q x 3 ? A ? B ? ? x 3 ?2 B ? A?
3 3



a ? y?A ? B ?,b ? y?2 A ? B? ? 0 c ? x?A ? B?,d ? x?2 B ? A? ? 0



a, b, c, d 为正整数,满足:

p a 3 ? b3 。 ? 3 q c ? d3

命题得证。

问题6 倍数。

设 p 是质数,证明:存在一个质数 q,使得对于任意整数 n,数 n

p

? p 不是 q 的

?1, ?2 ,则 n 2 ? r 2 ? 0, 证明:若 p=2,取 q=5,设 n ? 5 s ? r , r ? 0, 1, 4 mod 5
即n
2

?

?

? 2 ? 0?mod 5?
12

初等数论的若干定理及其应用

若 p ? 3 为奇素数, p 显然 记

p

? 1 ? ? p ? 1?? p i ,令 M ?
i ?0

p ?1

?
i ?0

p ?1

pi

M 是奇数。

PM ? q ? P q M , P 表示全体素数的集合 S ? kp 2 ? 1

?

?

?

?kp

2

? 1 M , k ? N , kp 2 ? 1 ? P

?

?



PM ? S ? ? 。否则, M 的任一素因子都将具有形式 kp 2 ? 1 ,

kp 2 ? 1 ? 1 mod p 2 ,所以
但M ?

?

?

M ? 1 mod p 2

?

?

?
i ?0

p ?1

p i ? p ? 1 mod p 2 ,矛盾。

?

?

取 q ? PM ? S ,显然 q 是奇数, q p 往证:数 n
p

?

p

?1。

?

? p 不是 q 的倍数。
p

反证法:假设 n 从而有 n
p2

? p?mod q ?
又 p, q ? 1 ,

? p p ? 1?mod q ? ,及 ?n, q ? ? 1 ,
n q ? 1 ? 1?mod q ?

?

?

由欧拉定理的推论,知 所以 而
2

n

? p ,q ? 1? ? 1?mod q ?
2

? p ,q ? 1?可能的取值为 1, p, p ?
2

2

1 )显然 p , q ? 1 ? p ,否则, q ? kp
2 2

?

2

? 1 ,这与 q ? S 矛盾。

2 )若 p , q ? 1 ? 1 ,则 p ? n 又qM , M ?

?

?

p

? 1?mod q ? ,即 q ? p ? 1?

?
i ?0

p ?1

p ? p ?
i

? ?p
p ?1 i ?0

i

? 1 ,所以 q p

?

从而 q p ? 1, p , q ? 1 矛盾。 3 )若 p , q ? 1 ? p ,同样有 p ? n
2

?

?

?

?

p

,矛盾。 ? 1?mod q ? ,同 2 )

综合 1 ) , 2) , 3) ,假设 n 故命题得证。

p

? p?mod q ? ,不成立。

13

初等数论的若干定理及其应用 已知斐波那切数列 Fn ,满足

问题 7

? ?

F1 ? 1, F2 ? 1, Fn ? 2 ? Fn ? 1 ? Fn ,n ? N ? ,
设 p 为大于 5 的素数,试证: p F p ? 1 F p ? 1 ? 1

?

?

n n ? ? ?1 ? 5 ? ? 1 ?? 1 ? 5 ? ? ? ? ? ?, n ? N ? 证明:斐波那契数列的通项公式 Fn ? ? ? ? ? ? ? 2 2 5 ? ? ? ? ? ? p ?1 对大于 5 的素数 p ,由费尔马小定理可知, 5 ? 1?mod p?

?

?

? p ?1 p 5 p ?1 ? 1 ? ? 5 2 ? ? ? p ?1 ? p ?1 ? 又 ? 5 2 ? 1, 5 2 ? 1? ? ? ? ? ? p ?1 ? ? ? p ?1 2 ? ? ? 1 或 p ?5 2 ∴ p 5 ? ? ? ? ? ?


?

?

?? p ? 1 ? 1 ?? 5 2 ? 1 ? , ?? ? ?? ? ? p ?1 ? ? 5 2 ? 1, 2? ? 2 ? ? ? ? ? ? 1? ? ?

? p ?1 ? 1) 如果 p ? 5 2 ? 1 ? ? ? ? ? 1 2 p Fp ?1 ? 1 ? 2 5 p 1 ? ? 1? 5 ? 1 2? ?

?

?

?

? ?
p ?1 2 k ?0

?1 ? ? ? ?
2k ? 1 p

?

5

?

p ?1

? 1?

?

5

?

p ?1

p 1 ? 5 ? ? 1? ? ? ? 2 5 ?

?

?

5

? ? ?1 ? 5 ? ??? ? 2
p p
p

? ? 2p ? ?

p

?

k ?0

?C

p ?1 2

2k p

5k ?

?C

5k ? 2 p
k

(1)

因为,当 k ? 1, 2,? , p ? 1 时, p C p ,即由费尔马小定理 2 所以 从而

? 2?mod p?

2 Fp ?1 ? 1 ? 1 ? 5
p
p ?1

? p ?F

? ? 1?
?

p ?1 2

? 2 p ? 1 ? 1 ? 2 ? 0?mod p?

? p ?1 ? p 2) 如果 p ? 5 2 ? 1 ? ,类似计算可得 2 F p ? 1 ? 0?mod p? ,进而 p F p ? 1 ? ? ? ?
综合 1)2) ,得 p F p ? 1 F p ? 1 ? 1 。 问题 8
2 1

?

对 于 正 奇 数 n n ? 2011 , 若 存 在 正 奇 数 x1 , x 2 ,? , x n , 满 足
2 2 2 n

?

?

x ? x ??? x

? n ,求满足条件的正奇数 n 的总和.
4
4

解:由 n 为正奇数得: n

? 1?mod 8?

又由 x1 , x 2 ,? , x n 为正奇数得: x i ? 1 mod 8
2

?

?

14

初等数论的若干定理及其应用 ∴ n ? x1 ? x 2 ? ? ? x n ? n
2 2 2 4

另一方面:若 n ? 1 mod 8 ,可以找到满足条件的正奇数 x1 , x 2 ,? , x n 当 n ? 1 时,则 x1 ? 1 ; 当 n ? 8k ? 1 k ? N
4 4

?

?

? 1?mod 8?

? ?8k ? 1? ? ?8k ? 1? ? ?8k ? 1?
2

n 4 ? ?8k ? 1? ? ?8k ? 1? ? ?8k ? 1? ? ?8k ? 1?
4 4

?

?

?时,

4 2

? ?8k ? 1? ? 32k 128k 2 ? 2
4 4 2 4 4 2

?

2

? ?8k ? 1? ? 4k ?32k ? 1? ? ?16k ? 1? ? 92k ? 1
2 2 2 2

?

?

???8k ? 1?

2

? ?8k ? 1?

?

? ?k ? 1? 9 2 ? 3 2 ? 12 ? 12 ? 9 2 ? 3 2 ? 12 ∴ 共 1 ? 4k ? 1 ? 4?k ? 1? ? 3 ? 8k ? 1 个正奇数的平方和.
综上: n ? 8k ? 1 k ? N , 则其总和为

? ?8k ? 1? ? 4k ?32k ? 1? ? ?16k ? 1?

? ?8k ? 1? ? 4k ?32k ? 1? ? ?16k ? 1? ? 92?k ? 1? ? 91

?

? ?

?

?

?

k ?0

? ?8k

251

? 1? ? 253260。

问题 9



n ? N ? ,n ? 1 , 正 整 数 数 组

?a ,a
1

2

,? ,a n ? 满 足 :

a1 ? a 2 ? ? ? a n ? 2n ,如果不能将 a1 ,a 2 ,? ,a n 分为和相等的两组数,那么称数
组 a1 ,a 2 ,? ,a n 为“优秀的” ,求所有的“优秀的”数组. 解:设数组 a1 ,a 2 ,? ,a n 为“优秀的” ,对 1 ? k ? n ,考虑下面的 n ? 1 个数:

?

?

?

?

a k ,a k ? 1 ,a k ? a k ? 1 ,a k ? a k ? 1 ? a k ? 2 ,? ,a k ? a k ? 1 ? ? ? a k ? n ? 1 , 其 中
an ? i ? ai
由于不能将 a1 ,a 2 ,? ,a n 分为和相等的两组数,即其中没有若干个数之和等于 n , ∴上面的 n ? 1 个数中,除 a k ,a k ? 1 外,其余任意两项关于模 n 不同余,否则这两项 之差等于 n . 另外,上面的 n ? 1 个数中,必有两个数模 n 同余,

2,? ,n 都成立 ∴ a k ? a k ? 1 mod n 对 k ? 1,
∴ a1 ? a 2 ? ? ? a n mod n

?

?

?

?

∴ a1 ? a 2 ? ? ? a n ? 1 或 2 mod n

?

又 a1 ? a 2 ? ? ? a n ? 2 n

?

综 上 : 当 n 为 奇 数 时 , a1 ,a2 ,? ,an 中 有 一 个 是 n ? 1 , 其 余 都 是 1 ; 或

a1 ? a 2 ? ? ? a n ? 2 ;
当 n 为偶数时, a1 ,a 2 ,? ,a n 中有一个是 n ? 1 ,其余都是 1.

15


推荐相关:

初等数论中的几个重要定理

初等数论中的几个重要定理 基础知识 定义 (欧拉(Euler)函数) 一组数 且对于...下面我们着重对 Fetmat 小定理及其应用来举例: 例3.求证:对于任意整数 , 是...


初等数论(四)-几个著名的数论定理

初等数论(四)-几个著名的数论定理_学科竞赛_高中教育_教育专区。初等数论(四)...(即,由 a 的若干倍生成) ,从而凡是与 b 有关的数论问 题(在模 m 的...


《初等数论》教学大纲

本课程的目的是简单介绍在初等数论研 究中经常用到的若干基础知识、基本概念、...2、孙子定理 (1)孙子定理;(2)孙子定理应用。 3、高次同余式的解数及解法...


初等数论中的几个重要定理 高中数学竞赛

初等数论中的几个重要定理基础知识 定义(欧拉(Euler)函数)一组数 的, 的剩余...下面我们着重对 Fetmat 小定理及其应用来举例: 例 3.求证:对于任意整数 , 是...


浅谈同余及其应用

浅谈同余定理及其应用摘 要 初等数论是研究数的规律,特别是整数性质的数学分支。...本文归纳总结了 同余的若干性质,结合实例,探究了同余性质在检验、判断整除问题、...


初等数论精品课程申请及大纲

本课程的目的是简单介绍在初等数论研究中经常用到的若干基础知识、基本概 念、...难点:整数的素数分解定理的理解与运用函数[x]、{x}的概念及其应用。 (三)...


第五节初等数论中的几个重要定理

第五节初等数论中的几个重要定理_学科竞赛_高中教育_教育专区。第五节基础知识...1480. k ?0 k ?0 k ?0 9 9 9 下面我们着重对 Fetmat 小定理及其应用...


初等数论期末复习资料201406

问题的若干方法, 熟练掌握本章中二个著名的定理: 带余除法定理和算术基本定理...(4)[x]的性质及其应用,n!的标准分解式。 四、自学指导 整除是初等数论中最...


初等数论在中学数学竞赛中的应用

2 整除理论及其应用初等数论是研究整数基本性质的一门十分重要的数学基础课程,由此而言,初 等数论的基础便是整除理论了,而最大公约数理论和算术基本定理则是初等...


初等数论总复习

问题的若干方法,熟练掌握本章中二个著名的定理:带余除法定理和算术基 本定理。...(4)[x]的性质及其应用,n!的标准分解式。 四、自学指导 整除是初等数论中最...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com