[答877] 互いに素な2数
'
[答877] 互いに素な2数
162000000 の正の約数 280 個のうち、互いに素な異なる2数の選び方は何通り?
[解答1]
162000000=27・34・56 だから、
互いに素な数の組み合わせは、まず、1 と 1以外の数の 279 通り、
a,b,c を a≦7,b≦4,c≦6 を満たす自然数として、
2a と 3b の 7・4=28 通り、2a と 5c の 7・6=42 通り、3b と 5c の 4・6=24 通り、
2a と 3b・5c ,3b と 2a・5c ,5c と 2a・3b は
いずれも、7・4・6=168 通り ですので、
279+28+42+24+3・168=877 通りです。
[解答2]
一般化して、N の正の約数のうち、互いに素な異なる2数の選び方の総数を求めます。
p,q が 互いに素な N の約数で p<q のとき、
d=Np/q とすれば、p/q<1 なので d<N 、N/q は自然数なので d も自然数、
N2/d=N2/(Np/q)=(N/p)q は自然数だから d は N2 の約数です。
逆に、d が N2 の約数で d<N のとき、
d/N=p/q (p/q は既約分数) とすれば、p,q は 互いに素、p<q 、q は N の約数、
N2/d は自然数で (N2/d)/N=N/d=q/p だから p は N の約数です。
よって、N の互いに素な約数の組(p,q) (p<q) と N2 の N より小さい約数 d が
1対1に対応し、その総数は ((N2の約数の個数)-1)/2 です。
本問では、N=162000000=27・34・56 、
N2=214・38・512 だから、(15・9・13-1)/2=877 通りです。
.