誘導問題の解答

　この記事はある高校の数学部の1年生が解く用の問題を並べています
　ですが、ユーザーのみなさんにも是非解いていただきたいのでこの場所を借りて問題を作成しています
　そこそこの難易度だと思いますので気軽に解いていってください！！

　以前、同校数学部の面々に出す予定の問題の難易度調整のため(あとJJMOあるあるを共有するため)に以下の誘導問題をLINEにて出題した。
　この問題は、正直知識問題のような反面もあるが、JMOに出場するにあたって数学の知識をつけることは全く悪いことでない。特に、難問が解きたい変人諸君はLTEの補題やアポロニウスの円のような知識が息をするように出てくるのが常であることを認めてほしい。
　では、誘導問題を見ていこう。

誘導問題

$x^{4}$の約数の個数を$4$で割った余りを求めよ

　約数の個数を求める問題である。手短に解答を終わらせよう。

解答

　$n$番目の素数を$p_{n}$とする。すなわち$p_{1}=2,p_{2}=3,p_{3}=5,...$ということである。ここで、$x=p_{1}^{k_{1}}\cdot p_{2}^{k_{2}}\cdot p_{3}^{k_{3}}\cdots p_{n}^{k_{n}}$と素因数分解できたとする(もちろん$k_{i}=0$となるような$i$が存在してもいい)。このとき、
　$x^{4}=(p_{1}^{k_{1}}\cdot p_{2}^{k_{2}}\cdot p_{3}^{k_{3}}\cdots p_{n}^{k_{n}})^{4}=p_{1}^{4k_{1}}\cdot p_{2}^{4k_{2}}\cdot p_{3}^{4k_{3}}\cdots p_{n}^{4k_{n}}$
である。
　$x^{4}$の約数は、素因数に$p_{1}$を$0 \sim 4k_{1}$個持ち、$p_{2}$を$0 \sim 4k_{2}$個持ち、同様に任意の$1 \leq i \leq n$に対して$p_{i}$を$0 \sim 4k_{i}$個持つことがわかる。素因数の個数の選び方は、$p_{1}$について$4k_{1}+1$通りあり、$p_{2}$について$4k_{2}+1$通りあり、同様に任意の$1 \leq i \leq n$に対して$p_{i}$について$4k_{i}+1$通りあることがわかる。
　すなわち、$x^{4}$の約数の個数は$(4k_{1}+1)(4k_{2}+1) \cdots (4k_{n}+1)$個であり、これを$4$で割った余りは$1$である。

　この問題を通して、私達は次の定理に気がつく。

約数の個数

$x=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{n}^{k_{n}}$のとき、$x$の約数の個数は$(k_{1}+1)(k_{2}+1)\cdots (k_{n}+1)$個である。
(ただし、$p$はそれぞれ素数である)

$18=2\cdot3^2$の約数の個数は$(1+1)(2+1)=6$個

$2025=3^4\cdot5^2$の約数の個数は$(4+1)(2+1)=15$個

　中学受験やJJMOなどでは必須テクニックであるが、JMOのレベルになるとあまり出てこないイメージがある約数の個数。頭の片隅においておけば極稀にエレガントな解法(個数による背理法)を導くことができるだろう。
　約数の個数だけでなく、ある素数$p$で何回割れるかを考えることはとても多い。そこで出てくるのが簡単な合同式とLTEの補題だ。
　1年生のうちはまだLTEの補題を理解しなくてもいいが、JMOでの入賞を本気で狙うのならば絶対に使えるようにならなくてはならない。補題の概要については各自調べてもらったほうが早いだろう。

　というわけで、これがいつか出題する難しい問題の誘導になっているからしっかり覚えてね！！じゃあ、練習問題です↓

　$72$の約数の個数を求めよ

　$x$の約数の個数は$7$である。$x$はどのような数か

　$x!$の約数の個数が$16$のとき、$x$を求めよ

　解答を一応残しておく。

↓