平成20年10月5日

[流れ星]

     第213回数学的な応募問題解答

      <解答募集期間:9月14日〜10月5日

最小公倍数

皆さん、今年の大分大学医学部の入試問題を改題して出題します。

 

NO1 uchinyan  9/15 1302分受信 更新10/5

第213回数学的な応募問題
[最小公倍数]

一般に,a, b, a < b の最大公約数を g とすると,c, d を互いに素な整数として,
a = gc, b = gd, c < d, A = gcd, A/g = cd, c^2 < A/g < d^2, 1 <= c < sqrt(A/g) < d
になります。つまり,a, b の最大公約数 g は,A の約数で,
c = a/g
1 以上 sqrt(A/g) より小で A/g の約数です。
d
はこの c から d = A/gc = A/a, ただし c, d は互いに素,として求まります。
a, b
は,これら c, d から a = gc, b = gd として求まります。
そして,N(A) は,この a, b の個数から求められますが,結局は,c の個数に等しくなります。
以下,これらのことを踏まえて考えてみます。

問題1 N(6)
A = 6 = 2 * 3, g = 1, 2, 3, 6
g = 1, A/g = 6 = cd, 1 <= c < sqrt(6) < 3, (c,d) = (1,6), (2,3), (a,b) = (1,6), (2,3)
g = 2, A/g = 3 = cd, 1 <= c < sqrt(3) < 2, (c,d) = (1,3), (a,b) = (2,6)
g = 3, A/g = 2 = cd, 1 <= c < sqrt(2) < 2, (c,d) = (1,2), (a,b) = (3,6)
g = 6, A/g = 1 = cd, 1 <= c < sqrt(1) = 1, (c,d) = NG, (a,b) = NG
N(6) = 2 + 1 + 1 + 0 = 4

問題2 N(15)
A = 15 = 3 * 5, g = 1, 3, 5, 15
g = 1, A/g = 15 = cd, 1 <= c < sqrt(15) < 4, (c,d) = (1,15), (3,5), (a,b) = (1,15), (3,5)
g = 3, A/g = 5 = cd, 1 <= c < sqrt(5) < 3, (c,d) = (1,5), (a,b) = (3,15)
g = 5, A/g = 3 = cd, 1 <= c < sqrt(3) < 2, (c,d) = (1,3), (a,b) = (5,15)
g = 15, A/g = 1 = cd, 1 <= c < sqrt(1) = 1, (c,d) = NG, (a,b) = NG
N(15) = 2 + 1 + 1 + 0 = 4

問題3 N(35)
A = 35 = 5 * 7, g = 1, 5, 7, 35
g = 1, A/g = 35 = cd, 1 <= c < sqrt(35) < 6, (c,d) = (1,35), (5,7), (a,b) = (1,35), (5,7)
g = 5, A/g = 7 = cd, 1 <= c < sqrt(7) < 3, (c,d) = (1,7), (a,b) = (5,35)
g = 7, A/g = 5 = cd, 1 <= c < sqrt(5) < 3, (c,d) = (1,5), (a,b) = (7,35)
g = 35, A/g = 1 = cd, 1 <= c < sqrt(1) = 1, (c,d) = NG, (a,b) = NG
N(35) = 2 + 1 + 1 + 0 = 4

問題4 N(105)
A = 105 = 3 * 5 * 7, g = 1, 5, 7, 35, 3, 15, 21, 105
以下は,A/g が問題3 3 倍になっています。
g = 1, A/g = 105 = cd, 1 <= c < sqrt(105) < 11, (c,d) = (1,105), (3,35), (5,21), (7,15),
(a,b) = (1,15), (3,35), (5,21), (7,15)
g = 5, A/g = 21 = cd, 1 <= c < sqrt(21) < 5, (c,d) = (1,21), (3,7), (a,b) = (5,105), (15,35)
g = 7, A/g = 15 = cd, 1 <= c < sqrt(15) < 4, (c,d) = (1,15), (3,5), (a,b) = (7,105), (21,35)
g = 35, A/g = 3 = cd, 1 <= c < sqrt(3) < 2, (c,d) = (1,3), (a,b) = (35,105)
以下は,g 3 の倍数ですが,A/g = cd は,問題3 と同じになります。
g = 3, A/g = 35 = cd, 1 <= c < sqrt(35) < 6, (c,d) = (1,35), (5,7), (a,b) = (3,105), (15,21)
g = 15, A/g = 7 = cd, 1 <= c < sqrt(7) < 3, (c,d) = (1,7), (a,b) = (15,105)
g = 21, A/g = 5 = cd, 1 <= c < sqrt(5) < 3, (c,d) = (1,5), (a,b) = (21,105)
g = 105, A/g = 1 = cd, 1 <= c < sqrt(1) = 1, (c,d) = NG, (a,b) = NG
N(105) = 4 + 2 + 2 + 1 + 4 = 13

問題5 N(210)
A = 210 = 2 * 3 * 5 * 7, g = 1, 3, 5, 7, 15. 21. 35, 105, 2, 6, 10, 14, 30, 42, 70, 210
以下は,A/g が問題4 2 倍になっています。
g = 1, A/g = 210 = cd, 1 <= c < sqrt(210) < 15,
(c,d) = (1,210), (2,105), (3,70), (5,42), (6,35), (7,30), (10,21), (14,15),
(a,b) = (1,210), (2,105), (3,70), (5,42), (6,35), (7,30), (10,21), (14,15)
g = 3, A/g = 70 = cd, 1 <= c < sqrt(70) < 9, (c,d) = (1,70), (2,35), (5,14), (7,10),
(a,b) = (3,210), (6,105), (15,42), (21,30)
g = 5, A/g = 42 = cd, 1 <= c < sqrt(42) < 7, (c,d) = (1,42), (2,21), (3,14), (6,7),
(a,b) = (5,210), (10,105), (15,70), (30,35)
g = 7, A/g = 30 = cd, 1 <= c < sqrt(30) < 6, (c,d) = (1,30), (2,15), (3,10), (5,6),
(a,b) = (7,210), (14,105), (21,70), (35,42)
g = 15, A/g = 14 = cd, 1 <= c < sqrt(14) < 4, (c,d) = (1,14), (2,7), (a,b) = (15,210), (30,105)
g = 21, A/g = 10 = cd, 1 <= c < sqrt(10) < 4, (c,d) = (1,10), (2,5), (a,b) = (21,210), (42,105)
g = 35, A/g = 6 = cd, 1 <= c < sqrt(6) < 3, (c,d) = (1,6), (2,3), (a,b) = (35,210), (70,105)
g = 105, A/g = 2 = cd, 1 <= c < sqrt(2) < 2, (c,d) = (1,2), (a,b) = (105,210)
以下は,g 2 の倍数ですが,A/g = cd は,問題4 と同じになります。
g = 2, A/g = 105 = cd, 1 <= c < sqrt(105) < 11, (c,d) = (1,105), (3,35), (5,21), (7,15),
(a,b) = (2,210), (6,70), (10,42), (14,30)
g = 10, A/g = 21 = cd, 1 <= c < sqrt(21) < 5, (c,d) = (1,21), (3,7), (a,b) = (10,210), (30,70)
g = 14, A/g = 15 = cd, 1 <= c < sqrt(15) < 4, (c,d) = (1,15), (3,5), (a,b) = (14,210), (42,70)
g = 70, A/g = 3 = cd, 1 <= c < sqrt(3) < 2, (c,d) = (1,3), (a,b) = (70,210)
g = 6, A/g = 35 = cd, 1 <= c < sqrt(35) < 6, (c,d) = (1,35), (5,7), (a,b) = (6,210), (30,42)
g = 30, A/g = 7 = cd, 1 <= c < sqrt(7) < 3, (c,d) = (1,7), (a,b) = (30,210)
g = 42, A/g = 5 = cd, 1 <= c < sqrt(5) < 3, (c,d) = (1,5), (a,b) = (42,210)
g = 210, A/g = 1 = cd, 1 <= c < sqrt(1) = 1, (c,d) = NG, (a,b) = NG
N(210) = 8 + 4 + 4 + 4 + 2 + 2 + 2 + 1 + 13 = 40

問題6 N(2310)
A = 2310 = 2 * 3 * 5 * 7 * 11,
g = 1, 3, 5, 7, 15. 21. 35, 105, 2, 6, 10, 14, 30, 42, 70, 210
及びそれらに 11 を掛けたもの
g = 1, 3, 5, 7, 15. 21. 35, 105, 2, 6, 10, 14, 30, 42, 70, 210
の場合は,A/g が問題5 11 倍になっています。
g = 1, A/g = 2310 = cd, 1 <= c < sqrt(2310) < 49,
c
は,A/g = 2310 49 より小さい約数です。それは,16 個です。そこで,
(c,d) = 16
, (a,b) = 16
以下同様にして,
g = 3, A/g = 770 = cd, 1 <= c < sqrt(770) < 28, (c,d) = 8
, (a,b) = 8
g = 5, A/g = 462 = cd, 1 <= c < sqrt(462) < 22, (c,d) = 8
, (a,b) = 8
g = 7, A/g = 330 = cd, 1 <= c < sqrt(330) < 19, (c,d) = 8
, (a,b) = 8
g = 15, A/g = 154 = cd, 1 <= c < sqrt(154) < 13, (c,d) = 4
, (a,b) = 4
g = 21, A/g = 110 = cd, 1 <= c < sqrt(110) < 11, (c,d) = 4
, (a,b) = 4
g = 35, A/g = 66 = cd, 1 <= c < sqrt(66) < 9, (c,d) = 4
, (a,b) = 4
g = 105, A/g = 22 = cd, 1 <= c < sqrt(22) < 5, (c,d) = 2
, (a,b) = 2
g = 2, A/g = 1155 = cd, 1 <= c < sqrt(1155) < 34, (c,d) = 8
, (a,b) = 8
g = 6, A/g = 385 = cd, 1 <= c < sqrt(385) < 20, (c,d) = 4
, (a,b) = 4
g = 10, A/g = 231 = cd, 1 <= c < sqrt(231) < 16, (c,d) = 4
, (a,b) = 4
g = 14, A/g = 165 = cd, 1 <= c < sqrt(165) < 13, (c,d) = 4
, (a,b) = 4
g = 30, A/g = 77 = cd, 1 <= c < sqrt(77) < 9, (c,d) = 2
, (a,b) = 2
g = 42, A/g = 55 = cd, 1 <= c < sqrt(55) < 8, (c,d) = 2
, (a,b) = 2
g = 70, A/g = 33 = cd, 1 <= c < sqrt(33) < 6, (c,d) = 2
, (a,b) = 2
g = 210, A/g = 11 = cd, 1 <= c < sqrt(11) < 4, (c,d) = 1
, (a,b) = 1
これを見ると,個数は,問題5 の場合の 2 + 1 = 40 * 2 + 1 になっています。
残りは,g 11 の倍数ですが,A/g = cd は,問題5 と同じになります。
そこで,(c,d) = 40 , (a,b) = 40
N(2310) = 40 * 2 + 1 + 40 = 121

参考 一般の N(A) について
もう少し例をやってみます。

N(2)
A = 2 = 2, g = 1, 2
g = 1, A/g = 2 = cd, 1 <= c < sqrt(2) < 2, (c,d) = (1,2), (a,b) = (1,2)
g = 2, A/g = 1 = cd, 1 <= c < sqrt(1) = 1, (c,d) = NG, (a,b) = NG
N(2) = 1

N(4)
A = 4 = 2^2, g = 1, 2, 4
g = 1, A/g = 4 = cd, 1 <= c < sqrt(4) = 2, (c,d) = (1,4), (a,b) = (1,4)
g = 2, A/g = 2 = cd, 1 <= c < sqrt(2) < 2, (c,d) = (1,2), (a,b) = (2,4)
g = 4, A/g = 1 = cd, 1 <= c < sqrt(1) = 1, (c,d) = NG, (a,b) = NG
N(4) = 2

N(12)
A = 12 = 2^2 * 3, g = 1, 2, 4, 3, 6, 12
c, d
は互いに素,に注意して,
g = 1, A/g = 12 = cd, 1 <= c < sqrt(12) < 4, (c,d) = (1,12), (3,4), (a,b) = (1,12), (3,4)
g = 2, A/g = 6 = cd, 1 <= c < sqrt(6) < 3, (c,d) = (1,6), (2,3), (a,b) = (2,12), (4,6)
g = 4, A/g = 3 = cd, 1 <= c < sqrt(3) < 2, (c,d) = (1,3), (a,b) = (4,12)
g = 3, A/g = 4 = cd, 1 <= c < sqrt(4) = 2, (c,d) = (1,4), (a,b) = (3,12)
g = 6, A/g = 2 = cd, 1 <= c < sqrt(2) < 2, (c,d) = (1,2), (a,b) = (6,12)
g = 12, A/g = 1 = cd, 1 <= c < sqrt(1) = 1, (c,d) = NG, (a,b) = NG
N(12) = 7

N(36)
A = 36 = 2^2 * 3^2, g = 1, 2, 4, 3, 6, 12, 9, 18, 36
g = 1, A/g = 36 = cd, 1 <= c < sqrt(36) = 6, (c,d) = (1,36), (4,9), (a,b) = (1,36), (4,9)
g = 2, A/g = 18 = cd, 1 <= c < sqrt(18) < 5, (c,d) = (1,18), (2,9), (a,b) = (2,36), (4,18)
g = 4, A/g = 9 = cd, 1 <= c < sqrt(9) = 3, (c,d) = (1,9), (a,b) = (4,36)
g = 3, A/g = 12 = cd, 1 <= c < sqrt(12) = 4, (c,d) = (1,12), (3,4), (a,b) = (3,36), (9,12)
g = 6, A/g = 6 = cd, 1 <= c < sqrt(6) < 3, (c,d) = (1,6), (2,3), (a,b) = (6,36), (12,18)
g = 12, A/g = 3 = cd, 1 <= c < sqrt(3) = 2, (c,d) = (1,3), (a,b) = (12,36)
g = 9, A/g = 4 = cd, 1 <= c < sqrt(4) = 2, (c,d) = (1,4), (a,b) = (9,36)
g = 18, A/g = 2 = cd, 1 <= c < sqrt(2) < 2, (c,d) = (1,2), (a,b) = (18,36)
g = 36, A/g = 1 = cd, 1 <= c < sqrt(1) = 1, (c,d) = NG, (a,b) = NG
N(36) = 12

以上を踏まえて考えてみます。

まず,明らかに
 命題1 A が素数の場合,N(A) = 1
です。これは,問題1 などと同様にして,
A, g = 1, A
g = 1, A/g = A = cd, 1 <= c < sqrt(A) < A, (c,d) = (1,A), (a,b) = (1,A)
g = A, A/g = 1 = cd, 1 <= c < sqrt(1) < 1, (c,d) = NG, (a,b) = NG
N(A) = 1
です。

次に,
 命題2 p は素数で A = p^n の場合,N(A) = n
がいえます。これは,
A = p^n, g = 1, p, p^2, ..., p^n
c, d
は互いに素でないといけないことに注意すると,
g = 1, A/g = p^n = cd, 1 <= c < sqrt(p^n), (c,d) = (1,p^n), (a,b) = (1,p^n)
g = p, A/g = p^(n-1) = cd, 1 <= c < sqrt(p^(n-1)), (c,d) = (1,p^(n-1)), (a,b) = (p,p^n)
...
g = p^k, A/g = p^(n-k) = cd, 1 <= c < sqrt(p^(n-k)), (c,d) = (1,p^(n-k)), (a,b) = (p^k,p^n)
...
g = p^(n-1), A/g = p = cd, 1 <= c < sqrt(p), (c,d) = (1,p), (a,b) = (p^(n-1),p^n)
g = p^n, A/g = 1 = cd, 1 <= c < sqrt(1) < 1, (c,d) = NG, (a,b) = NG
N(A) = N(p^n) = n
だからです。

さらに,
 命題3 A = Br, r は素数で B r は互いに素の場合,
 N(A) = 2 * N(B) + 1 + N(B) = 3 * N(B) + 1
がいえそうです。これは,次のように考えられます。
A = Br, g = B
の約数,B の約数 * r
g = B の約数 の場合 A/g = B/g * r です。
B/g = ef
e, f は互いに素とし,
そのような (e,f) のうち 1 <= e < sqrt(B/g) となる e の個数を n(B/g) とすると,
f = B/g * 1/e > B/g * 1/sqrt(B/g) = sqrt(B/g)
なので,
全体の互いに素な約数の個数は,e f とを合わせて 2 * n(B/g) です。
つまり,sqrt(B/g) より小さい場合の個数は,全体の半分になります。
一方,A/g = B/g * r = cd c は,B/g のものと B/g のものに r を掛けたもので 4 * n(B/g) です。
1 <= c < sqrt(A/g)
はこの半分なので,2 * n(B/g) になります。
つまり,c の個数は e の個数の 2 倍です。
ただし,g = B の場合は,B/g = 1, 1 <= e < sqrt(B/g) = 1 なる e は存在せず特別ですが,
A/g = r, 1 <= c < sqrt(A/g) = sqrt(r)
で,c = 1 が新たに存在します。
そこで,この特殊な場合以外は常に 2 倍になるので,個数は 2 * N(B) + 1 になります。
g = B の約数 * r の場合 g = rg', g' B の約数,として,A/g = B/g' です。
B/g' = A/g = cd
で,B/g' r が掛かっていない場合と同じなので,個数は N(B) になります。
以上ですべてなので,結局,
N(A) = 2 * N(B) + 1 + N(B) = 3 * N(B) + 1
になります。

そして,これを拡張すると,
 命題4 A = B * r^n, r は素数で B r は互いに素の場合,
 N(A) = (2 * N(B) + 1) * n + N(B) = (2n+1) * N(B) + n
がいえます。これは,命題3 とほとんど同じに考えられます。
A = B * r^n, g = B
の約数,B の約数 * rB の約数 * r^2...B の約数 * r^n
g = B の約数 * r^k, k = 0 n-1 の場合 A/g = B/g * r^(n-k) です。
命題3 と同じ記法で同じに考えて,B/g に関し全体の互いに素な約数の個数は,2 * n(B/g) です。
一方,A/g = B/g * r^(n-k) = cd c は,c, d が互いに素なので,
B/g
のものと B/g のものに r^(n-k) を掛けたものしかなく,4 * n(B/g) です。
1 <= c < sqrt(A/g)
はこの半分なので,2 * n(B/g) になり,やはり 2 倍です。
ただし,g = B * r^k の場合は,
A/g = r^(n-k), 1 <= c < sqrt(A/g) = sqrt(r^(n-k))
で,c, d は互いに素なので c = 1 だけです。
そこで,この特殊な場合以外は常に 2 倍になるので,個数は 2 * N(B) + 1 になります。
これが,k = 0 n-1 n 個あることになり,全体で (2 * N(B) + 1) * n です。
g = B の約数 * r^n の場合 g = r^n * g' として,A/g = B/g' です。
B/g' = A/g = cd
で,B/g' r が掛かっていない場合と同じなので,個数は N(B) になります。
以上ですべてなので,結局,
N(A) = (2 * N(B) + 1) * n + N(B) = (2n+1) * N(B) + n
になります。

以上で,一般に,p, q, ..., r を素数として,A = p^n * q^m * ... * r^k の場合は,
・命題2 より,N(p^n) を求める。
・命題4 より,順次,q^m を掛けた場合,...r^k を掛けた場合,をそれぞれ求めていく。
で得ることができます。

例えば,
N(2) = 1
N(6) = N(2 * 3) = 3 * N(2) + 1 = 3 * 1 + 1  4
N(3) = 1
N(15) = N(3 * 5) = 3 * N(3) + 1 = 3 * 1 + 1 = 4
N(5) = 1
N(35) = N(5 * 7) = 3 * N(5) + 1 = 3 * 1 + 1 = 4
N(105) = N(3 * 5 * 7) = 3 * N(3 * 5) + 1 = 3 * 4 + 1 = 13
N(210) = N(2 * 3 * 5 * 7) = 3 * N(3 * 5 * 7) + 1 = 3 * 13 + 1 = 40
N(2310) = N(2 * 3 * 5 * 7 * 11) = 3 * N(2 * 3 * 5 * 7) + 1 = 3 * 40 + 1 = 121
N(4) = N(2^2) = 2
N(12) = N(2^2 * 3) = 3 * N(2^2) + 1 = 3 * 2 + 1 = 7
N(12) = N(3 * 2^2) = 5 * N(3) + 2 = 5 * 1 + 2 = 7
N(36) = N(2^2 * 3^2) = 5 * N(2^2) + 2 = 5 * 2 + 2 = 12
となります。

(
感想)
今回は久しぶりに少し骨のある問題でした。
一般の場合が正しいことを祈ります (^^;

 

NO2 kashiwagi 9/25 0802分受信

kashiwagi 9/26 0840分受信 更新10/5

213回解答

ある数は必ず素数の積に分解されるので試みると、今回の問題の数は以下の様になる。

62×3

153×5

355×7

1053×5×7

2102×3×5×7

23102×3×5×7×11

ここで一般的に考えてみると、題意より最小公倍数が6ということは、6の公約数と6の組み合わせ、および公約数を持たない2数の組み合わせとなる。因って、求めるものは(1,6)(2,6)(3,6)(2,3)という事になる。即ち、N6)=4となる。

次に105を考えてみると、全く同様な考え方で1051357152135更に353152121515および157になる。即ち、(1,105)(3,105)(5,105)(7,105)(15,105)(21,105)(35,105)(3,35)(15,35)(21,35)(5,21)(15,21)(7,15

因って、N(105)13となる。

他も全く同様な考え方でやりまとめると、

問題1.3.

N6)=N(15)N(35)4

問題4.

N(105)13

問題5.

N(210)40

問題6.

N(2310)113

 

問題16を表にまとめ、N(A)を算定する式をじっと眺めて推定すると、約数の種類Nが関係していそうだと分かるので、試行錯誤してみると、

A

約数の種類(N

N(A)

N(A)の階差

6,15,35

2

4

932

105

3

13

2733

210

4

40

8134

2310

5

121

 

階差からN(A)=(3N+1-1/2 となることが判明する。

但し、この式は数Aが各々1個ずつの素数の積で表せた場合であり、素数の累乗積の場合は当てはまらない。

 

kasama    9/26 2331分受信 更新10/31

 

正の整数の組(a,b)(a,b)=(p1α1p2α2…pnαn,p1β1p2β2pnβn)と素因数分解されたします。このとき、組(a,b)の最小公倍数c

 c=p1γ1p2γ2pnγn ただし、γi=max(αii)(i=1,2,…,n)

と表すことができます。

逆に、最小公倍数がA=p1γ1p2γ2pnγnとなるような正数の組(a,b)=(p1α1p2α2…pnαn,p1β1p2β2pnβn)について考えます。i番目の素因数piの組み合わせは、(αii)=(γi,0),(γi,1)…(γii)…(1,γi),(0,γi)2(γi+1)-1個だから、すべての素因数で考えると、{2(γ1+1)-1}{2(γ2+1)-1}…{2(γn+1)-1}個あります。この中には、a=bとなるのが1個、残りはa<ba>bで半分ずつなので、a<bとなるような組(a,b)の個数は、1引いて2で割った数です。つまり、

 N(A)

=

{2(γ1+1)-1}{2(γ2+1)-1}…{2(γn+1)-1}-1


2

と表すことができます。この考察をもとに、問題を解くと下表のようになります。

問題

A(素因数分解)

N(A)

1

6=23

{2(1+1)-1}{2(1+1)-1}-1

=

4


2

2

15=35

{2(1+1)-1}{2(1+1)-1}-1

=

4


2

3

35=57

{2(1+1)-1}{2(1+1)-1}-1

=

4


2

4

105=357

{2(1+1)-1}{2(1+1)-1}{2(1+1)-1}-1

=

13


2

5

210=2357

{2(1+1)-1}{2(1+1)-1}{2(1+1)-1}{2(1+1)-1}-1

=

40


2

6

2310=235711

{2(1+1)-1}{2(1+1)-1}{2(1+1)-1}{2(1+1)-1}{2(1+1)-1}-1

=

121


2

 

 

皆さん、答えがわかったら、一部でも構いませんから、解答とペンネームを添えて、
メールで送ってください。待っています。