MathLabs
ステップ 4/7: N を一覧のどの素数で割っても余りが 1 になる
ざっくり言うと

N 個のビー玉を pip_i 個ずつ袋に詰める場面を想像してみよう。積の部分 p1p2cdotspnp_1 p_2 \\cdots p_n は余りなくちょうど整数個の袋に収まるため、最後の「+ 1」によって袋の外にビー玉が 1 個だけ余ることになる。つまり、N は pip_i で割り切れない。

N=pi⋅(∏j≠ipj)+1  ⟹  pi∤N(∀ i=1,…,n)N = p_i \cdot \left(\prod_{j \neq i} p_j\right) + 1 \implies p_i \nmid N \quad (\forall\, i = 1, \dots, n)
詳しい解説

リスト L={p1,p2,…,pn}L = \{p_1, p_2, \dots, p_n\} から任意の素数 pip_i を一つ選ぶ。積 P=p1p2⋯pnP = p_1 p_2 \cdots p_n において pip_i をくくり出すと、P=pi⋅KP = p_i \cdot K と書ける。ここで K=∏j≠ipjK = \prod_{j \neq i} p_j はリストの残りの素数の積である(n=1n = 1 のときは K=1K = 1)。これを NN の定義に代入すると、N=pi⋅K+1N = p_i \cdot K + 1 となる。

この等式は、NN を pip_i で割ったときの商が整数 KK で余りが 11 であることを表している。もし pip_i が NN を割り切る(pi∣Np_i \mid N)ならば、pip_i は pi⋅Kp_i \cdot K も割り切るので、それらの差である N−pi⋅K=1N - p_i \cdot K = 1 も割り切らなければならない。ユークリッドの第9巻命題20の言葉を借りれば、その素数は「余りである単位 DFDF を測ることになり、不合理である」。なぜならすべての素数は pi≥2p_i \ge 2 であり、≥2\ge 2 のいかなる整数も 11 を割り切ることはできないからである。したがって、すべての pi∈Lp_i \in L について pi∤Np_i \nmid N である。

このステップの用語
整除と余り
ある整数 k に対して a=dcdotka = d \\cdot k(余り0)となるとき、整数 d は整数 a を割り切る(dmidad \\mid a と書く)という。0<r<d0 < r < d に対して a=dcdotk+ra = d \\cdot k + r となるとき、r は残った余りであり、d は a を割り切らない(dnmidad \\nmid a と書く)。
このステップで使う知識