36 未満の数のうち、36 と因数を共有しないものは十二個

素数にわたる積としてのオイラーの φ 関数、そして包除原理で一行で出す同じ 12。

算術と関数 · 難易度: 古典的な結果 · 更新日 2026-11-10

36 までの整数のうち 36 と共通因数を持たないものの数は 12 です。積の手順は 36 から、各素因数で割り切れる割合を捨てます。(1 − 1/2) を掛けて偶数を除き、(1 − 1/3) を掛けて 3 の倍数を除くと、計算機は 12 と表示します。36 = 2²·3² なので、割るべき素数はこの二つだけです。

2 番目のリンクは同じものを別の方法、包除原理で数えます。2 の倍数が十八個、3 の倍数が十二個、そして二度引かれてしまう 6 の倍数が六個なので一度足し戻します。36 − 18 − 12 + 6 = 12 です。二つの手順は一致しなければならず、一致する理由は「2 または 3 で割り切れる」が「36 と互いに素でない」とまったく同じことだからです。φ は RSA の算術が乗っている数です。オイラーの定理は n と互いに素な任意の a について a^φ(n) ≡ 1 (mod n) と言うので、この数え上げの大きさが周期の大きさになります。

答え

12

読み方

計算機での 36·(1 − 1/2)(1 − 1/3)。2 番目のリンクは包除原理での数え上げ、3 番目はどの素数が関係するかを告げる素因数分解 2²·3² です。

出典

Euler's totient φ(36) = 36(1 − 1/2)(1 − 1/3) = 12, from his 1763 memoir on the function; the product form φ(n) = n·∏(1 − 1/p) over the primes dividing n is the standard result behind RSA key arithmetic

電卓で解いてみる

これらのリンクは、この問題の数値が入力済みの状態で適切な電卓を開きます。上の行は画面に表示されるはずの内容です。ぜひ自分で確認してください。

本サイトは独立した第三者のツールサイトです。Casio、Texas Instruments およびその販売代理店とは、提携・スポンサー・承認のいずれの関係もありません。機種名と製品名は各権利者の商標であり、機種を識別する目的でのみ記載しています。

本マニュアルのキー操作手順は、当サイト独自のレイアウトデータ(オンライン電卓の表示に使うものと同じデータ)と公開されている製品情報に基づいて作成しています。仕様と地域別の設定は、実機およびメーカーの最新資料で確認しています。