剛剛做考古題

看到一題很可愛的題目,
敘述可以寫得很嚇人, 但是做法意外的 elementary!
我決定以後開代導的時候要拿這個當 cyclic group 的例子 xD

看 $f(x) = x^2 - 2$ , 我們有

$\begin{array}{|c|ccccccc|}\hline x&1&2&3&4&5&6&\cdots\\ \hline f(x)&-1&2&7&14&23&34&\cdots\\ \hline \end{array}$
令 $S_k = \{ p \text{ prime }: p|f(i) \text{ for some } i\leq k \}$, 有

$\begin{array}{|c|ccccccc|}\hline x&1&2&3&4&5&6&\cdots\\ \hline S_x&&2&2&2&2&2&\cdots\\&&&7&7&7&7&\cdots\\&&&&&23&17&\cdots\\&&&&&&23&\cdots\\ \hline \end{array}$

(A) 證明不是所有的質數都會出現在某個 $S_k$ 中

令 $g(x) = (x^2-2)(x^2-3)(x^2-6)$
$T_k = \{ p \text{ prime }: p|g(i) \text{ for some } i\leq k \}$
有
$\begin{array}{|c|ccccccc|} \hline x&1&2&3&4&5&6&\cdots\\ \hline x^2-2&-1&2&7&14&23&34&\cdots\\ x^2-3&-2&1&6&13&22&33&\cdots\\ x^2-6&-5&-2&3&10&19&30&\cdots\\ \hline T_x&2&2&2&2&2&2&\cdots\\ &5&5&3&3&3&3&\\ &&&5&5&5&5&\\ &&&7&7&7&7&\\ &&&&13&11&11&\\ &&&&&13&13&\\ &&&&&19&17&\\ &&&&&23&19&\\ &&&&&&23&\\ \hline \end{array}$
(B) 證明所有的質數都會出現在某個 $T_k$ 中

(proof)
(A)
    因為 $x^2$ 的末位數字只會是 1, 4, 9, 6, 5, 故 $x^2-2$ 永遠不會是 5 的倍數
(B)
 ※ 對於所有的質數 p,
        p 出現在 $T_k$ 中
    <=> p 整除某個 $g(x)$
    <=> p 整除 $x^2-2, x^-3$ 或 $x^-6$ 其一 for some $x$
    <=> 2, 3 或 6 其一是 $\mathbb{Z}_p$ 中的平方

 ※ 因為 $(\mathbb{Z}_p)* = \mathbb{Z}_{p-1}$ 是 cyclic group, 令 $(\mathbb{Z}_p)* = \langle y\rangle$

       假設 2 和 3 都不是平方, 則 $2 = y^{2i+1}$    , 3 = y^{2j+1}$
                 
    故 $6 = 2*3 = y^{2(i+j+1)}$        是平方

    所以 2, 3 或 6 其一一定是 $(\mathbb{Z}_p)*$ 中的平方