阪大理系数学2024を解く　大問5

2024年に大阪大学で行われた入試の数学(理系)を思考を交えながら解いていく。

大問5

分野は整数で約数がらみの問題。あるあるパターンの(1)で示した事柄を(2)で使う形となっている。実はオイラー関数というのが題材になっているのだが、僕自身詳しくないのであまり触れないでおく。
ということで早速解いていくのだが、互いに素であるものの個数は数えられないことに気づくだろう。だから、こういう時は余事象を考える時のように互いに素でないものの個数を数えてそれを全体から引けばいいという発想に辿り着きたい。(1)はその発想さえあればあとは作業と化す。
$${p^aq^br^c}$$と互いに素ではない整数というのは$${p,q,r}$$が素数だから、必ず$${p}$$の倍数または$${q}$$の倍数または$${r}$$の倍数となる。そして$${1}$$から$${p^aq^br^c}$$の中で$${p}$$の倍数は$${p^{a-1}q^br^c}$$個、$${q}$$の倍数は$${p^aq^{b-1}r^c}$$個、$${r}$$の倍数は$${p^aq^br^{c-1}}$$個だからこれらの和を$${p^aq^br^c}$$から引き算すれば証明できる……というのは少し詰めが甘い。というのも例えば$${p}$$の倍数かつ$${q}$$の倍数つまり$${pq}$$の倍数はこのままでは2回引かれてしまっているからだ。だから集合を使って正しく考える必要がある。以下では$${1}$$以上$${p^aq^br^c}$$以下の整数の中で、$${x}$$の倍数の集合を$${|X|}$$とする。(例えば$${pq}$$の倍数の集合は$${|PQ|}$$となる。)
すると各集合の個数について、
$${|P|}$$は$${p^{a-1}q^br^c}$$個
$${|Q|}$$は$${p^aq^{b-1}r^c}$$個
$${|R|}$$は$${p^aq^br^{c-1}}$$個
$${|PQ|}$$は$${p^{a-1}q^{b-1}r^c}$$個
$${|QR|}$$は$${p^aq^{b-1}r^{c-1}}$$個
$${|RP|}$$は$${p^{a-1}q^br^{c-1}}$$個
$${|PQR|}$$は$${p^{a-1}q^{b-1}r^{c-1}}$$個
であるから、包除原理を用いれば

となって(1)の証明が完了する。
続いて(2)だが、素因数が3個の場合については(1)を利用できるが、それ以外の場合では使えない。しかし、素因数が4個となる数で最小のものは$${2×3×5×7=210}$$より100を超えるから素因数が4個以上の場合は考えなくてもよいと分かる。また、素因数が1個、2個の場合については(1)と同じ考え方で次のようにして求まる。

そして、その「$${f_{(n)}}$$が$${n}$$の約数となる」というのは「$${\frac{n}{f_{(n)}}}$$が整数になる」と言い換えられる。この発想に至ったらあとは偶奇を調べるだけで求められる。
$${n=p^a}$$のとき
$${\frac{n}{f_{(n)}}=\frac{p^a}{p^{a-1}(p-1)}\\=\frac{p}{p-1}}$$
$${p}$$と$${p-1}$$は互いに素だから$${\frac{p}{p-1}}$$が整数となるとき、$${p-1=1}$$つまり$${p=2}$$のときでありこれは$${p}$$が素数であることを満たしている。よって5以上100以下の整数のうち2の累乗の形で表されるものは全て条件を満たすことがわかる。
$${n=p^aq^b}$$のとき
$${\frac{n}{f_{(n)}}=\frac{p^aq^b}{p^{a-1}q^{b-1}(p-1)(q-1)}\\=\frac{pq}{(p-1)(q-1)}}$$
ここで$${p,q}$$が異なる素数であることから少なくとも一方は奇数となる。ゆえに$${p-1}$$,$${q-1}$$のうち少なくとも一方は偶数になるから、$${\frac{n}{f_{(n)}}}$$が整数になるならば$${p,q}$$のうち一方は偶数、つまり2となる。
$${p=2}$$として代入すると、
$${\frac{pq}{(p-1)(q-1)}=\frac{2q}{q-1}}$$
そして先ほど同様$${q}$$と$${q-1}$$は互いに素だから$${\frac{n}{f_{(n)}}}$$が整数になるとき、$${\frac{2}{q-1}}$$が整数となる。その時、$${q=2,3}$$で$${q}$$は2を除く素数であることから$${q=3}$$は適する。
ゆえに$${n=2^a3^b}$$の形で表される5以上100以下の整数も条件を満たす。
そして$${n=p^aq^br^c}$$のとき、
$${\frac{n}{f_{(n)}}=\frac{p^aq^br^c}{p^{a-1}q^{b-1}r^{c-1}(p-1)(q-1)(r-1)}\\=\frac{pqr}{(p-1)(q-1)(r-1)}}$$
ここで$${p,q,r}$$のうち少なくとも2つは奇数だから、$${pqr}$$は素因数に2を1つ以下しか含まない。一方で$${(p-1),(q-1),(r-1)}$$のうち少なくとも2つは偶数だから、$${(p-1)(q-1)(r-1)}$$は素因数に2を2つ以上含む。故に分子よりも分母の方が素因数2の個数が多いため割り切れることはない。よって整数にはなりえない。
これらより5以上100以下で条件を満たすものは
$${2^a}$$の形のものが、8,16,32,64
$${n=2^a3^b}$$の形のものが、6,12,18,24,36,48,54,72,96となってこれらが答えとなる。

一気に答えに近づいていったが、重要なのは偶奇、とりわけ分母分子が2で割れる回数に注目することである。素数が絡む問題では偶奇が鍵になることが多いからそれをうまく利用したい。
この問題は見かけ自体は難しいものの中身はそこまで大した問題ではないからぜひとも取れるようにしておきたいところだろう。