已知函数 \(f(x,y)\) 定义在正整数集上, 满足 \(\forall x,y \in \mathbb N^*\),

1. \(f(x,x) = x\),
2. \(f(x,y) = f(y,x)\),
3. \((x+y) \cdot f(x,y) = y \cdot f(x, x+y)\).

求证: \(f(x,y) = [x,y]\) (这里, \([x,y]\) 表示 \(x\) 与 \(y\) 的最小公倍数).

Qer: zhangboxin 20180821

探究

这道题出成证明题已经大大降低了难度, 如果出成解答题, 要求 \(f(x,y)\) 的解析式, 就会难很多.

这是一个数论和函数方程的问题, 作为函数方程的问题, 标准的上手思路当然还是代入一些特殊值来寻找规律并验证结论. 这里代值的方法当然主要是针对已知条件 3, 令 \(y = x\) 有
\[
2x \cdot f(x,x) = x \cdot f(x, 2x) \Rightarrow f(x, 2x) = 2 f(x,x) = 2x
\]
又令 \(y = 2x\), 有
\[
3x \cdot f(x, 2x) = 2x \cdot f(x, 3x) \Rightarrow f(x, 3x) = \dfrac32 f(x,2x) = 3x
\]
以此类推, 不难证明
\[
\forall n, x \in \mathbb N^*, f(x, nx) = nx
\]
再结合条件 2 知, 当 \(x\) 和 \(y\) 有倍数关系 (即 \(y=nx\) 或 \(x=ny\)) 的时候, 结论 \(f(x,y) = [x,y]\) 是成立的. 那么, 它们没有倍数关系的时候呢? 这时可以考虑利用条件 3 来对 \(f(x,y)\) 做变形和转换, 设法使得两个数变得有倍数关系.

在条件 3 中用 \(x+y\) 替换 \(y\) 有
\[
(2x+y) \cdot f(x,x+y) = (x+y) \cdot f(x, 2x+y)
\]
两边同时乘以 \(y\), 再结合条件 3 本身, 有
\[
(x+y) \cdot y \cdot f(x, 2x+y) = (2x+y) \cdot y \cdot f(x,x+y) = (2x+y) (x+y) f(x,y)
\]
由于 \(x+y\) 是正整数, 大于零, 因此
\[
(2x+y) \cdot f(x,y) = y \cdot f(x, 2x+y)
\]
类似的, 依次用 \(2x+y, 3x+y, \dots\) 替换 \(y\) 可以得到
\[
\forall n \in \mathbb N^*, (nx + y) \cdot f(x,y) = y \cdot f(x, nx+y)
\]
事实上, 这个式子不仅对于正整数 \(n\) 成立, 在 \(y > x\) 时对于负的整数 \(n\) 也是成立的, 只要确保 \(nx + y > 0\) 这个前提. 这就让人联想到可以借助辗转相除法.

另外, 如果注意到条件 3 形式上的对称性, 将其乘式形式变成除式形式, 并做适当变形, 可以得到一个更容易处理的形式:
\[
\dfrac{f(x,y)}{x \cdot y} = \dfrac{f(x, x+y)}{x \cdot (x+y)}
\]
显然, 需要把 \(\dfrac{f(x,y)}{x \cdot y}\) 视作一个整体, 那么这个等式其实也在提醒我们使用辗转相除法.

解答

构造函数 \(g(x,y) = \dfrac{f(x,y)}{x \cdot y}\), 则

1. \(g(x,x) = \dfrac1x\);
2. \(g(x,y) = g(y,x)\);
3. \(g(x,y) = g(x, x+y)\).

为证明 \(f(x,y) = [x,y]\), 只需证明 \(g(x,y) = \dfrac1{(x,y)}\), 这里 \((x,y)\) 表示 \(x\) 与 \(y\) 的最大公约数.

对于任意 \(x,y \in \mathbb N^*\), 若 \(x = y\), 则结论显然成立. 否则, 不妨设 \(x < y\), 则可作带余除法 \(y = x \cdot q_1 + r_1\) (其中 \(q_1, r_1 \in \mathbb N^*\) 且 \(r_1 < x\)), 于是由等式 3 有
\[
g(x, r_1) = g(x, x+r_1) = g(x, 2x+r_1) = \dots = g(x, q_1 \cdot x + r_1) = g(x, y)
\]
若 \(r_1 | x\), 则
\[
g(r_1, r_1) = g(r_1, 2r_1) = g(r_1, 3r_1) = \dots = g(r_1, x)
\]
因此
\[
g(x,y) = g(x, r_1) = g(r_1, x) = g(r_1, r_1) = \dfrac1{r_1}
\]
而不难证明此时 \(r_1 = (x,y)\), 因而结论成立.

否则 (若 \(r_1 \nmid x\)) 可继续作带余除法 \(x = r_1 \cdot q_2 + r_2\) (其中 \(q_2, r_2 \in \mathbb N^*\) 且 \(r_2 < r_1\)), 于是
\[
g(r_1, r_2) = g(r_1, r_1 + r_2) =
g(r_1, 2r_1 + x_2) = \dots = g(r_1, q_2 \cdot r_1 + r_2) = g(r_1, x)
\]
而 \(g(x,y) = g(x, r_1) = g(r_1, x) = g(r_1, r_2) = g(r_2, r_1)\). 若 \(r_2 | r_1\), 则不难证明这个值是 \(\dfrac1{r_2}\), 且此时 \(r_2 = (x,y)\). 否则 (若 \(r_2 \nmid r_1\)) 继续作带余除法 \(r_1 = r_2 \cdot q_3 + r_3\)...

以此类推, 这样继续下去可以得到一个有限项的恒为正值且单调递减的余数数列 \(r_1 > r_2 > \dots > r_{n-1} > r_n\), 满足 \(r_{k-2} = r_{k-1} \cdot q_k + r_k\) (\(k = 3,4,\dots,n\)), 这个数列在第 \(n\) 项终止当且仅当 \(r_n | r_{n-1}\). 不难证明
\[
g(x, y) = g(x, r_1) = g(r_1, r_2) = g(r_2, r_3) = \dots = g(r_{n-1}, r_n) = \dfrac1{r_n}
\]
且
\[
(x, y) = (x, r_1) = (r_1, r_2) = (r_2, r_3) = \dots = (r_{n-1}, r_n) = r_n
\]
因而结论成立.