设 \(p\) 和 \(q\) 是两个质数, 求不能表示为 \(mp + nq\) (其中, \(m,n\) 是自然数) 的最大正整数 (用 \(p\) 和 \(q\) 表示).
解答
结论: 所求的最大正整数值为 \(pq - p - q\).
首先证明 \(pq - p - q\) 无法表示为 \(mp + nq\), 且 \(m,n\) 是自然数.
否则, 若 \(pq - p - q = mp + nq\), 则 \((m+1) p = (p-n-1) q\), 由于 \(p,q\) 都是质数, 必有 \(p | p-n-1\).
若 \(n \ge 0\), 则设 \(p-n-1 = kp\) 时, \(kp < p\), 有 \(k \le 0\), 于是 \(m+1 \le 0\), \(m \le -1\).
否则 \(n \le -1\), 也就是说将 \(pq - p - q\) 表示为 \(mp + nq\) 时, \(m\) 和 \(n\) 中一定有一个是负数.下面证明大于 \(pq - p - q\) 的数都能表示为 \(mp + nq\), 且 \(m,n\) 是自然数.
考虑 \(pq-p-q+r = mp+nq\), 其中 \(r \ge 1\). 有 \((m+1)p = r + (p-n-1) q\).
考虑 \(n=0,1,2,\dots,p-1\) 时, 等号右边的值分别是 \(r + (p-1) q, r + (p-2) q, r + (p-3) q, \dots, r + 0 \cdot q\), 这 \(p\) 个数除以 \(p\) 的余数各不相同 (为什么?), 故其中必有一个是 \(p\) 的倍数, 它即所对应着我们需要的自然数 \(m,n\) 值.
后记
这个问题需要对裴蜀定理有比较深的理解. 裴蜀定理的内容很简洁:
- \((p,q) = 1\) 的充分必要条件是存在正数 \(m,n\) 使得 \(mp+nq = 1\).
充分性用反证法很容易证明. 若 \((p,q) = t > 1\), 则无论 \(m,n\) 取何值, 都必有 \(t \mid mp+nq\), 故不可能有 \(mp+nq=1\).
必要性稍稍难想一点点, 跟上面这道题用到的一个小技巧相同.
