闲题解答
申强老师提出了以下的问题：
是否存在正整数 \(n\), 满足下列条件: \(p=10^n+9\) 为质数，且能从 \(1\) 到 \(p-1\) 的正整数中选取一半，按照某种顺序排成一行，使得任意两个相邻的数 \(x\) 和 \(y\)，都满足 \(x^2+4xy-y^2\) 和 \(x^2-4xy-y^2\) 中有一个是 \(p\) 的倍数？
首先将条件写成关于 \(x\) 的二次函数，即
\(f(x) = x^2 \pm 4xy - y^2 = kp\) 其中 \(k\) 为整数
使用二次函数求根公式，解得：
\(x \equiv ( \pm 2\pm\sqrt 5) y \pmod{p}\) 假设存在 5 的二次剩余，如果不存在也自然无解了。
即选取的数每一个都是前一个的倍数（模意义下），此时需要需要考虑类似阶的问题。阶是多少就能选几个（像环一样，回到了起点就不能选了）
WLOG，考虑 \((\pm 2\pm\sqrt 5)\) 为 \((2 + \sqrt 5)\), 则现在需要求出 \((2 + \sqrt 5)\) 的阶。也就是
注意到题目要求选 \(\frac{p-1}{2}\) 个数，所以需要证明是否存在 \(p\) 使得 \(\text{ord}_p(2 + \sqrt 5) \geq \frac{p-1}{2}\)。实际上不需要分情况讨论，因为:
\(2 + \sqrt 5 = (\frac{1}{2}(1+\sqrt 5))^3\)
到这一步可以分两种情况讨论，但是下面的做法可以从不等式入手：
\[ \text{ord}_p(2 + \sqrt 5) = \text{ord}_p((\frac{1}{2}(1+\sqrt 5))^3)\geq \frac{p-1}{2} = \frac{\varphi(p)}{2} \]
\[ \text{ord}_p((\frac{1}{2}(1+\sqrt 5))^3) = \frac{\text{ord}_p(\frac{1}{2}(1+\sqrt 5))}{({\text{ord}_p(\frac{1}{2}(1+\sqrt 5)),3 })} \]
注意到当 \(n>1\) 的时候，\(\text{ord}_p(\frac{1}{2}(1+\sqrt 5))\) 永远是 \(3\) 的倍数。因为这个数也是 \(\text{ord}_p(2 + \sqrt 5)\) 的倍数，而 \(\text{ord}_p(2 + \sqrt 5)\) 可以被 \(3\) 整除。（在大于的情况下）
所以答案应该是否定的，不存在。
考虑使用反证法，如果对于 \(n>1\) 的情况命题成立，那么下式成立
\[ \text{ord}_p(2 + \sqrt 5) = \frac{\text{ord}_p(\frac{1}{2}(1+\sqrt 5))}{({\text{ord}_p(\frac{1}{2}(1+\sqrt 5)),3 })} \geq \frac{\varphi(p)}{2} \]
\[ \frac{\text{ord}_p(\frac{1}{2}(1+\sqrt 5))}{({\text{ord}_p(\frac{1}{2}(1+\sqrt 5)),3 })} = \frac{\text{ord}_p(\frac{1}{2}(1+\sqrt 5))}{3} \geq \frac{\varphi(p)}{2} \]
\[ \text{ord}_p(\frac{1}{2}(1+\sqrt 5)) \geq \frac{3\varphi(p)}{2} \]
左边可以放缩到 \(\varphi(p)\) 即
\[ \varphi(p) \geq \frac{3\varphi(p)}{2} \] 故矛盾。所以只需要考虑 \(n=1\) 的情况。经过计算是 \(3\)，那这种情况下就考虑了所有的情况了。