证明：这个过程是有限的，并且最终的结果是唯一的． （2008-第69届Putnam试题）
证：设?p1,p2,?,pm?为a1,a2,?,an的全部素因子的集，将每个ak都表成标准分解式：
?k1?k2?kmak?p1p2?pm,k?1,2,?,n，?ki?0,i?1,2,?,m，由此作出n?m矩形数
表A：
?11?12??1m?21?22??2m????
?n1?n2??nm对于aj?p1j1p2j2?pmjm与ak?p1k1p2k2?pmkm，(j?k)，若记
???????i?min(?ji,?ki),?i?max(?ji,?ki),i?1,2,?,m，则
?m?m?2?1?2(aj,ak)?p1?1p2?pm,[aj,ak]?p1p2?pm
因此，当对aj,ak进行所述操作后，数表A中的第i行与第j行即被右表B所取代；
?????????????j1?j2??jm?k1?k2??km?????1?2??m?????1?2??m ????
其中第i行与第j行所对应的子表中，每列上的数?ji与?ki都进行了调整，使得较小数排在上方，而较大数排在下方；称为第i行与第j行的“序调整”，显然，经有限多次序调整后，数表A最终化为数表C，其中表C每一列的数，从上到下就是表A相应列中的各数自小到大的排列．若设表C为：
x11x21?xn1x12?x1mx22?x2m???xn2?xnmxxx
与表C对应的n个数为c1,c2,?,cn，ck?p1k1p2k2?pmkm,k?1,2,?,n，由于表C唯一，则最后的数列
c1,c2,?,cn唯一．（对任意j?k，都有cjck）
16、数列{an},{bn}满足:a0?b0?1,an?1??an??bn, bn?1??an??bn,其中
?,?,?为正整数,???,且????2?1.
证明:?n?N,an?bn必可表为两个正整数的平方和.（06-国家队训练题）
引理1. 若正整数m,n,k满足：mn?k?1，则存在x1,x2,y1,y2?N，使以下三式：
22m?x12?y12, n?x2?y2, k?x1x2?y1y2 同时成立.
2不妨设m?n，对k归纳，k?1时，由于mn?2，则 m?1, n?2，此时有
m?02?12, n?12?12, k?0?1?1?1，即k?2时结论成立.
2设当k?r ?r?2?时结论成立，当k?r时，由mn?r?1??○1
r2?1r2?1r2?r则n?r?1, m????r，故可令n?r?s, m?r?t, (s,t?N*)
nr?1r?1221式成为 ?r?t??r?s??r?1 ? ?○2，即rs?ts?tr?1，两边同加t得， ○
3，因为r?t?m?0, 故s?t?0, s?t?0, t?r， ?r?t??s?t??t2?1 ? ?○
t?m?nt2, mm?由归纳假设知，存在m1,m2,n1,n2?N，使r?t?m1?n1s, ?222222122nn?12
22即m?r?t?m1?n1, n?r?s??r?t???s?t??2t??m1?m2???n1?n2?
r??r?t??t?m1?m1?m2??n1?n1?n2?，
若记 x1?m1, y1?n1, x2?m1?m2, y2?n1?n2，
则在○1式中有m?x1?y1, n?x2?y2, k?x1x2?y1y2，x1,x2,y1,y2?N， 即k?r时结论成立，
由归纳法，证得引理1成立.
引理2 . ?m,n?N, 有 am?n?bm?n?aman?bmbn??○4.
证：只要证，对于 0?k?m?n, 有am?n?bm?n?akam?n?k?bkbm?n?k??○5. 对k归纳，k?0时结论显然;
2222k?1时，由于 am?n??am?n?1??am?n?1，bm?n??am?n?1??bm?n?1，则 am?n?bm?n??????am?n?1??????bm?n?1?a1am?n?1?b1bm?n?1.
设当k?p时有am?n?bm?n?apam?n?p?bpbm?n?p，则当k?p?1时，am?n?bm?n?
?apam?n?p?bpbm?n?p?ap??am?n?p?1??bm?n?p?1??bp??am?n?p?1??bm?n?p?1? ???ap??bp?am?n?p?1???ap??bp?bm?n?p?1?ap?1am?n?p?1?bp?1bm?n?p?1.
故○5成立，再于○5中令k?m，则有 am?n?bm?n?aman?bmbn，引理2得证.
回到本题，据引理2，在○4中，令m?n，则有：a2n?b2n?an?bn； 又取 m?n?1，有a2n?1?b2n?1?an?1an?bn?1bn???an??bn?an???an??bn?bn
22222??an??bn?2?anbn??x12?y12?an??x2?y2?bn2?2?x1x2?y1y2?anbn
22??x1an?x2bn???y1an?y2bn?. 因此结论得证.
2217、设p为奇质数，a,b是小于p的正整数，证明：
?2an??2bn?a?b?p的必要充分条件是：对任何小于p的正整数n，均有????p??正奇数.
p????（其中方括号???表示取整.）（99-南昌赛题）
证明：必要性：若a?b?p,n是小于p的任一正整数，记??2an??2bn??u,?v，因p为????p??p?质数，故
2an2bn2an皆不为整数，因此有?,?,0???1,0???1, 使 ,?u??,
ppp2bn?v??, 相加得，2n?u?v??????，故???为整数，由于 0?????2，则p必有????1, 从而 u?v?2n?1?奇数.
充分性：若对任何小于p的正整数n，均有 ??2an??2bn?1 ???p??正奇数???○p????令c?p?a，则 a?c?p，据必要性的讨论可知，对任何小于p的正整数n，均有
?2an??2cn?2，因此由○1，○2，对任何小于p的正整数n，均有 ?p???p??正奇数???○
?????2bn??2cn?3，由○3进而可得，对任何正整数m，均有 ?p???p??偶数???○
?????2bm??2cm?4，（事实上，设m?pt?n,0?n?p,，则 ?p???p??偶数???○
?????2bm??2cm??2b?pt?n???2c?pt?n???????2bt?2ct??p???p???pp?????????2bn??2cn??p???p??偶数 ????为证充分性，只要证，b?c，用反证法，假若b?c，不妨设b?c，则
1?b?c?p，因p为质数，有 ?2?b?c?,p??1，因此有正整数m与k，使 2?b?c?m?pk?1??○5，据此知，k必为奇数，且
2cm12cm12bm2cm16，显然，（否则，若??整数，???k??○??整数，
ppppppp则由○6，
12bm2cm为整数，因?2b,p??1，则pm??整数??整数，矛盾）.
ppp今由
?2cm1??2cm?2cm1????，现对○6式两边取整，得 ??整数，则??p??p?pp?p?2bm??2cm??2bm??2cm??2cm?????，因此24式矛盾. ?p??p??p??p??p??k?奇数，这与○??????????故原假设不真，因此b?c，即 b?p?a，所以 a?b?p.
18、若三角形的三条边长皆为有理数，且有一个内角的角度数也是有理数，试求该内
角度数的所有可能的值．并给出所有这种三角形边长的一般表达式．（集训队训练题）
m0m??1800，解：设?ABC中，，其内角A? BC?a,CA?b,AB?c,(a,b,c为有理数）
n1n由于对三角形作相似变换，并不改变其内角值，故可设a,b,c皆为正整数。据余弦定理，
b2?c2?a2m2cosA??有理数，而nA?m?1800,则cosnA?cos?m?1800????1?，设
bcx?2cosA,?k??*,记fk?2coskA,则f1?x,f2?x2?2,?,且由三角和差化积公式，
cos?k?2?A?coskA?2cosA?cos?k?1?A，即有 fk?2?xfk?1?fk，f1?x, f2?x2?2,??①
据递推关系①立知，?k??,fk为首项系数为1的x的k次整系数多项式. 记 fn?x?an?1xnn?1*???a1x?a0,(ai为整数），注意fn?2???1?，有
mmxn?an?1xn?1???a1x?a0?2??1??0??②，而x?2cosA是方程②的有理根.
