给一个正整数 \(n\) 。找到三个不同的正整数 \(a, b, c\) 满足 \(a + b + c = n\) 并且 \(gcd(a, b) = c\) 。
公式归一化简:
\[\begin{cases}
a + b + c = n, \\
gcd(a, b) = c
\end{cases} \Rightarrow
a + b + gcd(a, b) = n
\]
不难想到 \(n - 2, 1, 1\) 是一组解,但不满足三个不同。
可以想到找到 \(a, b\) 互质且 \(a + b = n - 1\ (a, b \geq 2)\) 。这是问题的关键。
- 若 \((n - 1) \equiv 1 (\mod 2)\) ,奇数 \(x\) 显然能拆为 \(2 + (x - 2)\) 且 \(x - 2\) 依然是奇数。于是 \(gcd(n - 3, 2) = 1\) ,答案为 \(n - 3, 2, 1\) 。由 \(n \geq 10\) ,显然 \(n - 3 \geq 8\) 。
- 若 \((n - 1) \equiv 0 (\mod 2)\) ,则让 \(x = \frac{n - 1}{2}\) :
- 定理: \(2\) 的幂次与“奇数”的 \(gcd\) 为 \(1\) 。
- 若 \(x \equiv 0 (\mod 2)\) ,\(gcd(x - 1, x + 1) = 1\) 。答案为 \(x + 1, x - 1, 1\) ,显然 \(x - 1 \geq 4\) 。
- \(gcd(x - 1, x + 1) = gcd(2, x - 1)\) 。
- 若 \(x \equiv 1 (\mod 2)\) ,\(gcd(x - 2, x + 2) = 1\) 。答案为 \(x + 2, x - 2, 1\) ,显然 \(x - 1 \geq 4\) 。
- \(gcd(x - 2, x + 2) = gcd(4, x - 2)\) 。