FC2ブログ

Welcome to my blog

[答1417] 互いに素な約数の組

ヤドカリ

ヤドカリ

P7080657.jpg



[答1417] 互いに素な約数の組


 (1) 13230000の正の約数の個数は?

 (2) 13230000の正の約数のうち互いに素な異なる2個の選び方(組合せ)は何通り?

 (3) Nの正の約数のうち互いに素な異なる2個の選び方が (2)と同数である最小の自然数Nは?


[解答]

 (1) 13230000=24・54・33・72 ですので、5・5・4・3=300 個です。

 (2) 文字はすべて自然数とします。

  a,b (a<b) を互いに素なnの約数とし、c=an/b ,d=bn/a とおけば、cd=n2 だから、

  互いに素なnの約数の組(a,b)から 積が n2 の自然数の組(c,d)が得られます。

  逆に、cd=n2 (c<d) の自然数の組(c,d)について、その最大公約数を g とすれば、

  (c/g)(d/g)=n2/g2=(n/g)2 は平方数で、c/g,d/g は互いに素だからどちらも平方数、

  a=√(c/g) ,b=√(d/g) とおけば、 ab=n/g なので、a,b は互いに素なnの約数になり、

  積が n2 の自然数の組(c,d)から 互いに素なnの約数の組(a,b)が得られます。

  従って、互いに素なnの約数の組(a,b)と積が n2 の自然数の組(c,d)が 1対1に対応します。

  cd=132300002=28・58・36・74 を満たす(c,d)は 9・9・7・5=2835 個あり、

  組合せだから、c<d とすれば、(2835-1)/2=1417 通りあります。

 (3) 文字はすべて負でない整数とします。

  N2 の正の約数が 2835=9・9・7・5=7・5・3・3・3・3 個あればよい。

  (2a+1)(2b+1)(2c+1)(2d+1)(2e+1)(2f+1)=2835 ,a≧b≧c≧d≧e≧f≧0 の条件で、

  N=2a・3b・5c・7d・11e・13f の最小値は 23・32・5・7・11・13=360360 です。

  23・32・5・7・11・13 が最小である理由は、片っ端から調べれば、

   2a+1,2b+1,2c+1,2d+1,2e+1,2f+1 は、

   2835 の約数 1,3,5,7,9,15,21,27,35,45,…… であり、

   a,b,c,d,e,f は 0,1,2,3,4,7,10,13,17,22,…… です。

   222/(23・32・5・7・11・13)=216/45045>1 、

   217・3/(23・32・5・7・11・13)=214/15015>1 、

   213・32・5/(23・32・5・7・11・13)=210/1001>1 、

   210・37・54/(23・32・5・7・11・13)=27・35・53/1001>1 、

   210・37・5・7/(23・32・5・7・11・13)=27・35/143>1 、

   210・34・52・7/(23・32・5・7・11・13)=27・32・5/143>1 、

   210・32・5・7・11/(23・32・5・7・11・13)=27/13>1 、

   27・34・53・7/(23・32・5・7・11・13)=24・32・52/143>1 、

   27・33・5・7・11/(23・32・5・7・11・13)=24・3/13>1 、

   24・34・53・72/(23・32・5・7・11・13)=2・32・52・7/143>1 、

   24・33・52・7・11/(23・32・5・7・11・13)=2・3・5/13>1 だからです。

.
スポンサーサイト



Comments 0

There are no comments yet.