a,\ n$を2以上の自然数とする.
$a^n-1$が素数ならば,\ $a=2$であり,\ $n$は素数であることを示せ. \\
{完全数とメルセンヌ素数
本項では,\ 主に完全数にまつわる定理の証明を取り扱う.
まずは,\ 完全数と密接な関係があるメルセンヌ素数に関する定理を証明する.
$n≧2のとき a^n-1=(a-1)(a^{n-1}+a^{n-2}+･･･+a+1)}$
$a≧2,\ n≧2$より $a^{n-1}+a^{n-2}+･･･+a+1≧2^{2-1}+1=3$
$a^n-1$が素数のとき,\ $a-1=1}$より $a=2}$
$対偶「\,nが素数でないならば,\ 2^n-1も素数でない}」を証明する.$
$n≧2よりnは合成数であるから,\ n=pq\ (p,\ q:2以上の自然数)}とおける.$
$2^n-1=2^{pq}-1=(2^p)^q-1=(2^p-1)\{(2^p)^{q-1}+(2^p)^{q-2}+･･･+2^p+1\$
\scalebox{.93}[1]{$p≧2,\ q≧2より\ \ 2^p-1≧2^2-1=3,\ \ (2^p)^{q-1}+(2^p)^{q-2}+･･･+2^p+1≧(2^2)^{2-1}+1=5$}
2以上の自然数の積}であるから,\ $2^n-1$は合成数である.
対偶が真なので,\ 元の命題も真である.
つまり,\ $2^n-1が素数ならば,\ nは素数である.}$
次の因数分解公式は常識としておいてほしい.\ 整数分野では特によく利用する.
2以上の自然数nに対して x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+･･･+xy^{n-2}+y^{n-1})}
\rei\ \ x^2-y^2=(x-y)(x+y) x^3-y^3=(x-y)(x^2+xy+y^2)
\ \ x^4-y^4=(x-y)(x^3+x^2y+xy^2+xy^3)
a^n-1=a^n-1^n\,を公式を用いて因数分解し,\ 右の因数の範囲を調べると3以上である.
よって,\ a^n-1が素数になるためには,\ 左の因数a-1が1であることが必要条件}である.
nが素数であることは,\ 背理法}または対偶法}を用いて証明できる.
すべての自然数は,\ 1,\ 素数,\ 合成数の3つのいずれかに分類される.
素数でないということは1または合成数ということになるが,\ n≧2より,\ nは合成数である.
結局,\ nが合成数のとき,\ 2^n-1が1または合成数となる}ことを証明することになる.
合成数を2以上の自然数の積で表される整数}ととらえて文字で設定する.
2^{pq}=(2^p)^q\,として公式を用いて因数分解し,\ 各因数の範囲を調べればよい.
2^n-1の形で表される自然数をメルセンヌ数},\ これが素数であるときメルセンヌ素数}という.
本定理は,\ メルセンヌ素数2^n-1のnが必ず素数である}ことを主張する.
逆「\,nは素数ならば,\ 2^n-1は素数である」は成り立たない}ので注意してほしい.
実際,\ n=11のとき2^{11}-1=2047=23･89 という反例がある.
{正の約数の総和が自身の2倍になるような自然数を完全数という. \\
$n$を自然数とする.\ \ $2^n-1$が素数ならば,\ $2^{n-1}(2^n-1)$が完全数であることを示せ. \\
25zw}(紀元前3世紀\,;ユークリッド) \\
\\[-.8zh]
$2^n-1$が素数}のとき,\ $2^{n-1}(2^n-1)}$の正の約数の総和は
$(1+2+2^2+2^3+･･･+2^{n-1})(1+2^n-1})=2^n-1}{2-1}･2^n=(2^n-1)2^n=2･2^{n-1}(2^n-1)}$
よって,\ $2^n-1が素数ならば,\ 2^{n-1}(2^n-1)は完全数である.}$ \\
$\left[l}
実は,\ 完全数の定義は,\ 自身を除く正の約数の和に等しくなる自然数}とされていることの方が多い.
しかし,\ 以下の公式の利用を考えると,\ 正の約数の総和が自身の2倍ととらえておく方がよい.
自然数NがN=p^kq^lr^m\,と素因数分解されるとする.
正の約数の総和 (1+p+p^2+･･･+p^k)(1+q+q^2+･･･+q^l)(1+r+r^2+･･･+r^m)}
つまり,\ 各素因数ごとのすべての約数の和を掛けると総和が求まる. \rei\ \ p^k\,の約数は1,\ p,\ ･･･,\ p^k
正の約数の総和を計算し,\ 元の数の2倍になることを示す}ことで,\ 完全数であることを証明できる.
2^n-1=p\ (p:素数)とおくと,\ 2^{n-1}p^1\,の正の約数の総和は(1+2+･･･+2^{n-1})(1+p)となる.
初項a,\ 公比rの等比数列の和の公式(数 B)\ S_n=a(r^n-1)}{r-1}\,の適用で,\ 元の数の2倍になる.
本定理は,\ メルセンヌ素数を見つけると,\ 直ちに対応する\dot{偶}\dot{数}の完全数が見つかる}ことを意味する.
また,\ 2^n-1が素数ではないとき,\ 2^{n-1}(2^n-1)は完全数ではない.}\ 以下略証.
2^n-1が素数でないならば,\ その正の約数は1と2^n-1以外にも存在する.
このとき,\ 2^{n-1}(2^n-1)の正の約数の和は,\ 2･2^{n-1}(2^n-1)よりも大きくなる.
前問より「\,nが素数」が「\,2^n-1が素数」の必要条件なので,\,以下のように完全数を探索できる.
n=2のとき & 2^2-1=3\ (素数)より & 2^{1}(2^2-1)=2･3=6\ (完全数)
n=3のとき & 2^3-1=7\ (素数)より & 2^{2}(2^3-1)=4･7=28\ (完全数)
n=5のとき & 2^5-1=31\ (素数)より & 2^{4}(2^5-1)=16･31=496\ (完全数)
n=7のとき & 2^7-1=127\ (素数)より & 2^{6}(2^7-1)=64･127=8128\ (完全数)
n=11のとき & 2^{11}-1=23･89\ (非素数) & 2^{10}(2^{11}-1)は完全数ではない
n=13のとき & 2^{13}-1=8191\ (素数)より & 2^{12}(2^{13}-1)=4093･8191=33550336\ (完全数)
紀元前の古代ギリシャでは,\ 4個の完全数6,\ 28,\ 496,\ 8128が知られていた.
その後の2000年間,\ 新たに発見された完全数はわずか3個にとどまった.
nの値が大きくなるにつれて2^n-1の値は爆発的に大きくなり,\ 素数判定が困難になるのである.
20世紀にコンピュータが登場し,\ 2021年現在51個のメルセンヌ素数(完全数)が発見されている.
2021年の時点で「偶数の完全数は無数に存在するか」「奇数の完全数は存在するか」は未解決である.
n$を自然数とする.\ 偶数の完全数が$2^n-1$が素数となる$n$を用いて$2^{n-1}(2^n-1)$の形
で表されることを示せ. \ (18世紀\,;オイラー) \\
自然数$a$の正の約数の総和を$S(a)$とする.
偶数の完全数を$N=2^{n-1}k\ (n:2以上の整数\,;k:奇数)}$とおく.
$2^{n-1}$と$k$は互いに素なので $S(N)=(1+2+2^2+･･･+2^{n-1})S(k)=(2^{n}-1)S(k)$
一方,\ $N$は完全数であるから $S(N)=2N=2^{n}k$
よって $2^{n}k=(2^{n}-1)S(k)}$
$2^n,\ 2^n-1$は互いに素なので,\ $k=(2^n-1)m\ (m:自然数)}\ \ ･･････\,①$とおける.
$2^n(2^n-1)m=(2^n-1)S(k)$より $2^nm=S(k)\ \ ･･････\,②$
一方,\ $仮定すると,\ S(k)≧1+m+(2^n-1)m=2^nm+1となる.$
これは,\ ②と矛盾する.
よって,\ $m=1$であり,\ このとき①,\ ②より $k=2^n-1$,\ \ $S(k)=2^n$}
ゆえに,\ $S(k)=k+1$が成り立つから,\ $k$は素数}である.
\scalebox{0.95}[1]{∴\ \ 偶数の完全数Nは,\ 2^n-1が素数となるnを用いて2^{n-1}(2^n-1)の形で表される.}$
逆に,\ \dot{す}\dot{べ}\dot{て}の偶数の完全数が2^{n-1}(2^n-1)\ (2^n-1:素数)の形で表される}ことの証明である.
難易度が高く,\ 大学入試での出題も非常に少ないので超上級者向けである.
まず,\ 偶数の完全数を2の累乗数2^{n-1}\,と奇数kに分割して設定する.
後は,\ このkが2^n-1と表せ,\ かつ素数である}ことを示せばよい.
Nは完全数であるから,\ 2^{n-1}kの正の約数の総和が元の数Nの2倍に等しい.
この観点で等式を作成し,\ kについての条件を追求する.
連続する2整数は互いに素}であることから,\ kが2^n-1の倍数であることがわかる.
kが2^n-1と表せることを示すにはm=1を示せばよく,\ 背理法}を利用する.
m>1のとき,\ k=(2^n-1)mは少なくとも3個の約数1,\ m,\ (2^n-1)mをもつ.
よって,\ kの正の約数の総和S(k)≧2^nm+1であり,\ 2^nm=S(k)と矛盾する.
S(k)=k+1は,\ kの正の約数が1とkのみ}であることを意味する.\ つまり,\ kは素数である.
偶数の完全数のすべての正の約数の逆数の和が2となることを示せ.
偶数の完全数は,\ $2^{n-1}(2^n-1)\ (n:自然数\,;2^n-1:素数)}$と表される.
これの正の約数は,\ $1,\ 2,\ ･･･,\ 2^{n-1},\ 2^n-1,\ 2(2^n-1),\ ･･･,\ 2^{n-1}(n-1)$である.
正の逆数の和は $11+12+･･･+1}{2^{n-1+1}{2^n-1}+1}{2(2^n-1)}+･･･+1}{2^{n-1}(2^n-1)}$
$=2^{n-1}(2^n-1)+･･･+2+1{2^{n-1}(2^n-1)}=2･2^{n-1}(2^n-1){2^{n-1}(2^n-1)}=2}$ \\
まずは具体的な完全数で計算してみる.
完全数6のとき\ \, 11+12+13+16=6+3+2+1}{6}=2
完全数28のとき 11+12+14+17+1}{14}+1}{28}=28+14+7+4+2+1}{28}=2
このように,\ 通分により,\ 分母は元の完全数,\ 分子はすべての正の約数の和}となることがわかる.
前問までで証明した定理を利用し,\ これを一般化する.
2^n-1が素数のとき,\ 2^{n-1}(2^n-1)の正の約数は1から2^{n-1}(2^n-1)までの2n個ある.
わかりづらいならば,\ 素数2^n-1=pとおいて考えるとよい.
2^{n-1}pの正の約数は,\ 1,\ 2,\ ･･･,\ 2^{n-1},\ p,\ 2p,\ ･･･,\ 2^{n-1}pの2n個である.
完全数の定義より,\ 正の約数の総和(分子)は,\ 元の数2^{n-1}(2^n-1)の2倍に等しい.}
これを考慮すると,\ 正の約数の逆数の和が2となることはほぼ当たり前に感じられるはずである.
a,\ nを2以上の自然数とする.$
$a^n+1が素数ならば,\ n=2^m\ (m:整数)\ と表せることを示せ.$ \\
{フェルマー素数
対偶「\,$n=2^mと表せないならば,\ a^n+1が素数でない$}」を示す.
$n=2^m$と表せないとき,\ $n=kp\ (k:自然数\,;p:奇素数)}$とおける.
$a^{kp}+1=(a^k)^p+1=(a^k+1)\{(a^k)^{p-1}-(a^k)^{p-2}+･･･+(a^k)^2-a^k+1\$
$a^k+1≧2^1+1=3$
$(a^k)^{p-1}-(a^k)^{p-2}+･･･+(a^k)^2-a^k+1=(a^k)^{p-2}(a^k-1)+･･･+a^k(a^k-1)+1$
よって,\ 2以上の自然数の積}であるから,\ $a^{pk}+1$は合成数}である.
ゆえに,\ 対偶が真であるから,\ 元の命題も真である
「\,2^n-1が素数ならば,\ nは素数である」の証明と同様の方針で証明できる.
nが2の累乗数ではないとき,\ nは奇数の素因数をもつ}はずである.
これを文字で設定し,\ 以下の公式を適用する.
3以上の\dot{奇}\dot{数}\,nに対して x^n+y^n=(x+y)(x^{n-1}-x^{n-2}y+･･･-xy^{n-2}+y^{n-1})}
\rei\ \ x^3+y^3=(x+y)(x^2-xy+y^2) x^5+y^5=(x+y)(x^4-x^3y+x^2y^2-xy^3+y^4)
後は各因数が2以上の整数であることを示せば,\ a^n+1=a^{kp}+1が素数でないことが示される.
右の因数の処理がわかりづらいので,\ 具体例を示しておく.\ \ a^k=xとおき,\ p=5とする.
x=a^k≧2より,\ x^4-x^3+x^2-x+1=x^3(x-1)+x^2(x-1)+1>1である. (\,\because\ x-1>0)
F_m=2^{2^m}+1}\ (m:0以上の整数)をフェルマー数},\ これが素数のときフェルマー素数}という.
F_0=2^1+1=3\ (素数)
F_1=2^2+1=5\ (素数)
F_2=2^4+1=17\ (素数)
F_3=2^8+1=257\ (素数)
F_4=2^{16}+1=65537\ (素数)
F_5=2^{32}+1=4294967297=641×6700417\ (非素数)
フェルマー(17世紀)は,\ すべてのフェルマー数が素数であると予想した.
しかし,\ オイラー(18世紀)によってF_5\,が非素数であることが示された.
2021年現在でも,\ F_5\,以降の素数は発見されていない.
この5個以外にフェルマー素数が存在するかや,\ フェルマー素数が無限に存在するかは未解決である.
