一些有趣的主题 - 算术半群

我们来看如下的一道 IMO 预选题:

(1991 IMO32 Shortlist P20) 设 是方程 的正根. 对于任何自然数 定义 . 求证: 对所有自然数 有

$$(p*q)*r=p*(q*r).$$

直接暴算确实可以证明:

Proof. 记 , 则 且 .
对任何自然数 , 由于

又

所以

从而

$$于是 $$(p*q)*r=p*(q*r).$$

□

这个方法实在是太丑陋, 太没有启发性了. 题目让证明正整数关于这个运算构成一个半群, 这个半群的结构一定能从别的地方导出. 我们同样也能猜测, 并不是本质的.

事实上, 就在前一年, A.S. Frankel, H. Porta 和 K.B. Stolarsky 写了一篇关于一类算术半群的文章¹, 恰好能解决这个问题. 原文章中只显式给出了 的结论, 我们也只会这样做, 相信大家容易把它推广到一般的 .

Another proof. 如果我们对任意整数 定义

再考虑

那么 是单射. 如果展开

再利用 , 便能得到

由于 永远是整数, 显然有

但由于 的值域在 内, 所以总有 , 所以实际上最左边的小数部分可以去掉. 去掉后我们立即得到

也就是说, 如果定义运算 , 那么 . 由于 是单射, 我们可以认为它把 上的实数乘法运算拉回为了 上的 运算, 从而 自然是结合的.

□

显然这个做法是可以推广的: 对任意非负整数 , 我们都可以定义 , 并将 上的乘法拉回为 上的 . 根据定义, 这需要满足

而熟知 Fibonacci 数列 满足性质 , 以及 , 所以 实际上可以看做 , 从而

类似的还有非常多的关系, 感兴趣的可以去看 Frankel, Porta, Stolarsky 的原文章.

¹. A. S. Fraenkel, H. Porta, and K. B. Stolarsky. Some arithmetical semigroups. In Bruce C. Berndt, Harold G. Diamond, Heini Halberstam, and Adolf Hildebrand, editors, Analytic Number Theory: Proceedings of a Conference in Honor of Paul T. Bateman, pages 255-264. Birkhäuser Boston, Boston, MA, 1990. https://doi.org/10.1007/978-1-4612-3464-7_16. 这里附上全书 pdf. ↩