Weekend Mathematics問題/問題41



41.整数の問題

  1. 1715にある正の整数nをかけたところ立方数となりました。 最小のnを求めなさい。

  2. 1より大きい正の整数Nを因数分解したところ、6乗でも8乗でも12乗でも表されました。
    すなわち、正の整数a,b,cを用いて、N=a=b=c12となりました。
    このような数のうち、最小の正の整数を求めなさい。

  3. ある正の整数Nに224をかけ、363で割ったところ平方数になりました。
    次にこの数Nに484をかけ、567で割ったところ立方数となりました。
    このような数のうち最小のNを求めなさい。

  4. 5桁の2つの互いに素な数MとN(M>N)をかけたところ、398,250,000となりました。
    最小のN≠10,000を求めなさい。



問題の出典


日本の数学 何題解けますか?(上)

深川英俊/ダン・ソフコロフスキ−共著

森北出版





答えと解説












答えと解説

問題1


解答 25



解答・その1

(ペンネ−ム:みそG)

まず、1715を素因数分解します。
すると、1715=7・5
よって、これに、5をかければ、 7・5となり、35の立 方となる。
∴答えは25となる。



問題2


解答 16,777,216



解答・その2

(ペンネ−ム:柿本 浩)

※共通解A:
a,bを素数とすると an・bn = (a・b)・(a・b)・(a・b)・…… = (a*b)n が成り立つ。
1より大きく素数でない全ての整数は、素因数分解を行う事により 2つ以上の素数の積として表す事が出来るため 1より大きな全ての整数のn乗は、素数のn乗もしくは 素数のn乗同士の積として表す事が出来る。
例)62 = 22・32
  83 = 23・23・23

共通解Aより、1より大きな整数のn乗を素因数分解すると 因数の個数はnまたはnの倍数となる事が分かる。
これより、問題の数Nを素因数分解した時の因数の数は 6,8,12の公倍数となり、Nは最少でも24個の素因数に分解される事が分かる。
そうなる様な最少の整数は224であり、これは
224 = (24)6 = (23)8 = (22)12となり 問題の条件を満たしているため、 1以上でa6 = b8 = c12を満たす
最少の整数は224 = 16,777,216である事が分かる。



解答・その3

(ペンネ−ム:かつ)

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



解答・その4

(ペンネ−ム:mhayashi)

a=b(4/3)=c2 で最小な整数組は (a,b,c)=(16,8,4) より、
166=88=412=16,777,216



問題3


解答 448,278,138



解答・その5

(ペンネ−ム:マサボー)

224 = 25 x 7, 363 = 3 x 112, 484 = 22 x 112, 567 = 34 x 7 であるから、
最小 N は 2a x3b x 7c x 11d とおける。
よって、
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 37 x 7 x 114 = 448,278,138



解答・その6

(ペンネ−ム:ch3cooh)

条件は、
N x (224/363)= p2, N x (484/567)= q3
ここで、224= 25 x 7, 363= 3 x 112, 484= 22 x 112, 567= 34 x 7 であるので
N x (25 x 7)/(3 x 112)= p2, N x (22 x 112)/(34 x 7)= q3である。
素数 2,3,7,11について、各々満足する数を計算すると・・・
A: N= 21 x 37x 71x 114 = 448,278,138

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



解答・その7

(ペンネ−ム:夜ふかしのつらいおじさん)

N=448,278,138(=2 x 37 x 7 x 114)
(N x 224)/363=(N x 25 x 71)/(31 x 112)=(平方数)・・・(a)
(N x 484)/567=(N x 22 x 112)/(34 x 71)=(立法数)・・・(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= 21 x 37x 71x 114



解答・その8

(ペンネ−ム:浜田 明巳)

条件から,Nは363=3×11,567=3×7の公倍数であるので,
N=3×7×11×n(nは自然数) とすることができる.
また
  (2×7×N)/(3×11)が平方数,
  (2×11×N)/(3×7)が立方数
であるので,Nの最小値は
  N=2×3×7×11
  (a,b,c,dは非負整数,b≧4,c≧1,d≧2)
であると予想できる.

これ以降は,Ubasicのプログラムseisuu3.ubにて求めた.
Ubasicはこのような桁数の大きい数の計算に優れている.
適当に指数の最大値(Max)を定め,シラミつぶしにa,b,c,dの値から, 上記分数がそれぞれ平方数,立方数になる,つまり約分したとき,指数がそれぞれ偶数, 3の倍数になる場合を求める.その中でNを最小にする場合が,求める答である.
このプログラムにより,答は
N=448,278,138=2×3×7×11 になることが分かる.

以下のように手計算でも求めてみた.
条件から,
  (2×7×N)/(3×11)=a ・・・(1)
  (2×11×N)/(3×7)=b・・・(2)
  N=3×7×11×n・・・・・・・(3)
  (a,b,nは自然数)
とすることができる.
 (3)を(1),(2)に代入すると,
  2×3×7×n=a, 2×11×n=b
  ∴n=a/(2×3×7) =b/(2×11)・・・(4)
  ∴11×a=2×3×7×b・・・(5)
 故に
  a=2×3×7×a,b=11×b(a,bは自然数)・・・(6)
とすることができる.
 (5)に代入すると,
  2×3×7×11×a2 =2×3×7×11×b
  ∴11×a=2×3×b・・・(7)
 故に
  a=2×3×a,b=11×b(a,bは自然数)・・・(8)
とすることができる.
 (7)に代入すると,
  2×3×11×a =2×3×11×b
  ∴2×3×a=11×b・・・(9)
 故に
  a=11×a,b=2×3×b(a,bは自然数)・・・(10)
とすることができる.
 (9)に代入すると,
  2×3×11×a =2×3×11×b
  ∴a=2×3×b
 故に
  a=2×3,b=1
とすることができる.
 (10)に代入すると,
  a=2×3×11,b=2×3
 (8)に代入すると,
  a=2×3×11,b=2×3×11
 (6)に代入すると,
  a=2×3×7×11,b=2×3×11
 (4)に代入すると,
  n=2×3×11
 (3)に代入すると,
  N=2×3×7×11




問題4


解答 15,625



解答・その9

(ペンネ−ム:kiyo)

398250000=2×3×5×59
=15625
答え 15625。



解答・その10

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

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

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



解答・その11

(ペンネ−ム:浜田 明巳)

398,250,000=2×3×5×59 であるから,
N=2×3×5×59
  (a=0 or 4,b=0 or 3,c=0 or 6,d=0 or 1, 10,000<N<398,250,0001/2)
となる.この形のNの最小値を求めればよい.
これ以降は,Ubasicのプログラムseisuu4.ubにて求めた.
このプログラムにより,答は,
  N=15625=5 になることが分かる.

   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




正解者

kiyoみそG夜ふかしのつらいおじさん
浜田 明巳木瓜紋(ボケモン)かつ
ch3cooh柿本 浩マサボー
mhayashi





まとめ

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

素因数分解の一意性

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

証明

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

n=2については、OK。

1<k<nなるkについては、題意を満たしていると仮定します。

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


証明終わり。

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

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

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








E-mail 戻る ホ−ムペ−ジ