作者sarah21 (Derek Jeter)
看板Math
标题[中学] gcd and lcm
时间Sat Mar 5 15:30:44 2011
利用辗转相除法求
(288, 1008)
[288, -1008]
我只知道辗转相除法可以用来求LCM，但是没听说过他可以用来求GCD
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 111.83.90.102
1F：推 robertshih :我倒是听说辗转相除法是用来求gcd的 03/05 15:33
2F：推 superlori :我笑了!!!! 03/05 15:35
3F：推 n19860423 :应该是常用来求gcd吧~XD lcm我反而不太会XD 03/05 15:35
4F：→ n19860423 :但我知道好像是可以做的XD 03/05 15:35
5F：→ superlori :求辗转相除法求完gcd，就可以求lcm了呀!! 03/05 15:36
6F：→ sarah21 :抱歉，说反了 03/05 15:38
7F：→ sarah21 :如何做 可以教我吗 03/05 15:39
8F：→ n19860423 :a*b=(a,b)*[a,b] 03/05 15:40
9F：→ n19860423 :所以(a,b)求到了~[a,b]=a*b/(a,b) 03/05 15:40
10F：→ sarah21 :能否证明一下 为什麽a*b=(a,b)*[a,b] 03/05 15:46
11F：→ sarah21 :这个方法好像不适用超过两个数以上 a*b*c=()*[] 03/05 15:47
12F：推 n19860423 :对~三数以上不适用 03/05 15:49
13F：→ n19860423 :以标准分解式来看，(a,b)是取共同的质因数的最小次方 03/05 15:50
14F：→ n19860423 :[a,b]是取两数所有质因数的最大次方 03/05 15:51
15F：→ n19860423 :一个取共同，一个取所有，次方分别取大的、小的 03/05 15:51
16F：→ n19860423 :所以(a,b)和[a,b]一乘起来刚好就是a*b 03/05 15:52
17F：→ n19860423 :可以从例子来看~108=2^2*3^3 120=2^3*3*5 03/05 15:52
18F：→ n19860423 :(108,120)=(2^2*3^3,2^3*3*5)=2^2*3 03/05 15:53
19F：→ n19860423 :[108,120]=[2^2*3^3,2^3*3*5]=2^3*3^3*5 03/05 15:53
20F：→ n19860423 :(108,120)*[108,120]=(2^2*3)(2^3*3^3*5) 03/05 15:54
21F：→ n19860423 :=(2^2*3^3)*(2^3*3*5)=108*120 03/05 15:55
22F：→ sarah21 :谢谢你 03/05 15:57
23F：→ bibo9901 :(a,b)=d ===> let a=dh, b=dk ===> [a,b]=dhk 03/05 19:59
24F：→ bibo9901 :a*b=dh*dk=d*(dhk)=(a,b)*[a,b] 03/05 19:59
25F：→ mikechan :ab=[a,b](a,b) 03/06 03:37