作者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