MathLabs

第3题

设 kk 为正整数,SS 为奇素数组成的有限集合。证明将 SS 的元素排列在一个圆周上,使得任意相邻两数之积都具有 x2+x+kx^2+x+k(其中 xx 为某个正整数)的形式,这样的排列方式(不计旋转与反射)至多只有一种。
第 2/6 步:二次同余式模 pp 至多有两个解
T2+T+k≡0(modp)T^2+T+k\equiv0\pmod p
详细分析

若 pp 为奇素数,且对某素数 q<pq<p 与 0≤x<p0\le x<p 有 pq=x2+x+kpq=x^2+x+k 良好,则 xx 满足 T2+T+k≡0(modp)T^2+T+k\equiv0\pmod p;由于该二次同余式在域 Z/pZ\mathbb{Z}/p\mathbb{Z} 上至多有两个解,故至多两个素数 q<pq<p 能使 pqpq 良好。