[ 数学 ] 1339 との最大公約数が1であるものは何個あるか | 近畿大学
[サイトマップを見る ]
問題
自然数nに対して，nとの最大公約数が1である自然数の個数をf(n)で表す．たとえば6以下の自然数で，6との最大公約数が1であるものは，1，5の2個であるからf(6)=2である．f(1339)について考える．1339の素因数分解を1339=pq（p, qは素数でp<q）とするとp=[1]，q=[2]となる．したがって，1339以下の自然数でpで割り切れるものの個数は[3]，qで割り切れるものの個数は[4]である．こうした考え方を用いるとf(1339)=[5]であることがわかる．同様にf(10712)=[6]である。
準備
最大公約数が1: 互いに素であることを意味します。
素因数分解: 自然数を素数の積に分解することで、約数の個数や互いに素な数の個数を数えやすくなります。
包除の原理: 複数の条件を満たすものの個数を数える際に、重複を避けるために用いる考え方です。
解答
素因数分解
1339 を素因数分解します。素因数分解というのは素数の積に分解することですね。素因数分解の手順は以下のとおりです。
$${2, 3, 5, 7, 11 \cdots}$$と小さい数から，1339 を割ってみます。
割り切れたら，ひとつ約数を見つけました。
割り切れなかったら，次の素数で割ってみます。
割り切れたら，商について，再び小さい素数から割って行きます。
今回の 1339 の場合，13 で割り切れます。このときの商は 103 で 103 は素数なので，素因数分解はここで終わりです。[1] と [2] にはそれぞれ 13, 103 が入ります。
包除の原理
問題を読み進めます。
1339以下の自然数で13で割り切れるものの個数: 1339 ÷ 13 = 103 個
1339以下の自然数で103で割り切れるものの個数: 1339 ÷ 103 = 13 個
[3] と[4] はそれぞれ 103, 13 です。
包除の原理より、1339以下の自然数で13または103のいずれかで割り切れるものの個数は、103 + 13 個です。しかし、1339 (13×103) は重複して数えられているので、1つ減らして、103 + 13 - 1 = 115 個となります。
よって、1339と互いに素な数（つまり、13でも103でも割り切れない数）の個数は、1339個から115個を引いた数になります。
$$
f(1339) = 1339 - 115 = 1224
$$
[5] は 1224 ですね。
10712の場合
$${10712 = 2^3 × 3^2 × 7^2}$$ と素因数分解できます。
2で割り切れるものの個数: 10712 ÷ 2 = 5356 個
3で割り切れるものの個数: 10712 ÷ 3 = 3570 個
7で割り切れるものの個数: 10712 ÷ 7 = 1530 個
包除の原理を用いて、重複を考慮しながら計算すると、
$$
f(10712) = 10712 - (5356 + 3570 + 1530) + (10712 ÷ (2×3) + 10712 ÷ (2×7) + 10712 ÷ (3×7)) - 10712 ÷ (2×3×7)
$$
これを計算すると、
$$
f(10712) = 2520
$$
となります。[6] は2520ですね。
まとめ
素因数分解を行い、各素因数で割り切れる数の個数を数える。
包除の原理を用いて、重複を考慮しながら、互いに素な数の個数を計算する。
[ サイトマップを見る ]