Weekend Mathematics／問題／問題41

４１．整数の問題

1. 1715にある正の整数ｎをかけたところ立方数となりました。 最小のｎを求めなさい。
   
   
2. １より大きい正の整数Ｎを因数分解したところ、６乗でも８乗でも１２乗でも表されました。
   すなわち、正の整数a,b,cを用いて、Ｎ＝a^６＝b^８＝c^１２となりました。
   このような数のうち、最小の正の整数を求めなさい。
   
   
3. ある正の整数Ｎに224をかけ、363で割ったところ平方数になりました。
   次にこの数Ｎに484をかけ、567で割ったところ立方数となりました。
   このような数のうち最小のＮを求めなさい。
   
   
4. ５桁の２つの互いに素な数ＭとＮ(Ｍ＞Ｎ)をかけたところ、398,250,000となりました。
   最小のＮ≠10,000を求めなさい。
   
   

問題１

解答 25

解答・その１

（ペンネ−ム：みそＧ）

まず、１７１５を素因数分解します。
すると、１７１５＝７^３・５
よって、これに、５^２をかければ、 ７^３・５^３となり、３５の立 方となる。
∴答えは２５となる。

問題２

解答 16,777,216

解答・その２

（ペンネ−ム：柿本　浩）

※共通解Ａ：
a,bを素数とすると aⁿ･bⁿ = (a･b)･(a･b)･(a･b)･…… = (a*b)ⁿ が成り立つ。
1より大きく素数でない全ての整数は、素因数分解を行う事により ２つ以上の素数の積として表す事が出来るため 1より大きな全ての整数のn乗は、素数のn乗もしくは 素数のn乗同士の積として表す事が出来る。
例）6² = 2²･3²
　　8³ = 2³･2³･2³

共通解Ａより、1より大きな整数のn乗を素因数分解すると 因数の個数はnまたはnの倍数となる事が分かる。
これより、問題の数Ｎを素因数分解した時の因数の数は 6,8,12の公倍数となり、Ｎは最少でも24個の素因数に分解される事が分かる。
そうなる様な最少の整数は2²⁴であり、これは
2²⁴ = (2⁴)⁶ = (2³)⁸ = (2²)¹²となり 問題の条件を満たしているため、 1以上でa⁶ = b⁸ = c¹²を満たす
最少の整数は2²⁴ = 16,777,216である事が分かる。

解答・その３

（ペンネ−ム：かつ）

まず、a,b,cの関係を調べます。 これはcを基準として考えたほうがいいです。
なぜなら今、a,b,cの中で一番小さい数はcだからです。 よってこんなことがいえます。
a⁶=c¹², b⁸=c¹²から、 a=c², b²=c³となります。
また、Nが最小の数になると言うことから、これは2ⁿの形になります。
つまり、a,b,cも「2の累乗」となるわけです。
それでは、さっき見た関係b²=c³から、 最小の数は8²=4³=64、つまりb=8,c=4です。
それではあとはもう一つの関係a=c²で大丈夫か調べます。
これは当然a=16にできます。 と言うことで、
N=16⁶=16,777,216になると思います。

解答・その４

（ペンネ−ム：mhayashi）

a=b^(4/3)=c² で最小な整数組は (a,b,c)=(16,8,4) より、
16⁶=8⁸=4¹²=16,777,216

問題３

解答 448,278,138

解答・その５

（ペンネ−ム：マサボー）

224 = 2⁵ x 7, 363 = 3 x 11², 484 = 2² x 11², 567 = 3⁴ x 7　であるから、
最小 N は 2^a x3^b x 7^c x 11^d とおける。
よって、
N x 224 / 363 = 2^(a+5) x 3^(b-1) x 7^(c+1) x 11^(d-2)
N x 484 / 567 = 2^(a+2) x 3^(b-4) x 7^(c-1) x 11^(d+2)
以上より
a+5 = 2k, a+2 =3k' とおけ、a = 2k-5 = 3k'-2 (≧0)
2k = 3k' + 3 = 3(k'+1)
上記の式を満たす最小のk、k'は3、1であるから、a = 1
同様にして、b>4、c>1、d>2を満たすようなb、c、dを求めると、b = 7、c =1、d = 4
N = 2 x 3⁷ x 7 x 11⁴ = 448,278,138

解答・その６

（ペンネ−ム：ch3cooh）

条件は、
N x (224/363)= p², N x (484/567)= q³
ここで、224= 2⁵ x 7, 363= 3 x 11², 484= 2² x 11², 567= 3⁴ x 7 であるので
N x (2⁵ x 7)/(3 x 11²)= p², N x (2² x 11²)/(3⁴ x 7)= q³である。
素数 2,3,7,11について、各々満足する数を計算すると・・・
A: N= 2¹ x 3⁷x 7¹x 11⁴ = 448,278,138

(立方数が、有理数の立方数でも良いときは 3のべき乗が1で良いのでもっと小さい値になる。)

解答・その７

（ペンネ−ム：夜ふかしのつらいおじさん）

N=448,278,138(=2 x 3⁷ x 7 x 11⁴)
(N x 224)/363=(N x 2⁵ x 7¹)/(3¹ x 11²)=(平方数)・・・(a)
(N x 484)/567=(N x 2² x 11²)/(3⁴ x 7¹)=(立法数)・・・(b)
なので、Nの各因数の指数は、
2について、(a)より 1,3,5,7,・・・、(b)より 1,4, 7,10,・・・、なので、1
3について、(a)より 1,3,5,7,・・・、(b)より 4,7,10,13,・・・、なので、7
7について、(a)より 1,3,5,7,・・・、(b)より 1,4, 7,10,・・・、なので、1
11について、(a)より 2,4,6,8,・・・、 (b)より 1,4, 7,10,・・・、なので、4
だから、N= 2¹ x 3⁷x 7¹x 11⁴

解答・その８

（ペンネ−ム：浜田　明巳）

条件から，Ｎは３６３＝３×１１^２，５６７＝３^４×７の公倍数であるので，
Ｎ＝３^４×７×１１^２×ｎ（ｎは自然数） とすることができる．
また
　　(２^５×７×Ｎ)／(３×１１^２)が平方数，
　　(２^２×１１^２×Ｎ)／(３^４×７)が立方数
であるので，Ｎの最小値は
　　Ｎ＝２^ａ×３^ｂ×７^ｃ×１１^ｄ
　　（ａ，ｂ，ｃ，ｄは非負整数，ｂ≧４，ｃ≧１，ｄ≧２）
であると予想できる．

これ以降は，Ｕｂａｓｉｃのプログラムseisuu3.ubにて求めた．
Ｕｂａｓｉｃはこのような桁数の大きい数の計算に優れている．
適当に指数の最大値（Max）を定め，シラミつぶしにａ，ｂ，ｃ，ｄの値から， 上記分数がそれぞれ平方数，立方数になる，つまり約分したとき，指数がそれぞれ偶数， ３の倍数になる場合を求める．その中でＮを最小にする場合が，求める答である．
このプログラムにより，答は
Ｎ＝４４８,２７８,１３８＝２×３^７×７×１１^４ になることが分かる．

以下のように手計算でも求めてみた．
条件から，
　　(２^５×７×Ｎ)／(３×１１^２)＝ａ^２ ・・・(1)
　　(２^２×１１^２×Ｎ)／(３^４×７)＝ｂ^３・・・(2)
　　Ｎ＝３^４×７×１１^２×ｎ・・・・・・・(3)
　　（ａ，ｂ，ｎは自然数）
とすることができる．
　(3)を(1)，(2)に代入すると，
　　２^５×３^３×７^２×ｎ＝ａ^２， ２^２×１１^４×ｎ＝ｂ^３
　　∴ｎ＝ａ^２／(２^５×３^３×７^２) ＝ｂ^３／(２^２×１１^４)・・・(4)
　　∴１１^４×ａ^２＝２^３×３^３×７^２×ｂ^３・・・(5)
　故に
　　ａ＝２×３×７×ａ_１，ｂ＝１１×ｂ_１（ａ_１，ｂ_１は自然数）・・・(6)
とすることができる．
　(5)に代入すると，
　　２^２×３^２×７^２×１１^４×ａ_１２ ＝２^３×３^３×７^２×１１^３×ｂ_１^３
　　∴１１×ａ_１^２＝２×３×ｂ_１^３・・・(7)
　故に
　　ａ_１＝２×３×ａ_２，ｂ_１＝１１×ｂ_２（ａ_２，ｂ_２は自然数）・・・(8)
とすることができる．
　(7)に代入すると，
　　２^２×３^２×１１×ａ_２^２ ＝２×３×１１^３×ｂ_２^３
　　∴２×３×ａ_２^２＝１１^２×ｂ_２^３・・・(9)
　故に
　　ａ_２＝１１×ａ_３，ｂ_２＝２×３×ｂ_３（ａ_３，ｂ_３は自然数）・・・(10)
とすることができる．
　(9)に代入すると，
　　２×３×１１^２×ａ_３^２ ＝２^３×３^３×１１^２×ｂ_３^３
　　∴ａ_３^２＝２^２×３^２×ｂ_３^３
　故に
　　ａ_３＝２×３，ｂ_３＝１
とすることができる．
　(10)に代入すると，
　　ａ_２＝２×３×１１，ｂ_２＝２×３
　(8)に代入すると，
　　ａ_１＝２^２×３^２×１１，ｂ_１＝２×３×１１
　(6)に代入すると，
　　ａ＝２^３×３^３×７×１１，ｂ＝２×３×１１^２
　(4)に代入すると，
　　ｎ＝２×３^３×１１^２
　(3)に代入すると，
　　Ｎ＝２×３^７×７×１１^４

問題４

解答 15,625

解答・その９

（ペンネ−ム：kiyo）

３９８２５００００＝２^４×３^３×５^６×５９
５^６＝１５６２５
答え １５６２５。

解答・その１０

（ペンネ−ム：木瓜紋(ボケモン; ≠呆け者、≠ポケモン)）

素因数分解すると398,250,000＝2⁴×3³×5⁶×59である。
ＭとＮは互いに素であるから、 上記素因数2、3、5、59の各々は、ＭとＮとの一方にのみ含まれている。
即ち、ＭもＮも、４つの数(2⁴=16、3³=27、5⁶=15625、59)から １〜３個選んで作った積である。
さて、5⁶=15625を因子として含む方の数を考えると、 その数は、他の因子を含んでいるはずが無い。
なぜならば、2⁴=16、3³=27、59のどれをかけても、 ５桁を超えてしまうからである。
よって、他方の数が残りの因子を全て含んでいる。
それは即ち2⁴×3³×59=16×27×59=25488である。
それが5⁶=15625よりも大きいので、そちらがＭであり、 小さい方5⁶=15625＝Ｎである。

(註)
(1)「≠10,000」という条件は不要です。
Ｎ＝10,000ならば、 Ｍ＝39,825のはずだが、両者は互いに素でない(5が共通素因子であることは明らか)。
(2)「最小の」という条件も不要です。
「５桁の２つの互いに素な数ＭとＮ(Ｍ＞Ｎ)であって積が398,250,000になる」のは、 上記解答で明らかなように、Ｍ＝25488とＮ＝15625の組み合わせしかないからです。
「そのようなＭとＮの組を全て求めよ」とした方がよかったのではないでしょうか？

解答・その１１

（ペンネ−ム：浜田　明巳）

３９８,２５０,０００＝２^４×３^３×５^６×５９ であるから，
Ｎ＝２^ａ×３^ｂ×５^ｃ×５９^ｄ
　　（ａ＝０ or ４，ｂ＝０ or ３，ｃ＝０ or ６，ｄ＝０ or １， １０,０００＜Ｎ＜３９８,２５０,０００１／２）
となる．この形のＮの最小値を求めればよい．
これ以降は，Ｕｂａｓｉｃのプログラムseisuu4.ubにて求めた．
このプログラムにより，答は，
　　Ｎ＝１５６２５＝５^６ になることが分かる．

   10   'asave "seisuu3.ub"
   20   dim J(4),Kakeru(4),Mn(4)
   30   Kakeru(1)=2:Kakeru(2)=3:Kakeru(3)=7:Kakeru(4)=11
   40   Max=20:Mn(0)=1000000
   50   for A=0 to Max:J(1)=A
   60    if or{(A+5)@2>0,(A+2)@3>0} then 190
   70    for B=4 to Max:J(2)=B-4
   80     if or{(B-1)@2>0,(B-4)@3>0} then 180
   90     for C=1 to Max:J(3)=C-1
  100      if or{(C+1)@2>0,(C-1)@3>0} then 170
  110      for D=2 to Max:J(4)=D-2
  120       if or{(D-2)@2>0,(D+2)@3>0} then 160
  130       Nn=1:for J1=1 to 4:for J2=1 to J(J1):Nn*=Kakeru(J1):next:next
  150       if Mn(0)>Nn then Mn(0)=Nn:Mn(1)=A:Mn(2)=B:Mn(3)=C:Mn(4)=D
  160      next
  170     next
  180    next
  190   next
  200   N=1:for J1=1 to 4:for J2=1 to Mn(J1):N*=Kakeru(J1):next:next
  220   print "N =";N;" = 2^";Mn(1);" * 3^";Mn(2);" * 7^";Mn(3);" * 11^";Mn(4)
  230   end

   10   'asave "seisuu4.ub"
   20   dim J(4),Kakeru(4)
   30   N_min=int(sqrt(398250000))+1
   40   Kakeru(1)=2:Kakeru(2)=3:Kakeru(3)=5:Kakeru(4)=59
   50   for J1=0 to 4 step 4:J(1)=J1
   60    for J2=0 to 3 step 3:J(2)=J2
   70     for J3=0 to 6 step 6:J(3)=J3
   80      for J4=0 to 1:J(4)=J4
   90       N=1:for J5=1 to 4:for J6=1 to J(J5):N*=Kakeru(J5):next
  100       if and{N>10000,N_min>N} then N_min=N:J1_min=J1:J2_min=J2:J3_min=J3:J4_min=J4
  110   next:next:next:next
  120   print "N =";N_min;" = 2^";J1_min;" * 3^";J2_min;" * 5^";J3_min;" * 59^";J4_min
  130   end

今回の問題を解くにあたって基本になっているのは、以下の定理です。

素因数分解の一意性

「１より大きい整数は必ず素因数分解ができて、しかもそれは順序を別とすれば一意である。」

証明

ｎについての数学的帰納法で示します。

ｎ＝２については、ＯＫ。

１＜ｋ＜ｎなるｋについては、題意を満たしていると仮定します。

ｎについても正しいということを証明します。

• ｎが素数ならＯＫ。
• ｎが合成数の場合。
  ｎが２種類の素因数分解を持っていたとします。
  つまり、ｎ＝ｐ_１・ｐ_２・・・ｐ_ｓ ＝ｑ_１・ｑ_２・・・ｑ_ｔ
  ｐ_１は、積ｑ_１・ｑ_２・・・ｑ_ｔを割るから、 少なくともどれか、ｑ_iを割る。
  ｐ_１もｑ_iも素数であるから、ｐ_１＝ｑ_i
  ｑ_i＝ｑ_１として｛ｑ｝の番号を振り直すと、
  ｐ_１＝ｑ_１、ｐ_２・ｐ_３・・・ｐ_ｓ ＝ｑ_２・ｑ_３・・・ｑ_ｔ
  ｐ_２・ｐ_３・・・ｐ_ｓ ＝ｑ_２・ｑ_３・・・ｑ_ｔ＝ｎ／ｐ_１＜ｎであるから、 帰納法の仮定により、順序を別として同一のものである。
  従って、ｎが合成数の場合においても証明された。

この定理は「The fundamental theorem of arithmetic」とも呼ばれるほど偉大な定理です。

更に１を素数といわない理由がここにあります。
つまり１を素数としてしまうと、この素因数分解の一意性が成り立たなくなってしまうのです。

木瓜紋さんのご指摘の通り、問題４における「≠10,000」という条件、「最小の」という条件 は確かに不要ですね。

E-mail 戻る ホ−ムペ−ジ