インテジャーズ

INTEGERS

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

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

30は「1 \leq k \leq nなる整数kであって、nと互いに素なものが1を除いて全て素数である」という性質をもつ整数nのうち、最大の数です。

実際、30以下で30と互いに素な自然数は1, 7, 11, 13, 17, 19, 23, 29の8つあり(\varphi (30)=8)、1以外の数は全て素数です。他に同じ性質をもつ数は3,4,6,8,12,18,24のみです。

ちなみに、1 \leq k \leq nであってnと互いに素であるような整数kのことを英語では"nのtotative"というそうです。すなわち、Eulerのトーシェント関数\varphi (n)nのtotativesの個数ということになります。

Bonseの不等式

準備としてBonseの不等式(1907年)を証明します。証明の仕方は色々あると思いますが、Bertrandの仮説
integers.hatenablog.com
を用いると簡単に証明できます。p_kk番目の素数を表すものとします。

Bonseの不等式 k \geq 4ならば p_{k+1}^2 < p_1\cdots p_kが成り立つ。

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

11^2 = 121 < 210 = 2\cdot 3\cdot 5\cdot 7

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

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

を得る。 Q.E.D.

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

n \geq 3として、nを割り切らない素数のうち最小の素数をp^{(n)}とする(n \geq 3ならば\varphi (n)\geq 2なので、このようなnは必ず1でないtotativeをもつ。totativeの素因子はまたtotativeとなるので、p^{(n)}の存在が分かる)。

31 \leq n \leq 49のとき
このとき、p^{(n)} \leq 5となっていることが確認できる。すると、(p^{(n)})^2 \leq 25 < nであるから、(p^{(n)})^2(合成数)がnのtotativeとなる。

n \geq 50かつp^{(n)}\leq 7のとき
このとき、:(p^{(n)})^2 < 50 \leq nとなって、(p^{(n)})^2(合成数)がnのtotativeとなる。

n \geq 50かつp^{(n)} > 7のとき
p^{(n)}=p_{k+1}なる番号kk \geq 4を満たす。よって、Bonseの不等式により、

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

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

*1:実際は、31以上の整数は合成数のtotativeを必ずもつということだけでなく、必ず素数の二乗の形のtotativeをもつことを示している。