MENU
277,837

スレッドNo.368

gcd,lcm連立方程式

(1)
自然数A.B(A<B)があり
gcd(A,B)=84
lcm(A,B)=3528
である時A,Bは?

(2)
自然数A,B,C(A<B<C)があり
gcd([A,B,C])=12
lcm([A,B,C])=144
である時A,B,Cは?

(3)
自然数A,B,C(A<B<C)があり
gcd([A,B,C])=12
lcm([A,B,C])=720
である時A,B,Cは?

引用して返信編集・削除(編集済: 2022年10月31日 10:31)

(1)は、(A,B)=(84,3528)、(168,1764)、(252,1176)、(504,588)
(2)は、(A,B,C)=(12,36,48)
(3)は、(A,B,C)=(12,36,240)、(12,48,180)、(12,60,144) ですね!

引用して返信編集・削除(編集済: 2022年11月02日 02:44)

解は意外と多くて
(2)
1;(12,24,144)
2;(12,36,48)
3;(12,36,144)
4;(12,48,72)
5;(12,48,144)
6;(12,72,144)
7;(24,36,48)
8;(24,36,144)
9;(36,48,72)
10;(36,48,144)


(3)
1;(12,24,720)
2;(12,36,240)
3;(12,36,720)
4;(12,48,180)
5;(12,48,360)
6;(12,48,720)
7;(12,60,144)
8;(12,60,720)
9;(12,72,240)
10;(12,72,720)
11;(12,120,144)
12;(12,120,720)
13;(12,144,180)
14;(12,144,240)
15;(12,144,360)
16;(12,144,720)
17;(12,180,240)
18;(12,180,720)
19;(12,240,360)
20;(12,240,720)
21;(12,360,720)
22;(24,36,240)
23;(24,36,720)
24;(24,48,180)
25;(24,60,144)
26;(24,60,720)
27;(24,144,180)
28;(24,180,240)
29;(24,180,720)
30;(36,48,60)
31;(36,48,120)
32;(36,48,180)
33;(36,48,240)
34;(36,48,360)
35;(36,48,720)
36;(36,60,144)
37;(36,60,240)
38;(36,60,720)
39;(36,72,240)
40;(36,120,144)
41;(36,120,240)
42;(36,120,720)
43;(36,144,240)
44;(36,180,240)
45;(36,240,360)
46;(36,240,720)
47;(48,60,72)
48;(48,60,144)
49;(48,60,180)
50;(48,60,360)
51;(48,60,720)
52;(48,72,180)
53;(48,120,180)
54;(48,144,180)
55;(48,180,240)
56;(48,180,360)
57;(48,180,720)
58;(60,72,144)
59;(60,72,240)
60;(60,72,720)
61;(60,120,144)
62;(60,144,180)
63;(60,144,240)
64;(60,144,360)
65;(60,144,720)
66;(72,180,240)
67;(120,144,180)
68;(144,180,240)
だけ存在できます。

この解の個数は
gcd(A,B,C)=G,lcm(A,B,C)=L
A=a*G;B=b*G;C=c*G ((a,b,c)は互いに素)とするとき
gcd([a,b,c])==1かつlcm([a,b,c])==L/G
を満たす(a,b,c)の組合せが存在する数と対応しています。
(2)なら144/12=12,(3)なら720/12=60ですので

(2)gcd([a,b,c])==1かつlcm([a,b,c])=12
(3)gcd([a,b,c])==1かつlcm([a,b,c])==60
でその組合せが決まり、それぞれから10通り,68通りが生じてきます。

A,Bの2つでの場合しか経験してなかったので、3つの場合を調べていて
こんなにも多く存在することに驚いてしまいました。

このことからL/Gの値が解の個数の決め手になっていることが面白く感じたので
s=L/Gの値で解の個数が如何ほどか調査してみたら100までのもので
s; 解の個数
1; 0 21; 4 41; 0 61; 0 81; 3
2; 0 22; 4 42; 32 62; 4 82; 4
3; 0 23; 0 43; 0 63; 10 83; 0
4; 1 24; 16 44; 10 64; 5 84; 68
5; 0 25; 1 45; 10 65; 4 85; 4
6; 4 26; 4 46; 4 66; 32 86; 4
7; 0 27; 2 47; 0 67; 0 87; 4
8; 2 28; 10 48; 22 68; 10 88; 16
9; 1 29; 0 49; 1 69; 4 89; 0
10; 4 30; 32 50; 10 70; 32 90; 68
11; 0 31; 0 51; 4 71; 0 91; 4
12; 10 32; 4 52; 10 72; 34 92; 10
13; 0 33; 4 53; 0 73; 0 93; 4
14; 4 34; 4 54; 16 74; 4 94; 4
15; 4 35; 4 55; 4 75; 10 95; 4
16; 3 36; 22 56; 16 76; 10 96; 28
17; 0 37; 0 57; 4 77; 4 97; 0
18; 10 38; 4 58; 4 78; 32 98; 10
19; 0 39; 4 59; 0 79; 0 99; 10
20; 10 40; 16 60; 68 80; 22 100; 22

100倍まではs=60,84,90
で最も多く68通り

このことはgcd(A.B,C)=Gの値が何であれ、例えば
gcd(A.B,C)=8
lcm(A,B,C)=8*60=480

gcd(A.B,C)=10
lcm(A,B,C)=10*60=600

gcd(A.B,C)=11
lcm(A,B,C)=11*84=924

gcd(A.B,C)=16
lcm(A,B,C)=16*90=1440

それぞれを満たす解の個数はすべて68通り存在することができます。
この同じ68の値を発生させるsの特徴は
60=2^2*3*5
84=2^2*3*7
90=2*3^2*5
で一般に素数p,q,rでp^2*q*r型で示されます。

このことからsの数字の特徴がsの素因数構造で分類できることが起こせます。
sを1000まで延長させて分類すると(以下p,q,r,sは素数です。大小を問いません。)
s=p^(k+1) ->k(k=0,1,2,・・・)
s=p*q ->4
s=p^2*q ->10
s=p^3*q ->16
s=p^4*q(またはq^2*q^2) ->22
s=p^5*q ->28
s=p^6*q ->34
s=p^7*q ->40
s=p^4*q^2(またはp^8*q) ->46
s=p^5*q^2 ->58
s=p^4*q^3(またはp^6*q^2) ->70
s=p^5*q^3 ->88
s=p*q*r ->32
s=p^2*q*r ->68
s=p^3*q*r ->104
s=q^4*q*r(またはp^2*q^2*r) ->140
s=p^5*q*r ->176
s=p^3*q^2*r ->212
s=p^4*q^2*r ->284
s=p*q*r*s ->208
s=p^2*q*r*s ->424
s=p^3*q*r*s ->640

の様な対応がつけられました。

引用して返信編集・削除(未編集)

法則を見つけただけで証明はしていませんが、上の計算は
n=(素数の種類の数)、m=(各素因数の指数の積)とすると
6^(n-1)×m - 2^(n-1)
と表されますね。

引用して返信編集・削除(編集済: 2022年11月02日 20:46)

お~~!!
こんな式で統一できるんだ。
途中でp^4*qとp^2*q^2、p^6*qとp^3*q^2、p^4*q^3とp^6*q^2などが同じ数字が対応してきていたので不思議に感じていました。
こんな背景があったのですね。

引用して返信編集・削除(未編集)

全くの勘であって確認していませんが、
3数A,B,C で 6^(n-1)×m - 2^(n-1) = 3!^(n-1)×m - 2!^(n-1) ならば
4数A,B,C,Dの場合は 4!^(n-1)×m - 3!^(n-1) = 24^(n-1)×m - 6^(n-1) かも?

(追記)
その理屈だと2数の場合に2!^(n-1)×m-1!^(n-1)=2^(n-1)×m-1となりますが、
(84,3528)のときに合わないので違いますね。

引用して返信編集・削除(編集済: 2022年11月03日 23:02)

4数A,B,C,Dの場合
p^n->1/2*(n-1)*(n-2) (n≧3)
p*q->1
p^2*q->13
p^3*q->39
p*q*r->64
p^2*q^2->70
p^4*q->79
p^5*q->133
p^3*q^2->177
p^6*q->201
p^7*q->283
p^2*q*r->304
p^4*q^2->334
p^8*q->379
p^3*q^3->425
p^5*q^2->541
p^3*q*r->740
p^4*q^3->783
p^6*q^2->798
p^2*q^2*r->1246
p^5*q^3->1251
p*q*r*s->1284
p^4*q*r->1372
p^5*q*r->2200
p^3*q^2*r->2888
p^6*q*r->3224
p^2*q^2*r^2->4780
p^2*q*r*s->5076
p^4*q^2*r->5230
p^3*q*r*s->11612

なる対応になると思いますが・・・
その他のパターンは0が対応しています。
(重複部分は解消されます。)

引用して返信編集・削除(編集済: 2022年11月04日 09:58)

4数になるとずいぶんと複雑になるのですね。「全くの勘」は完全にはずれでした。
素因数2種類、3種類の一般式は
p^m*q^n → 6(mn)^2+m^2+n^2-9mn+2
p^l*q^m*r^n → 70(lmn)^2+14{(lm)^2+(mn)^2+(nl)^2}-54(lm+mn+nl-l-m-n)-48
あたりでしょうか。
(l,m,n>1の場合は例が一つしかなかったのでl=m=n=2以外では正しくないかも知れません)

引用して返信編集・削除(編集済: 2022年11月04日 12:22)

追加データ
p^3*q^2*r->2888
p^3*q^2*r^2->10814
p^4*q^2*r->5230
p^4*q^2*r^2->19348
p^4*q^3*r->11804
p^4*q^3*r^2->43166
p^4*q^3*r^3->95868
p^5*q^2*r->8272
p^5*q^2*r^2->30382
p^5*q^3*r->18572
p^5*q^3*r^2->67592
p^5*q^3*r^3->149832
p^5*q^4*r->33100
p^5*q^4*r^2->119902
p^5*q^4*r^3->265292
p^5*q^4*r^4->469270
p^5*q^5*r->51856
p^5*q^5*r^2->187312
p^5*q^5*r^3->413972
p^5*q^5*r^4->731836

引用して返信編集・削除(編集済: 2022年11月04日 14:40)

時間がかかりましたが、ようやく素因数3種類の一般式が出せました。
p^l*q^m*r^n → (1/3){(6l^2+1)(6m^2+1)(6n^2+1)+11}-54lmn
という比較的綺麗な式になりました。
これにならうと、素因数2種類の一般式は
p^m*q^n → (1/6){(6m^2+1)(6n^2+1)+11}-9mn
となり似たような形になります。
両方とも「11」という定数が含まれているのが面白いですね。
この形から素因数4種類の一般式を数少ないデータを使って予想すると
p^k*q^l*r^m*s^n → (2/3){(6k^2+1)(6l^2+1)(6m^2+1)(6n^2+1)+11}-324klmn
それにより完全な一般式は素因数n種類で指数がa[1],a[2],…,a[n]のとき
(1/24){(2^n)(Π{6(a[k])^2+1}+11)-(6^(n+1))Πa[k]}
となりそうで、これは素因数が1種類の場合も正解と一致しています。

引用して返信編集・削除(編集済: 2022年11月04日 16:42)

自分も一般式が構成出来ないものかと、らすかるさんが見つけられた様式を参考にあれこれ挑戦していたんですが、係数が分数になったり
素数の指数と上手く連動しなかったりと、ほとんど絶望状態でした。
ほんの一部でi=1,2,3,・・・で
p^i*q^i->(2*i^2-1)*(3*i^2-2)
p^i*q*r->98*i^2-54*i+20
p^i*q->7*i^2-9*i+3
p^m*q^2->25*m^2-18*m+6 (m=2,3,4,・・・)
p^n*q^3->55*n^2-27*n+11 (n=3,4,5,・・・)
などの個別の式でした。

これを一気に記述できる一般式に到達出来ることが物凄いです。
論理的に攻めて行けるものなのですか?
それとも何となくこんな式なのかと直感的に予測していくのですか?
自分なりにあれこれ挑戦した感覚としてこんな式のあり様がどこから考えてこれるのかとても不思議です。

引用して返信編集・削除(未編集)

式の形は無数にありますので、「何となくこんな式なのかと直感的に予測」はほとんど無理ですね。
特別な場合の式を立て、それを統合する式を考えていってすべて論理的に攻めてます。
今回の場合は、「l,m,nに関して対称」ということがかなり使えました。

引用して返信編集・削除(未編集)

このスレッドに返信

このスレッドへの返信は締め切られています。

ロケットBBS

Page Top