[答877] 互いに素な２数

'


[答877] 互いに素な２数


　162000000 の正の約数 280 個のうち、互いに素な異なる２数の選び方は何通り？


[解答1]

　162000000＝2⁷･3⁴･5⁶ だから、

　互いに素な数の組み合わせは、まず、1 と 1以外の数の 279 通り、

　a，b，c を a≦7，b≦4，c≦6 を満たす自然数として、

　2^a と 3^b の 7･4＝28 通り、2^a と 5^c の 7･6＝42 通り、3^b と 5^c の 4･6＝24 通り、

　2^a と 3^b･5^c ，3^b と 2^a･5^c ，5^c と 2^a･3^b は

　いずれも、7･4･6＝168 通り ですので、

　279＋28＋42＋24＋3･168＝877 通りです。


[解答2]

　一般化して、N の正の約数のうち、互いに素な異なる２数の選び方の総数を求めます。

　p，q が 互いに素な N の約数で p＜q のとき、

　 d＝Np/q とすれば、p/q＜1 なので d＜N 、N/q は自然数なので d も自然数、

　 N²/d＝N²/(Np/q)＝(N/p)q は自然数だから d は N² の約数です。

　逆に、d が N² の約数で d＜N のとき、

　 d/N＝p/q (p/q は既約分数) とすれば、p，q は 互いに素、p＜q 、q は N の約数、

　 N²/d は自然数で (N²/d)/N＝N/d＝q/p だから p は N の約数です。

　よって、N の互いに素な約数の組(p，q) (p＜q) と N² の N より小さい約数 d が

　１対１に対応し、その総数は ((N²の約数の個数)－1)/2 です。

　本問では、N＝162000000＝2⁷･3⁴･5⁶ 、

　N²＝2¹⁴･3⁸･5¹² だから、(15･9･13－1)/2＝877 通りです。

.