第3题

求所有函数

g:\mathbb{Z}_{>0}\to\mathbb{Z}_{>0}

，使得对所有

m,n\in\mathbb{Z}_{>0}

，

\left(g(m)+n\right)\left(g(n)+m\right)

都是完全平方数。

第 3/6 步：证明素数模刚性

上一步下一步

g(a)\equiv g(b)\pmod p\Longrightarrow a\equiv b\pmod p

详细分析

固定素数 $p$ 以及满足 $g(a)\equiv g(b)\pmod p$ 的正整数 $a,b$ 。选取充分大的正整数 $M$ ，使 $v_p(M+g(a))$ 与 $v_p(M+g(b))$ 都为奇数；可以通过模 $p$ 的足够高次幂选取 $M$ 的适当剩余类来做到：若两个常数之差至少被 $p$ 的两个幂次整除（或二者相等），可令两个赋值都为 $1$ ；若它们之差恰被 $p$ 的一个幂次整除，则可令两个赋值为 $1$ 与 $3$ 。由于 $P(M,a)=(g(M)+a)(g(a)+M)$ 是完全平方数， $M+g(a)$ 的奇赋值迫使 $a+g(M)$ 的 p 进赋值也为奇数，从而 $p\mid a+g(M)$ 。对 $b$ 作同样论证得到 $p\mid b+g(M)$ 。因此 $a\equiv b\pmod p$ 。