tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

高二数学竞赛讲义 裴蜀恒等式3


高二数学竞赛班二试讲义 第 3 讲 裴蜀恒等式
班级 姓名

一、知识点金
1.欧几里得除法:设 a, b 为整数, b ? 0 ,按下述方式反复作带余除法,有限步之后必然停 止(即余数为零) : 用 b 除 a : a ? bq0 ? r0 , 0 ? r0 ? b 用 r0 除 b : b ? r0 q1 ? r1 , 0 ? r1 ?

r0 用 r1 除 r0 : r0 ? r1q2 ? r2 , 0 ? r2 ? r1 …… 用 rn ? 2 除 rn ?3 : rn?3 ? rn?2 qn?1 ? rn?1 , 0 ? rn?1 ? rn?2 用 rn ?1 除 rn ? 2 : rn ?2 ? rn ?1qn ? rn , 0 ? rn ? rn ?1 用 rn 除 rn ?1 : rn ?1 ? rn qn ?1 则 (a, b) ? rn 实际上,由于余数 r0 , r1 , ??? 为整数,且满足 r0 ? r1 ? ??? ? rn ?1 ? ??? ? 0 ,从而上述的带余除 法有限步后余数必为零。因此

(a, b) ? (bq0 ? r0 , b) ? (b, r0 ) ? (r0 , r1 ) ? (r1 , r2 ) ? ??? ? (rn?1 , rn ) ? (rn qn?1 , rn ) ? rn 给定 a, b , 欧几里得除法不仅能(在有限步内)求出 (a, b) ,还可以证明方程 ① ax ? by ? (a, b) 有一组整数解 x, y ,并能实际地求出一组解。具体的做法是将欧几里得除法倒推回去: rn ? rn ?2 ? rn ?1qn , rn?1 ? rn?3 ? rn?2 qn?1 ,…, r1 ? b ? r0q1 , r0 ? a ? bq0 ,
依次消去 rn ?1 , rn ? 2 , ???, r1 , r0 ,得到一组整数 x, y ,使得 rn ? ax ? by ? (a, b) 。 2. a, b 互素的充分必要条件是,存在整数 x, y ,使得 ax ? by ? 1 等式②称为(互素整数的)裴蜀恒等式。 3.若 a, b 互素,且 a | bc ,则 a | c 。 4.若 p 是素数,且 p | ②

? a ,则至少有一个 a ,使得 p | a
i ?1 i
i

n

i

(1 ? i ? n)
n i

5.若 a1 , a2 , ???, an 两两互素,且 ai | A , i ? 1, 2,3, ???, n ,则 6.设 (a, b) ? d ,则 (

?a | A 。
i ?1

a b , ) ?1 d d

二、例题分析
例 1. 记 Fk ? 2
2k

? 1, k ? 0 。证明:若 m ? n ,则 Fn | ( Fm ? 2)

1

例 2.设 n ? 1 是奇数,证明: n | (1 ?

1 1 ? ??? ? )(n ? 1)! 2 n ?1

例 3. (1)设 n 是正整数,证明: (21n ? 4,14n ? 3) ? 1 。 (2)设 n 是正整数,证明: (n!? 1,(n ? 1)!? 1) ? 1 。 (3)记 Fk ? 2
2k

? 1, k ? 0 。证明:对 m ? n ,有 ( Fm , Fn ) ? 1 。

例 4.设 m, a, b 都是正整数, m ? 1 。证明: (m ? 1, m ? 1) ? m
a b

( a ,b )

?1

2

三、同步检测 1.设 n 是整数,证明: (12n ? 1,30n ? 2) ? 1

2.设 a, b 都是正整数, a ? ab ? 1 被 b ? ab ? 1 整除,证明: a ? b
2 2

3.设 a, b 是正整数,且

b ?1 a ?1 是整数。证明: (a, b) ? a ? b 。 ? a b

3

4.设 m, n 是正整数, m 是奇数。证明: (2 ? 1, 2 ? 1) ? 1
m n

5.求证:若正整数 x, y 使得 2 xy | x ? y ? x ,则 x 是完全平方数。
2 2

4

高二数学竞赛班二试讲义 第 3 讲 裴蜀恒等式
例 1. 法 1: Fm ? 2 ? 2 又2
2
n?1 n

2m

? 1 ? (22 ) 2
n n

n?1

m?n?1

? 12

m?n?1

,所以 (2
n

2n?1
n?1

? 1) | ( Fm ? 2)

? 1 ? (22 ) 2 ? 1 ? (22 ? 1)(22 ? 1) ,所以 (22 ? 1) | (22 ? 1) ,
2n

所以 (2

? 1) | ( Fm ? 2) ,则 Fn | ( Fm ? 2)
20 20 21 22 23 2 m? 2

法 2: Fm ? 2 ? (2 ? 1)(2 ? 1)(2 ? 1)(2 ? 1)(2 ? 1) ??? (2

? 1)(2 2

m?1

? 1)

? F0 ? F1 ? F2 ????? Fn ? Fn?1 ????? Fm?2 ? Fm?1 ,所以 Fn | ( Fm ? 2)
注: 2n ? 1 称为梅森数, 2 ? 1 称为费尔马数。
2n

1 (n ? 1)! 并不总成立。 k 1 1 论证的诀窍是将和 (1 ? ? ??? ? )(n ? 1)! 作配对变形。 2 n ?1 对 1 ? k ? n ? 1 ,因 n 为奇数,故 n ? k ? k , 1 1 n 从而 ( ? )(n ? 1)! ? (n ? 1)! 是 n 的倍数,进而它们的和也是 n 的倍数。 k n?k k (n ? k ) 例 3. (1) ?2(21n ? 4) ? 3(14n ? 3) ? 1 ,所以 (21n ? 4,14n ? 3) ? 1 (2)设 (n!? 1,( n ?1)!?1) ? d ,则 d | n !? 1 , d | (n ? 1)!? 1) 由 (n ? 1)(n!? 1) ? ((n ? 1)!? 1) ? n ,可推得 d | n , 所以 d |1 ,所以 d ? 1 ,故 (n!? 1,(n ? 1)!? 1) ? 1 (3) Fm ? 2 ? F0 ? F1 ? F2 ????? Fn ? Fn ?1 ????? Fm?2 ? Fm?1 ,则 Fm ? xFn ? 2
例 2.对 1 ? k ? n ? 1 , n | 设 ( Fm , Fn ) ? d ,所以 d | 2 ,所以 d ? 1 或 2 。但 Fn 显然是奇数,故 d ? 1 例 4.我们对指数作欧氏除法。

(ma ? 1, mb ? 1) ? (mbq0 ? r0 ? 1, mb ? 1) ? ((mbq0 ? 1)mr0 ? mr0 ? 1, mb ? 1) ? (mr0 ? 1, mb ? 1)
重复上述论证, (m ? 1, m ? 1) ? (m ? 1, m 0 ? 1) ? (m 0 ? 1, m 1 ? 1)
a b b r r r

? ??? ? (mrn?1 ? 1, mrn ? 1) ? (mrn qn?1 ? 1, mrn ? 1) ? ((mrn )qn?1 ? 1, mrn ? 1) ? mrn ? 1 ? m( a ,b ) ? 1 三、同步检测 1. 5(12n ? 1) ? 2(30n ? 2) ? 1 ,有裴蜀恒等式知 (12n ? 1,30n ? 2) ? 1
2. b(a ? ab ? 1) ? a(b ? ab ? 1) ? b ? a ,所以 a ? ab ? 1| b ? a ,
2 2 2

因为 a ? ab ? 1 ? b ? a ,所以 b ? a ? 0 , a ? b
2

3.设 (a, b) ? d ,则 a ? a1d , b ? b1d , (a1 , b1 ) ? 1 ,

b ? 1 a ? 1 b ? b 2 ? a 2 ? a (a ? b) ? (a ? b) 2 ? 2ab ? ? ? ,所以 d | a1 ? b1 a b ab ab 2 所以 d ? a1 ? b1 , d ? (a1 ? b1 )d ? a ? b , (a, b) ? a ? b
4.设 (2 ? 1, 2 ? 1) ? d , d 为奇数, 2 ? 1 ? du, 2 ? 1 ? dv ,
m n m n

2m ? du ? 1, 2n ? dv ? 1, (du ? 1)n ? (dv ? 1)m ,由二项式定理知 dA ? 1 ? dB ? 1, 所以 d | 2 ,又 d 为奇数,所以 d ? 1
5.设 x ? y ? x ? k ? 2 xy ,将上式化成关于 y 的一元二次方程 y ? k ? 2 xy ? x ? x ? 0 ,
2 2 2 2

因为它是整系数的,且两根为整数,故其判别式 ? ? (2kx) ? 4( x ? x) ? 4 x(k x ? x ? 1)
2 2 2

为完全平方数,也即 x(k x ? x ? 1) 为完全平方数,注意到 ( x, k x ? x ? 1) ? 1 ,于是 x 是完全平方数。
2 2

5


推荐相关:

高二数学竞赛讲义 裴蜀恒等式3

高二数学竞赛讲义 裴蜀恒等式3_学科竞赛_高中教育_教育专区。高二数学竞赛班二试讲义 第 3 讲 裴蜀恒等式班级 姓名 一、知识点金 1.欧几里得除法:设 a, b 为...


高中数学竞赛讲义(免费)

高中数学竞赛讲义(免费)_高三数学_数学_高中教育_教育...初等数论 同余,欧几里得除法,裴蜀定理,完全剩余类,...3、方程和不等式 含字母系数的一元一次方程、一元...


【高中数学(竞赛)知识点提纲】

高中数学(竞赛)知识点提纲】_学科竞赛_高中教育_...威尔逊定理 15.7 裴蜀定理 15.8 平方数 15.9 ...16.2 组合恒等式,不等式(参见 9.3) 16.3 存在性...


高中数学竞赛大纲

高中数学竞赛大纲_学科竞赛_高中教育_教育专区。高中...几何不等式; 几何极值问题; 几何中的变换:对称、平移...3.初等数论 同余,欧几里得除法,裴蜀定理,完全剩余系...


高中数学竞赛大纲

高中数学竞赛大纲(2006 年修订试用稿) 中国数学会...几何不等式。 几何极值问题。 几何中的变换:对称、...初等数论 同余,欧几里得除法,裴蜀定理,完全剩余类,...


全国高中数学联赛新规则

全国高中数学联赛新规则_学科竞赛_高中教育_教育专区...几何不等式; 几何极值问题; 几何中的变换:对称、平移...3.初等数论 同余,欧几里得除法,裴蜀定理,完全剩余系...


全国高中数学联赛竞赛大纲

第二数学归纳法; 平均值不等式,柯西不等式,排序不等式,切比雪夫不等式,一元凸...3.初等数论 同余,欧几里得除法,裴蜀定理,完全剩余系,不定方程和方程组,高斯...


高中数学竞赛大纲

威尔逊定理 15.7 裴蜀定理 15.8 平方数 15.9 ...16.2 组合恒等式,不等式(参见 9.3) 16.3 存在性...高中数学竞赛讲义 59页 1下载券喜欢此文档的还喜欢...


全国高中数学联赛竞赛大纲(修订稿)及全部定理内容

3、 几个全国高中数学联赛竞赛大纲及全部定理内容一、平面几何 1、 数学竞赛...(称为裴蜀等式) :若 a,b 是整数,且(a,b)=d,那么对于任意的整数 x,y,...


分好的高中数学竞赛大纲

分好的高中数学竞赛大纲_学科竞赛_高中教育_教育专区。高中数学竞赛大纲(2006 年...函数迭代,简单的函数方程* 3.初等数论 同余,欧几里得除法,裴蜀定理,完全剩余类...

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