偏差値30からの早慶圧勝の個別指導塾 HIRO ACADEMIA

  • 資料請求
  • カウンセリング
  • おー電話

偏差値30からの早慶圧勝の個別指導塾 HIRO ACADEMIA

  • 資料請求
  • カウンセリング
  • お電話

【数学】素因数分解の真髄

まず、N=24について考えてみます。

N=24=2^3\cdot3^1で、約数をすべて列挙すると、{1,2,3,4,6,8,12,24}で約数の個数は、8コで約数すべての和は60です。

次に、N=24・3=72について考えてみます。

N=2^3\cdot3^2で、約数をすべて列挙すると、{1,2,3,4,6,8,9,12,18,24,36,72}で約数の個数は、12コで、約数のすべての和は195です。

これら3つから、約数の個数と約数のすべての和について考えてみます。

・N=24のとき、{1,2,3,2^2,2\cdot3,2^3,2^2\cdot3,2^3\cdot3}で、

2^0は、1,3

2^1は2,2\cdot3

2^22^2,2^2\cdot3

2^32^3,2^3\cdot3に含まれていることが分かります。

つまり、2^k(0≦k≦3)は3の約数(1,3)とすべてかけられています。

逆に、3^0は1,2,2^2,2^3

3^1は3,2\cdot3,2^2\cdot3,2^3\cdot3に含まれていますから、3^l(0≦l≦1)は2の約数(1,2,2^2,2^3)とすべてかけられています。

以上から約数の個数はN=2^3\cdot3^1のべき乗部分に注目して、(1+3)(1+1)=4・2=8コと求められます。

和は、(2^0+2^1+2^2+2^3)(3^0+3^1)=15\cdot4=60となります。

・N=72=2^3\cdot3^2のとき、{1,2,3,4,6,8,9,12,18,24,36,72}

つまり、{1,2,3,2^2,2\cdot3,2^3,\underline{3^2},2^2\cdot3,\underline{2\cdot3^2},2^3\cdot3,\underline{2^2\cdot3^2},\underline{2^3\cdot3^2}}

_(傍線部)はN=24に含まれなかった約数です。_(傍線部)も2^0,2^1,2^2,2^3
すべてかけられているので先程と同様に考えると、(1+3)(1+1+1)=(1+3)(1+2)=4・3=12コで、和は(2^0+2^1+2^2+2^3)(3^0+3^1+3^2)=15\cdot13=195です。

■JMO(日本数学オリンピック)の予選の問題ですが、約数の個数という面で楽しんで頂けないでしょうか?

結局、(1+q_1)(1+q_2)\dots(1+q_n)をm=10,q_i=1(1≦i≦m)として、重複を2で割ったのが本問でした。

ここまでくれば、アルゴリズムが見えてきますね。

P_k(1≦k≦m)を素数として、N=P_1^{q_1}\cdot P_2^{q_2}\dots P_m^{q_m}と表されたNの約数の個数は、(1+q_1)(1+q_2)\dots(1+q_m)

約数の総和は、(1+P_1+\dots+P_1^{q_1})(1+P_2+\dots+P_2^{q_2})\dots(1+P_m+\dots+P_m^{q_m})と一般化できます。

さて、小手調べに以下の問題にとりくんでみよう!


▶問1

ある整数の約数をすべて足すと168になり、約数の逆数をすべて足すと、2.8になる整数を求めよ。(有名問題)


解 N=P_1^{q_1}\cdot P_2^{q_2}\dots P_m^{q_m}とする。

S=(1+P_1+\dots +P_1^{q_1})(1+P_2+\dots +P_2^{q_2})\dots (1+P_m+\dots +P_m^{q_m})=168

T=1+\frac{1}{P_1}+\frac{1}{q_1}+\dots +\frac{1}{P_1^{q_1}\cdot P_2^{q_2}\dots P_m^{q_m}}=2.8\rightleftharpoons \frac{P_1^{q_1}\cdot P_2^{q_2}\dots P_m^{q_m}+\dots +1}{P_1^{q_1}\cdot P_2^{q_2}\dots P_m^{q_m}}=2.8 \rightleftharpoons\frac{S}{N}=2.8 \rightleftharpoons N=\frac{168}{2.8}=\frac{1680}{28}=60

∴N=60…(答え)

■多項式と関係が深いです

ただの丸暗記だと、上の式変形は難しいかもしれませんが、この記事を読んだ皆さんなら、簡単に解けたのではないでしょうか?


問2
正の整数の組み(a,b)であって、a<b,ab=29!を満たし、かつaとbが互いに素であるようなものはいくつあるか。(2017JMO 予選2)


解 29以下の素数は、{1,2,3,5,7,11,13,17,23,29}の10コである。

まず、a=bと仮定すると,ab=29!⇄a^2=29!=28!・29で、29の要素は1つしかなく、平方数にならない。よって、a≠bである。

29!=P_1^{q_1}\cdot P_2^{q_2}\cdot P_3^{q_3}\dots P_{10}^{q_{10}}とする。

q_i=x+y(1≦i≦10)、(1≦x≦q_i-1)として、たとえばaがP_i^x、bがP_i^yを因数にもって、aとbが互いに素に矛盾するから、aとbは一方がP_i^{q_i}をもつかどうかしかありえず、これは2通りである。

P_i(1≦i≦10)について同じことがいえるので、2^{10}通りだが、これにはa>bも含まれている。

対称性(aとbをいれかえても変わらない)より、a<bとa>bの個数は同じだから求める個数は\frac{2^{10}}{2}=2^9=512通り…(答)


Published by

早慶専門個別指導塾 HIRO ACADEMIA

早慶専門個別指導塾 HIRO ACADEMIA

数々のできない受験生を圧倒的にできるレベルまで指導してく個別指導塾。早慶専門ではありますが、早慶志望でなくても勉強ができるようになりたい!と切望する受験生であれば指導できます。必要なのは、志望校に絶対に合格したいという熱意のみ。早稲田大学のある高田馬場で直接指導をしつつ、オンラインでの指導で世界中どこからでも指導を受けることができます。