問題　８８２以下の自然数で８８２と互いに素である自然数の個数を求めよ。
であるので２でも３でも７でも割り切れないということであるから
１周期２×３×７＝４２として考える。

１から４２までで２でも３でも７でも割り切れない数は

１、５、１１、１３、１７、１９、２３、２５、２９、３１、３７、４１の１２個

８８２÷４２＝２１　２１周期分なので

１２×２１＝２５２　

つまり、８８２以下の自然数で８８２と互いに素である自然数の個数は２５２個となります。

ここでオイラー関数を使うと

となり簡単に計算できます。

オイラー関数

について

で定めらる関数をオイラー関数といい

これは、N以下の自然数でNと互いに素である自然数の個数を表すものです。

知っておくと便利ですね。

（大分理系専門塾WINROAD 首藤）

Follow me!