MathLabs

第3题

设整数 n>3n>3。从集合 {1,2,…,n}\{1,2,\ldots,n\} 中选取三个数,每个数使用一次,利用加法、乘法和括号写出所有可能的表达式。(a) 证明:若三个选数都大于 n/2n/2,则所得各值两两不同。(b) 设 pp 是满足 p≤np\le \sqrt{n} 的素数。证明最小选数为 pp 且表达式的值不全相异的选法数,恰好等于 p−1p-1 的正因数个数。
第 6/7 步:参数化 (b) 中取值重复的选法
x=p,(y−p)(z−p)=p(p−1),d=y−p∣(p−1)x=p,\qquad (y-p)(z-p)=p(p-1),\qquad d=y-p\mid(p-1)
详细分析

令 x=px=p。由相等条件得 (y−p)(z−p)=p(p−1)(y-p)(z-p)=p(p-1)。因为 y−p<z−py-p<z-p,有 (y−p)2<p(p−1)(y-p)^2<p(p-1),所以 y−p<py-p<p;由于 pp 为素数,pp 不整除 y−py-p,从而 d=y−pd=y-p 整除 p−1p-1。反过来,p−1p-1 的每个正因数 dd 都给出 x=px=p、y=p+dy=p+d、z=p+p(p−1)dz=p+\frac{p(p-1)}{d}。