当サイトは、PRを含む場合があります。
上野竜生です。素因数分解はできると思いますが（一応復習します），それを利用していろいろな問題が解けます。その応用例を（裏技も含めて）紹介していきたいと思います。
素因数分解とは
すべての整数Xは素数の積で書くことができる。つまり
\( X=p_1^{k_1} \times p_2^{k_2} \times \cdots \times p_n^{k_n} \)
の形で書くことができる。順番を除いて一意（1通り)に定まる。
\( X=p_1^{k_1} \times p_2^{k_2} \times \cdots \times p_n^{k_n} \)
の形で書くことができる。順番を除いて一意（1通り)に定まる。
例： 200＝23×52
13=131
2077=31×67など・・・
13=131
2077=31×67など・・・
一般に素因数分解は簡単にはできません。素因数分解の練習問題として出るのは2や3で何度も割り切れるような簡単なものです。
以下では素因数分解を利用した応用例を紹介します。
広告
正の約数の個数
例題：12000の正の約数の個数は何個か？
12000=25×31×53です。よって約数は2a3b5cの形であり，0≦a≦5,0≦b≦1,0≦c≦3であり，aの選び方が0,1,2,3,4,5の6通り。bの選び方が0,1の2通り。cの選び方が0,1,2,3の4通りです。よって6×2×4=48個が答えとなります。答案には次の程度でいいでしょう。
答え12000=25×31×53より
(5+1)×(1+1)×(3+1)=48個
この程度でいいというのは今の説明を一般化した次の公式があるからです。
\( X=p_1^{k_1} \times p_2^{k_2} \times \cdots \times p_n^{k_n} \)と素因数分解したときXの正の約数の個数は(k1+1)(k2+1)・・・(kn+1)個
正の約数の総和
12000の正の約数の総和を求めよ。
これも先に答えを見せます。
答え12000=25×31×53より
(20+21+22+23+24+25)×(30+31)×(50+51+52+53)
=(1+2+4+8+16+32)×(1+3)×(1+5+25+125)
=63×4×156
=39312
ではどうしてこの式で得られるのかと言うと次の公式があるのです。
p,q,r,・・・を素数とする。
paの正の約数の総和はp0＋p1+p2+・・・+pa
paqbrc・・・の正の約数の総和は(paの正の約数の総和)×(qbの正の約数の総和)×(rcの正の約数の総和)×・・・
paの正の約数の総和はp0＋p1+p2+・・・+pa
paqbrc・・・の正の約数の総和は(paの正の約数の総和)×(qbの正の約数の総和)×(rcの正の約数の総和)×・・・
証明は少しだけ複雑になりますが今回の12000の例を見てみましょう。12000の正の約数は2a3b5c(0≦a≦5,0≦b≦1,0≦c≦3)で書けるのでその和は
\( \displaystyle \sum_{a=0}^5 \sum_{b=0}^1 \sum_{c=0}^3 2^a3^b5^c \\
=\displaystyle\sum_{a=0}^5 \sum_{b=0}^1 \left( \sum_{c=0}^3 2^a3^b5^c \right) \\
=\displaystyle\sum_{a=0}^5 \sum_{b=0}^1 2^a3^b \left( \sum_{c=0}^3 5^c \right)\\
=\displaystyle\sum_{a=0}^5 2^a \left( \sum_{b=0}^1 3^b \left(\sum_{c=0}^3 5^c\right)\right)\\
=\displaystyle\sum_{a=0}^5 2^a \left(\sum_{b=0}^1 3^b \right) \left(\sum_{c=0}^3 5^c \right) \\
=\displaystyle\left( \sum_{a=0}^5 2^a \right)\left(\sum_{b=0}^1 3^b \right) \left(\sum_{c=0}^3 5^c \right)\)
=\displaystyle\sum_{a=0}^5 \sum_{b=0}^1 \left( \sum_{c=0}^3 2^a3^b5^c \right) \\
=\displaystyle\sum_{a=0}^5 \sum_{b=0}^1 2^a3^b \left( \sum_{c=0}^3 5^c \right)\\
=\displaystyle\sum_{a=0}^5 2^a \left( \sum_{b=0}^1 3^b \left(\sum_{c=0}^3 5^c\right)\right)\\
=\displaystyle\sum_{a=0}^5 2^a \left(\sum_{b=0}^1 3^b \right) \left(\sum_{c=0}^3 5^c \right) \\
=\displaystyle\left( \sum_{a=0}^5 2^a \right)\left(\sum_{b=0}^1 3^b \right) \left(\sum_{c=0}^3 5^c \right)\)
となります。ですが結構難しい計算ですよね。なので結果（公式）を覚えておきましょう。
広告
互いに素な自然数の数
一般論があります。ですが，証明は大変なのでもし記述式で必要になったらこの定理を使うのではなくベン図などを使って解き，これは検算に使うことをオススメします。
n以下の自然数のうちnと互いに素であるものの数をφ(n)とする。（オイラー関数）
\(\displaystyle \phi(p^a)=p^a\left(1-\frac{1}{p}\right) \\
\phi(p^aq^br^c\cdots)=\phi(p^a)\phi(p^b)\phi(p^c)\cdots \)
\(\displaystyle \phi(p^a)=p^a\left(1-\frac{1}{p}\right) \\
\phi(p^aq^br^c\cdots)=\phi(p^a)\phi(p^b)\phi(p^c)\cdots \)
例題
\(\displaystyle \frac{1}{12000},\frac{2}{12000}\cdots,\frac{11999}{12000} \)の中に既約分数(これ以上約分できない分数)はいくつあるか？
\(\displaystyle \frac{1}{12000},\frac{2}{12000}\cdots,\frac{11999}{12000} \)の中に既約分数(これ以上約分できない分数)はいくつあるか？
記述式では使えないですがオイラー関数を使うと次の通り
12000=253153
12000=253153
φ(25)=25-24=16
φ(31)=31-30=2
φ(53)=53-52=100
よってφ(12000)=φ(25)φ(31)φ(53)=16×2×100=3200個
直感的には次のような解答です。素因数分解すると2,3,5以外の素数では割り切れない。2で割り切れないのは半分ある。3で割り切れないのは全体の3分の2ある。5で割り切れないのは全体の5分の4ある。よって
\( \displaystyle 12000\times \frac{1}{2}\times \frac{2}{3} \times \frac{4}{5}=3200\)
ちゃんとした記述だと次のようになります。
答え1から11999までの整数のうち，2の倍数の集合をA,3の倍数の集合をB,5の倍数の集合をCとし，集合Xに対しn(X)でXの要素の数を表すとする。
n(A)=5999
n(B)=3999
n(C)=2399
n(A∩B)=1999(6の倍数の集合)
n(B∩C)=799(15の倍数の集合)
n(C∩A)=1199(10の倍数の集合)
n(A∩B∩C)=399(30の倍数の集合)
よってn(A∪B∪C)
=n(A)+n(B)+n(C)-n(A∩B)-n(B∩C)-n(C∩A)+n(A∩B∩C)
=5999+3999+2399-1999-799-1199+399
=8799（2か3か5で割れる数）
よって2でも3でも5でも割れないのは11999-8799=3200個
解説を読んで数学がわかった「つもり」になりましたか？数学は読んでいるうちはわかったつもりになりますが演習をこなさないと実力になりません。そのためには問題集で問題を解く練習も必要です。オススメの参考書を厳選しました
<高校数学>上野竜生です。数学のオススメ参考書などをよく聞かれますのでここにまとめておきます。基本的にはたくさん買うよりも…
上野竜生です。大学数学の参考書をまとめてみました。フーリエ解析以外は自分が使ったことある本から選びました。 大…
上野竜生です。当サイトでも少し前まで各ページで学習サイトをオススメしていましたが他にもオススメできるサイトはた…
