素因数分解と約数の個数などの性質

上野竜生です。素因数分解はできると思いますが(一応復習します),それを利用していろいろな問題が解けます。その応用例を(裏技も含めて)紹介していきたいと思います。

素因数分解の応用

スポンサーリンク

素因数分解とは

すべての整数Xは素数の積で書くことができる。つまり
\( 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など・・・
一般に素因数分解は簡単にはできません。素因数分解の練習問題として出るのは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の正の約数の総和)×・・・
証明は少しだけ複雑になりますが今回の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)\)
となります。ですが結構難しい計算ですよね。なので結果(公式)を覚えておきましょう。

 互いに素な自然数の数

一般論があります。ですが,証明は大変なのでもし記述式で必要になったらこの定理を使うのではなくベン図などを使って解き,これは検算に使うことをオススメします。
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 \frac{1}{12000},\frac{2}{12000}\cdots,\frac{11999}{12000} \)の中に既約分数(これ以上約分できない分数)はいくつあるか?
 記述式では使えないですがオイラー関数を使うと次の通り
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個

数学はもちろん他の科目も勉強できる「スタディサプリ」なら人気講師の授業動画で、塾にいかなくてもまるで塾にいったかのような勉強ができます。塾と比較すると格安で、しかも無料おためしもできます。当サイトオススメのサイトです。


スタディサプリについて解説したページはこちら
スポンサーリンク

シェアする

  • このエントリーをはてなブックマークに追加

フォローする