実践演習 整数系

オーダー【素因数の個数】【2007年度 横浜国立大学ほか】

例題はこちら(画像をクリックするとPDFファイルで開きます。)

類題はこちら(画像をクリックするとPDFファイルで開きます。)

自然数 \(n\) がもつ素因数 \(p\) の個数を \(a\) としたとき、\(a\) を \(n\) の素因数 \(p\) に関するオーダーと言い、

\(a=\mathrm{ord}_{p}n\)

と表すことがあります。

この記号自体はあまり馴染みがないと思いますし、事実本問においてもこの記号は用いずに \(f(n)\) を定義することで出題しています。

素因数の個数を「数える」

という場合の数の問題の中でスポットが当てられることもありますが、今回は素因数の個数を題材とした整数問題としての側面が強い問題を扱います。

(以下ネタバレ注意)

 

+ クリック(タップ)して続きを読む

例題について

例題はこちら(再掲)(画像をクリックするとPDFファイルで開きます。)

(1) について

非負整数 \(a\) ,  \(c\) ,  正の奇数 \(b\) ,  \(d\) を用いて

  • \(k=2^{a}b\)
  • \(m=2^{c}d\)

と表すことで手なりに話が進んでいきます。

余談ですが、一般に

\(\mathrm{ord}_{p}mn=\mathrm{ord}_{p}m+\mathrm{ord}_{p}n\)

ということが言えます。

指数部分を取り出す記号である \(\mathrm{log}\) に似た性質をもっています。

(2) について

実験してみると

  • \(f(3^{0}+1)=f(1)=1\)
  • \(f(3^{1}+1)=f(4)=2\)
  • \(f(3^{2}+1)=f(10)=1\)
  • \(f(3^{3}+1)=f(28)=2\)

ということで、\(1\) ,  \(2\) の繰り返しであることが予想できますので、帰納法で裏付ければよいでしょう。

(3) について

\(3^{n}-1=(3-1)(3^{n-1}+3^{n-2}+\cdots+3+1)\)

という因数分解を見抜けないと厳しいものがあります。

素因数 \(2\) の個数が 1 個はあることが確定しました。

そうなると、残りの

\(3^{n-1}+3^{n-2}+\cdots+3+1\)

のもつ素因数 \(2\) の個数に興味がいくはずです。

また、順番は多少前後するかもしれませんが、\(f(n)\) を考えるにあたっては

\(p\) を非負整数 ,  \(q\) を正の奇数として

\(n=2^{p}q\)

と表現したくなります。

さて、 \(n\) 個の奇数の和

\(3^{n-1}+3^{n-2}+\cdots+3+1\)

は \(n\) が奇数のときである \(p=0\) のときは

奇数個の奇数の和

ですから、\(3^{n-1}+3^{n-2}+\cdots+3+1\) は奇数ということになります。

あとは、\(p \geq 1\) のときです。

\(f(3^{2^{p}q}-1)\) について考えるわけですが、目がチカチカします。

そこで

\(b_{p}=f(3^{2^{p}q}-1)\)

とおきます。

やはり頭を整理するために、実験しながら要領を掴んでいきます。

例えば

\(b_{1}=f(3^{2q}-1)\)

\(=f((3^{q}+1)(3^{q}-1))\)

(1) より

\(=f(3^{q}+1)+f(3^{q}-1)\)

(2) の結果と、\(p \geq 0\) のときの結果を考えると

\(=2+1\)

\(=3\)

ということになります。

同じ要領で、\(b_{2}\) ,  \(b_{3}\) \(\cdots\) を調べてみると

\(b_{2}=4\) ,  \(b_{3}=5\)

となりますから、

\(b_{p}=p+2\)

という等差数列であることが予想できます。

あとは、\(b_{p+1}\) を計算してみようという気になると思います。

類題について

類題はこちら(再掲)(画像をクリックするとPDFファイルで開きます。)

今度は素因数 \(3\) の個数について考えます。

結局オチは

\(n^{3}-n\) は素因数 \(3\) を \(1\) 個以上もつ

ことを示すという問題です。

紐解いて見ればド定番の内容で、見慣れない記号に怯むことなく定義を読み取るということに慣れていきましょう。

例題の解答はコチラ

類題の解答はコチラ

-実践演習, 整数系
-

© 2022 MathClinic