【2023大阪公立大学・理系・第４問】
\(p\) は素数とする．次の問いに答えよ．
問1 \(j\) を \(0<j<p\) である整数とすると，二項係数 \(_{p}C_{j}\) は \(p\) で割り切れることを示せ．
問2 自然数 \(m\) に対して \((m+1)^p-m^p-1\) は \(p\) で割り切れることを示せ．
問3 自然数 \(m\) に対して \(m^p-m\) は \(p\) で割り切れることを示せ．さらに \(m\) が \(p\) で割り切れないときには，\(m^{p-1}\) が \(p\) で割り切れることを示せ．
ここで，次の集合 \(S\) を考える．
\(S=\left\{4n^2+4n-1 | n は自然数\right\}\)
例えば，\(n=22\) とすると \(4n^2+4n+-1=2023\) なので \(2023\) は \(S\) に属する．
次の問いに答えよ．
問4 整数 \(a\) が \(S\) に属し，\(a=4n^2+4n-1\) ( \(n\) は自然数 ) と表されているとする．このとき，\(a\) と \(2n+1\) は互いに素であることを示せ．
問5 \(p\) は \(3\) 以上の素数とする．\(p\) が \(S\) に属するある整数 \(a\) を割り切るならば，\(2^{\frac{p-1}{2}}-1\) は \(p\) で割り切れることを示せ．
解答・解説
問1 二項係数 \(_{p}C_{j}\) は \(p\) で割り切れることを示せ．
\(_{p}C_{j}=\displaystyle\frac{p!}{j!(p-j)!}\)
\(=\displaystyle\frac{p\cdot(p-1)!}{j\cdot(j-1)!(p-j)!}\)
\(=\displaystyle\frac{p}{j}\cdot\displaystyle\frac{(p-1)!}{(j-1)!(p-j)!}\)
\(=\displaystyle\frac{p}{j}\cdot_{p-1}C_{j-1}\)
よって \(j\cdot_{p}C_{j}=p\cdot_{p-1}C_{j-1}\)
\(p\cdot_{p-1}C_{j-1}\) は \(p\) の倍数なので，\(j\cdot_{p}C_{j}\) も \(p\) の倍数となる．
\(0<j<p\) ，\(p\) は素数より，\(p\) と \(j\) は互いに素であるから，\(_{p}C_{j}\) は \(p\) の倍数となる．
問2 \((m+1)^p-m^p-1\) は \(p\) で割り切れることを示せ．
二項定理から
\((m+1)^p=\displaystyle\sum_{j=0}^{p}{_{p}C_{j}m^j}=\displaystyle\sum_{j=1}^{p-1}{_{p}C_{j}m^j}+m^p+1\) より
\((m+1)^p-m^p-1=\displaystyle\sum_{j=1}^{p-1}{_{p}C_{j}m^j}\)
問1 より \(_{p}C_{j}\) ( \(1≦j≦p-1\) ) は \(p\) で割り切れるので，\((m+1)^p-m^p-1\) は \(p\) で割り切れる．
問3 \(m^p-m\) は \(p\) で割り切れることを示せ．さらに \(m\) が \(p\) で割り切れないときには，\(m^{p-1}\) が \(p\) で割り切れることを示せ．
数学的帰納法を用いて証明する．
( ⅰ ) \(m=1\) のとき
\(1^p-1=0\) は \(p\) で割り切れる．
( ⅱ ) \(m=k\) のとき，\(k^p-k\) が \(p\) で割り切れると仮定する．
\((k+1)^p-(k+1)=\left\{(k+1)^p-k^p-1\right\}+(k^p-k)\)
問2 より \((k+1)^p-k^p-1\) は \(p\) で割り切れ，また \(k^p-k\) は仮定から \(p\) で割り切れるので，\((k+1)^p-(k+1)\) は \(p\) で割り切れる．
( ⅰ )，( ⅱ )より，自然数 \(m\) に対して \(m^p-m\) は \(p\) で割り切れる．
また，\(m^p-m=m(m^{p-1}-1)\) であり，
\(m\) が \(p\) で割り切れないとき， 左辺は \(p\) で割り切れるので，
\(m^{p-1}\) は \(p\) で割り切れる．
フェルマーの小定理
\(p\) が素数で、\(a\) が \(p\) の倍数でない正の整数のとき
\(a^{p-1} ≡ 1\) \(( mod p )\)
問3 の結果を，「フェルマーの小定理」といいます。
他の有名解法として「フェルマーの小定理の証明｜高校数学 整数問題（素数）」をご覧ください！
問4 \(a\) と \(2n+1\) は互いに素であることを示せ．
\(a\) と \(2n+1\) の最大公約数を \(g\) とし，
\(a=gx\) ，\(2n+1=gy\) ( \(x\)，\(y\) は互いに素 ) とおく．
\(a=4n^2+4n+1=(2n+1)^2-2\) より
\(gx=(gy)^2-2\) \(\iff\) \(2=g(gy^2-x)\)
よって \(g=1\) または \(2\) となるが，
\(2n+1=gy\) より，\(g\) は奇数であるから，\(g=1\)
すなわち，\(a\) と \(2n+1\) の最大公約数が \(1\) となるので，
\(a\) と \(2n+1\) は互いに素である．
問5 \(p\) が \(S\) に属するある整数 \(a\) を割り切るならば，\(2^{\frac{p-1}{2}}-1\) は \(p\) で割り切れることを示せ．
以下， \(mod p\) として考える．
条件より \(a=4n^2+4n-1≡0\) ・・・①
問4 から \(a\) と \(2n+1\) は互いに素なので， \(2n+1\) は \(p\) で割り切れない．
よって問3 より，
\((2n+1)^{p-1}-1≡0\)
\(\left\{(2n+1)^2\right\}^{\frac{p-1}{2}}-1≡0\)
\(\left\{(4n^2+4n-1)+2\right\}^{\frac{p-1}{2}}-1≡0\)
①より
\(2^{\frac{p-1}{2}}-1≡0\)
したがって，\(2^{\frac{p-1}{2}}-1\) は \(p\) で割り切れる．
コメント