第65届IMO暨首届INO第一天NT大本营中官方认证为NT的一道题。
P2:
求所有的正整数对(a, b)，使得存在正整数g和N，对于所有的整数n ≥ N都满足 gcd(an + b, bn + a) = g。（注：gcd(x, y)表示整数x和y的最大公约数。）
随着n的增长，两个与n有关的整数相应递增，但当n大于等于某个足够大的正整数 N以后，这两个数的最大公约数有可能固定于某个常数g吗？
当然可能。
比如，我们构造两个正整数kn和k(n + 1)，k为一个给定的正整数。因为n和n + 1互质，所以当n ≥ 1时，这两个数的最大公约数始终为k。
具体到这道P2，首先我们可以从递增的严格性入手。
注意到随着n增长，an + b和bn + a递增，但可以不严格递增。这意味着an + b和bn + a本身保持恒定不变，此时幂的两个底数a和b等于1。
因此，一组平凡解(1, 1)是显而易见的。相应地，g = 2，N = 1。
进一步，考虑(k, k)，k > 1。
此时，an + b = bn + a = kn + k。
g = gcd(an + b, bn + a) = kn + k。
当k ≠ 1时，不论是否n ≥ N，kn这一项显然不能保持恒定。无解。
因此除平凡解以外，必然有a ≠ b。不失一般性，假设a < b。
特殊地，当a = 1，1 < b时，
令n = N，gcd(1 + b, bN + 1) = g，有
g|1 + b和g|bN + 1。显然，b和g互质。
令n = N + 1，gcd(1 + b, bN + 1 + 1) = g，有g|bN + 1 + 1。
所以，g|(bN + 1 – bN)，即g|bN(b – 1)。
因为b和g互质，所以g|b – 1。结合g|1 + b可知g = 2。
当n ≥ N的奇数时，1 + b|bN + 1，所以
g = gcd(1 + b, bN + 1) = 1 + b
因此，b = 1。
可知除了(1, 1)这组平凡解，并无形如(1, b)的其他解，因此我们可以假设1 < a < b。
接下来考虑n ≥ N，
由g|aN + b得到g|aN + 1 + ab
结合g|aN + 1 + b，得出g|ab – b
显然ab + 1和a互质，构造
M = kφ(ab + 1)
其中，φ是欧拉函数；k是一个足够大的正整数，使得M ≥ N + 1。
因为ab + 1和a互质，根据欧拉定理，
aφ(ab + 1) ≡ 1 (mod ab + 1)
所以，aM ≡ 1 (mod ab + 1)
aM – 1 + b ≡ 1/a + b ≡ (ab + 1)/b ≡ 0 (mod ab + 1)
即，ab + 1|aM – 1 + b
又因为M ≥ N + 1，所以M – 1 ≥ N，有
g = gcd(aM – 1 + b, bM – 1 + a)
所以，ab + 1|g
结合g|ab – b，得到
ab + 1|ab – b
因为1 < b，ab + 1 > ab – b
所以，只可能ab – b = 0。即，a = 1。
这与1 < a相矛盾。
因此，本题除了(1, 1)之外，不存在其他解。
总结：本题的关键在于找到ab + 1并证明出ab + 1|g，从而将引出ab + 1|ab – b的矛盾。
往期精彩文章：
数学科普：
数学竞赛：
数学教育：
数学文化：
敬请关注“唯思客俱乐部”，分享、点赞、在看我们的文章：
