北京大学附属中学(100190) 单治超

“更相减损之术”是中国古代数学专著《九章算术》中提到的用来求两个正整数的最大公约数的算法,是中国古代数学的杰出成就.

“更相减损之术”的正确性可以用现代数学的语言表述如下:

定理1 任给两个正整数a,b,构造一个数列{an},使得a1=a,a2=b,且对任意正整数n,an+2=|an+1-an|,那么{an}中一定存在为0 的项,且第一个为0 的项的前一项就是a,b的最大公约数.

2019 年北京市朝阳区高考一模试题压轴题就是以此为背景命制的.

证明 假设{an}中所有项非0. 那么对任意正整数n,一定有an+2＜max{an+1,an},同理

an+3＜max{an+2,an+1}≤max{an+1,an}.所以max{an+3,an+2}＜max{an+1,an}.

设bn= max{a2n-1,a2n}, 则{bn}是单调递减且取正整数值的数列. 因此对任意n ∈N*,bn+1≤bn-1, 所以bn≤b1-(n-1).n ＞b1+1 时,bn ＜0,与bn是正整数矛盾! 所以{an}中存在值为0 的项.

设m= min{n ∈N+|an= 0}. 由于am-1能整除am,am-1, 所以am-1能整除am-2, 依此下去,am-1能整除a1,a2, 因此am-1能整除a1,a2的最大公约数. 反过来,a1,a2的最大公约数能整除a1,a2,因此能整除a3,依此下去,也能整除am-1. 因此am-1就是a1,a2的最大公约数.

推论 对于定理1 中的数列{an},{an}中第一个为0 的项之后,将是0 与a1,a2的最大公约数交错出现.

下面我们试图把问题一般化: 任给两个正整数a,b,构造数列{an}, 使得a1=a,a2=b, 且对任意正整数n,an+2=|pan+1-qan|(p,q ∈N+). 易见,p=q=1 时,我们就得到定理1 中的数列. 一般情形下,数列{an}会有什么性质呢?

定理2 如果p= 1,q= 2,那么以下三种情况有且仅有一个发生: (1){an}是常数列;(2){an}中存在唯一项为0,且此项之后是一个非零的常数;(3){an}中不存在最大项.

证明 如果a=b,第(1)种情况发生.

如果a/=b,且{an}中存在为0 的项. 设m= min{n ∈N+|an=0}. 易见am+1/=0,且任意n≥m+1,an=am+1.第(2)种情况发生.

如果a/=b, 且{an}中不存在为0 的项. 假设{an}存在最大值M. 设m= min{n ∈N+|an=M}. 如果m ＞1,如果am-2am-1＞0,那么am+1=am-2am-1,am+2=|am+1- 2am| =am+ 2am-1＞ am, 矛盾!如果am- 2am-1= 0, 那么am+1= 0, 矛盾! 如果am- 2am-1＜0, 那么am+1=-am+ 2am-1,am+2=|am+1-2am|=3am-2am-1＞am,矛盾!

如果m=1,由a/=b得a2＜a1,所以a3=2a1-a2＞a1. 矛盾!

定理3 如果|q-p|≥2,那么{an}中不存在最大项.

证明 先考虑q≤p-2 的情形:

如果{an}中存在为0 的项,设m=min{n ∈N+|an=0}, 易见am+1＞0, 从而am+2=pam+1＞am+1, 进而am+3=pam+2-qam+1＞pam+2-qam+2≥am+2,依此下去,对任意n≥m+1,an+1＞an,{an}中不存在最大项.

如果{an}中不存在为0 的项, 那么存在正整数m,am+1≥am,am+2=pam+1-qam≥pam+1-qam+1＞am+1,依此下去,对任意n≥m+1,an+1＞an,{an}中不存在最大项.

再考虑q≥p+2 的情形:

假设{an}存在最大值M. 显然M ＞0.

设m= min{n ∈N+|an=M}, 那么am+2=qam-pam+1≥qam-pam ＞am. 矛盾!

定理4 如果q=p-1,那么以下两种情况有且仅有一个发生: (1){an}从某一项起是常数;(2){an}中不存在最大项.

证明 如果第(1)种情况不发生,当{an}中存在为0 的项时, 证明同定理3 证明中q≤p-2 的第一段; 当{an}中不存在为0 的项时, 把定理3 证明中q≤p-2 的第二段中“存在正整数m,am+1≥am”加强为“存在正整数m,am+1＞am”,后续证明类似.

注 如果a=b,那么{an}是常数列. 但是a/=b时,第(1)种情况也可能发生,例如取p= 3,q= 2,a= 2,b= 1,此时数列是2,1,1,1,...

定理5 (定理2 的一般化)如果q=p+1,那么以下两种情况有且仅有一个发生: (1){an}从某一项起为常数;(2){an}中不存在最大项.

证明 假设{an}存在最大值M. 设m= min{n ∈N+|an=M}. 如果am+1=am, 那么对任意n≥m,an=am, 第(1) 种情况发生; 如果am+1＜ am, 那么am+2=|pam+1-(p+1)am|=am+p(am-am+1)＞am,矛盾!

定理6 (定理1 的一般化)如果p=q≥4,{an}中不一定存在为0 的项,例如a=1,b=2 时,{an}中就不存在为0的项.

证明 设a= 1,b= 2. 我们证明an+2-an+1≥2(an+1-an)且an+2≥2an+1,从而立得结论.

n=1 时显然两个不等式成立.

设n=k(k ∈N+)时两个不等式成立,那么n=k+1

定理7 (定理1 的一般化)如果p=q=2 或3,{an}中一定存在为0 的项.

证明 如果p=q= 2,利用数学归纳法可以证明: 对任意j ∈N,a2j+1,a2j+2都能被2j整除.

假设{an}中不存在为0 的项,对任意i ∈N+,设ai=c,ai+1=d,分类讨论如下表:

ai+2 ai+3 ai+4 ai+5 4(ai+ai+1)-(ai+4+ai+5)d 2d-2c 2d-4c 4c 4d-16c 16c ＞0 c ＞4 2 ＜d 2d-2c 2d-4c 4c 16c-4d 8d-16c ＞0 c ≤4 8 2d-2c 4c-2d 8d-12c 20d-32c 48c-24d ≥0 5 ＜d c ≤2 3 2d-2c 4c-2d 8d-12c 32c-20d 16d-16c ＞0 2 ＜d c ≤8 5 4 2d-2c 4c-2d 12c-8d 12d-16c 8c ＞0 3 ＜d c ≤3 2 1 ＜d 2d-2c 4c-2d 12c-8d 16c-12d 24d-24c ＞0 c ≤4 3 4 2c-2d 6d-4c 16d-12c 20d-16c 32c-32d ≥0 5 ＜d c ≤1 4 ＜d 3 2c-2d 6d-4c 16d-12c 16c-20d 8d ＞0 c ≤4 5 8 2c-2d 6d-4c 12c-16d 44d-32c 24c-24d ＞0 11 ＜d c ≤3 4 2 2c-2d 6d-4c 12c-16d 32c-44d 64d-40c ＞0 3 ＜d c ≤ 8 11 4 2c-2d 4c-6d 8d-4c 28d-16c 24c-32d ＞0 7 ＜d c ≤2 3 1 2c-2d 4c-6d 8d-4c 16c-28d 24d-8c ＞0 2 ＜d c ≤4 7 0 ＜d c ≤1 2 2c-2d 4c-6d 4c-8d 4d 4d ＞0

从上表可知,当