インテジャーズ

INTEGERS

数、特に整数に関する記事。

105:この数の持つ或る性質

30は「1 \leq k \leq nなる整数kであって、nと互いに素なものが1を除いて全て素数である」という性質をもつ整数nのうち、最大の数でした:30:この数の持つ或る性質 - INTEGERS

少し緩めて「1 \leq k \leq nなる奇数kであって、nと互いに素なものが1を除いて全て素数である」という整数nに関する条件を考えると、最大の数は105となります。

105以下の105と互いに素な正整数は\varphi(105) = 48個あって、

\begin{align}&1, 2, 4, 8, 11, 13, 16, 17, 19, 22, 23, 26, 29, 31, 32, 34, 37, 38, 41, 43, 44, 46, 47, 52, 53, \\ &58, 59, 61, 62, 64, 67, 68, 71, 73, 74, 78, 79, 82, 83, 86, 88, 89, 92, 94, 97, 101, 103, 104\end{align}

1以外の奇数は確かに素数です。105の他に5以上の奇数で同じ性質を満たすものとして、5, 7, 9, 15, 21, 45があります。

補題 k \geq 5ならば p_{k+1}^2 < p_2\cdots p_kが成り立つ。ここで、p_ii番目の素数を表す。

証明. kに関する数学的帰納法で証明する。k=5のときは、

13^2 = 169 < 1155 = 3\cdot 5\cdot 7 \cdot 11

より確認できる。p_k^2 < p_2\cdots p_{k-1}が成り立つと仮定する。Bertrandの仮説より、p_{k+1} < 2p_kが成り立つため、

p_{k+1}^2 < 4p_k^2 < 4p_2\cdots p_{k-1} < p_2\cdots p_k

を得る。 Q.E.D.

105が最大であることの証明

n \geq 3として、nを割り切らない最小の素数をp^{(n)}とすると、n \geq 31は必ず(p^{(n)})^2をtotativeにもつことを30に関する記事で既に証明した。従って、p^{(n)}=2の場合を考えれば十分であり、それはすなわちnが奇数のときである。以下、nを奇数とし、nを割り切らない最小の奇素数をq^{(n)}とする。

107 \leq n \leq 121のとき:
このとき、q^{(n)} =3 or 5となっていることが確認できる。すると、(q^{(n)})^2 \leq 25 < nであるから、(q^{(n)})^2(奇数の合成数)がnのtotativeとなる。

n \geq 123かつq^{(n)}\leq 11のとき:
このとき、:(q^{(n)})^2 \leq 121 < nとなって、(q^{(n)})^2(奇数の合成数)がnのtotativeとなる。

n \geq 123かつp^{(n)} >11のとき]:
q^{(n)}=p_{k+1}なる番号kk \geq 5を満たす。よって、補題より、

(q^{(n)})^2=p_{k+1}^2 < p_2\cdots p_k \leq n

なので(最後の不等号は、q^{(n)}の定義によって、np_2, \dots, p_kの全てを素因子にもつことから分かる)、(q^{(n)})^2(奇数の合成数)はnのtotativeとなる。 Q.E.D.