Milindaの書斎

母国語と外国語を行ったり来たりしながら、自分なりに「書くこと」を追求したいと思います。

数学 5


頭を休めるため、いったん中学校の範囲に戻ります。


【問題】
 2つの自然数 a と b の最大公約数が 1 であるとき,a と b を「互いに素である」という.例えば 1 と 10,8 と 9 はそれぞれ互いに素である.
 次の問いに答えなさい.

(1)1 から 35 までの自然数で,35 と互いに素であるものの個数を求めなさい.
(2)p を素数とするとき,1 から p までの自然数で,p と互いに素であるものの個数を求めなさい.
(3)p,q を素数とするとき,1 から pq までの自然数で,pq と互いに素であるものの個数を求めなさい.
(東京・中央大附高 改題)


答えは下に。






【解答】
(1)
35 の素因数は 5 と 7 であるから,5 の倍数と 7 の倍数を除けばよい.
35 までの 5 の倍数は,5,10,15,20,25,30,35 の7つ.
同様に 7 の倍数は,7,14,21,28,35 の5つ.
35 は重複しているので、5 の倍数と 7 の倍数は合わせて 7 + 5 - 1 = 11 個.
よって求める数は 35 - 11 = 24 個.(答)


(1)の別解
5 の倍数と 7 の倍数を数え上げるのではなく、より抽象化した解き方がある.

35 までの 5 の倍数は,
35 ÷ 5 = 7 個ある.
同様にして、35 までの 7 の倍数は,
35 ÷ 7 = 5 個ある.

よって 5 の倍数と 7 の倍数は合わせて
7 + 5 = 12 個と考えられる.
しかし,5 と 7 の両方を素因数として持つ数が重複している.
重複している数は
35 ÷ 5 ÷ 7 = 1 個.
よって 35 と互いに素でない数は
7 + 5 - 1 = 11 個.

求める数は
35 - 11 = 24 個.(答)

※これはより一般化された解き方であり、問題(3)に応用が利く。


(2)
p が素数であるなら,p の素因数は p だけである.よって pの倍数を除けばよい.
1 から p までの自然数で、p の倍数は p のみ.
よって求める数は p - 1 個.(答)


(3)
p,q が素数なのだから,pq の素因数は p と q.よって p の倍数と q の倍数を除けばよい.
pq までの自然数に,p の倍数は
pq ÷ p = q 個ある.
同様にして,q の倍数は
pq ÷ q = p 個ある.
また,p と q の両方を素因数として持つ数は
pq ÷ p ÷ q = 1 個.
よって、pq までの自然数で pq と互いに素でないものは
pq - p - q + 1 個.(答)