場合の数

質問

101から200までの整数のうち、15と互いに素な数の個数をもとめよ。
という問題なのですが、「15と互いに素である」とはどういった意味なのかがいまいちよく分かりません。
どなたか回答お願いします。

回答No.3

sanori · ベストアンサー

＃１さんのおっしゃるとおりですが、
例を挙げたほうが分かりやすいですか？

１５と互いに素であるものを○、そうでないものを×と書きますね。

１０１　○
１０２　×　（３の倍数）
１０３　○
１０４　○
１０５　×　（３の倍数、５の倍数）１５の倍数
１０６　○
１０７　○
１０８　×　（３の倍数）
１０９　○
１１０　×　（５の倍数）
１１１　×　（３の倍数）
１１２　○
１１３　○
１１４　×　（３の倍数）
１１５　×　（５の倍数）
１１６　○
１１７　×　（３の倍数）
１１８　○
１１９　○
１２０　×　（３の倍数、５の倍数）１５の倍数
・・・

ここまで書くと、おそらく気づかれると思いますが、
素なものをカウントするのではなく、
素でないものをカウントするほうが合理的であることに気づかれたと思います。
すなわち、
３の倍数、５の倍数の個数をカウントし、
二重にカウントされるもの（１５の倍数）の個数を引き算すれば、
素でないものの個数。
それを全体の個数（１００個）から引き算すれば、素なものの個数になります。

つまり、
上記の最後の最後の１行だけを除けば、
「１０１から２００までの整数に、３の倍数または５の倍数である数の個数（×印の個数）は何個か？」
という問題と全く同じであるということです。

お礼

例まであげていただき、ありがとうございます。
分かりやすかったです。

回答No.2

Quattro99

2つの整数の最大公約数が1であるとき、その2つの整数を互いに素と呼びます。つまり、公約数が1しかないときということです（負の整数も考える場合は、公約数が1と-1のみ）。

お礼

回答ありがとうございます。

回答No.1

ymmasayan

「互いに素」というのは共通の約数を持たないこと。
つまり３でも５でも(１５でも)割れない数かと。

お礼

なるほど。
回答ありがとうございます。