◆茨城県 こんにちは さんからの解答。
【定理】
pを素数とする。
以下の条件を満たすqが存在する。
どんな整数nについても、np−pはqで割り切れない。
【証明】
【補題１】
pを素数、nをpで割り切れない自然数とする。
np-１≡1 (mod p)である。
証明は「割り切れる？part2」にあります。
【補題２】
a,mを自然数とする。
集合S(a,m)をS(a,m)={kは自然数 | ak≡1 (mod m)}とおく。
Sの最小の要素をeとすると、Sの任意の要素はeで割り切れる。
【補題証明】
eで割り切れないSの要素のhが存在すると仮定する。
h=e*q+r(0＜r＜n)
ar≡ar*ae*q≡ae*q+r≡ah≡1 (mod m)
rはeより小さなSの要素となって、eの仮定に反する。
よって補題2が示された。
補題証明終
さて本題に入る。
自然数Mを
| M= | pp-1 p-1 | =pp-1+pp-2+・・・+p+1・・・※ |
よって、Mの素因子q中には、q-1がp2で割り切れないものが存在する。
もし、そうでなければ、Mの任意の素因数qiが
qi≡1 (mod p2)となると仮定すると、※より
1+p≡M=Π(qi)≡1 (mod p2)
よってp≡0 (mod p2)となって不合理
よって、Mにはq-1がp2で割り切れない素因数q・・・★
が存在することがわかる。
このqが求めるものである事を示す。
十分大きな自然数Kに対して
(n+q*K)p-p≡np-p (mod q)だから、
自然数nに対して、定理を証明すればよいことがわかる。・・・・(A)
ある自然数nに対して、np≡p (mod q)・・・☆
となると仮定する。
qはMの素因数かつpp-1=M(p-1)より、pp≡1 (mod q)
よって、np2≡npp≡pp≡1 (mod q)・・・●
n≡0 (mod q)となると仮定する。
1≡np2≡0 (mod q)となって不合理。
よって、nとqは互いに素
よって、補題１よりnq-1≡1 (mod q)・・・○
●と○よりq-1とp2はS(n,q)の要素である。
補題２より、S(n,q)の最小の要素eはp2の約数である事がわかる。
e=p2となると仮定する。
e=p2は補題２よりq-1の約数となり★に反する。
よってe=1あるいはe=p
e=1のときnp≡1p≡1 (mod q)
e=pのときnp≡1 (mod q)
いずれにしてもnp≡1 (mod q)
よって、☆よりp≡np≡1 (mod q)
※より0≡M=pp-1+pp-2+・・・+1≡1+1+・・・+1≡p (mod q)
よって、p≡0 (mod q)となって不合理である。
ある自然数nに対して、np≡p (mod q)という仮定は誤りであることがわかる。
よって、任意の自然数に対して、定理が正しい事が分かる。
(A)より、任意の整数に対して、定理が正しいことが示された。