階乗進法を利用した因数分解

今回はテクニカルな問題を解いていきます。かなりレアなタイプの問題だと思います。それでは、よろしくお願いします。

問題

因数分解による解法を二つ紹介します。特に後半の階乗進法を利用した解法はかなり奇抜だと思います。

解説

解法1(通常の因数分解)

\[ \begin{align*} n^{k!}-1 & =\left(n-1\right)\left(n^{k!-1}+n^{k!-2}+\cdots+n^{2}+n+1\right) \end{align*} \] である。ここで\(p\) を \(k\) 未満の素数とすると、\(\left(n^{k!-1}+n^{k!-2}+\cdots+n^{2}+n+1\right)\)は \(S=(n^p+n^{p-1}+\cdots+n^{2}+n^{1}+1),\) \(S'=(n^{p-1}+n^{p-2}+\cdots+n^{2}+n^{1}+1)\) を約数に持つ。 ここで、\(n \equiv 1 \ (mod \ p)\) のとき、\( S \equiv 1 \ (mod \ p)\) であり、\(n \not\equiv 1 \ (mod \ p)\) のとき、\(S' = \frac{n^{p}-1}{n-1} \equiv \frac{n-1}{n-1} =1 \ (mod \ p)\) となる。 これらは明らかに \(1\) ではないので題意は示された。

(約数に持つことは因数分解を考えればわかります。これは項を \(i\) 個ずつまとめる方法での因数分解を考えれば良いです。)

解法2(階乗進法による因数分解)

\[ \begin{align*} n^{k!}-1 & =\left(n-1\right)\left(n^{k!-1}+n^{k!-2}+\cdots+n^{2}+n+1\right) \\ & =(n-1)(n^{1!}+1)(n^{2\cdot 2!}+n^{2!}+1)\cdots(n^{(k-1)(k-1)!}+n^{(k-2)(k-1)!}+\cdots+n^{2(k-1)!}+n^{(k-1)!}+1) \end{align*} \] ただし、最後の変形に関しては階乗進法の一意性を用いた。 \(n^{p!}-1\) の約数 \(S=(n^{p\cdot p!}+n^{(p-1)p!}+\cdots+n^{2\cdot p!}+n^{p!}+1)\) を考える。 このとき、フェルマーの小定理より \(n\) が \(p\) の倍数でないならば \(n^{p!} \equiv 1 (mod \ p)\) であるから、\(S \equiv 1 (mod \ p)\) が従う。 \(n\) が \(p\) の倍数である場合も \(S \equiv 1 (mod \ p)\) である。よって題意は示された。

(階乗進法の利用例の一つです。)