Ask 　&
　　Answer

日期	主題	作者(提供者)
2000/08/24	gcd與 lcm的問題	William數學王子

聽我怎麼說！

【救命呀！】 　網友 小哈 問說： 　　在網路的討論區有一個題目如下 　　假設 A @ B 表示A、B兩數的最 　　小公倍數減去最大公因數的值 。 　　　例如 10 @ 14 = 70 - 2 = 68 　　請問若 6 @ x = 87 求 x = ? 　 你可以幫他解決嗎?

【網友 William 的解答】

　　　因為　6 @ x = 87

　　　意思是　lcm(6,x) - gcd(6,x) = 87

　　　我們從以上的算式可以得知

　　　　lcm(6,x) > 87,又因 lcm 的值是六的倍數

　　　　第一個比 87 大的六的倍數是 90

　　　　我們可以假設 lcm(6,x) = 90

　　　　　90 - gcd(6,x) = 87

　　　　因為　gcd(6,x) >= 1, gcd 的值是 1, 2, 3, 6

　　　　因此　 gcd(6,x) = 3 從理論得知,

　　　　　lcm(x,y) = x*y/gcd(x,y)

　　　　所以 90 = 6x/3,

　　　　　　270 = 6x,

　　　　　　so x = 45

　　　　【check】

　　　　　 90 = 6 * 15

　　　　　　90 = 45 * 2

　　　　　so lcm(6,45) = 90

　　　　　　　6/3 = 2

　　　　　　　45/3 = 15 so

　　　　　gcd(6,45) = 3 therefore, X = 45

 

【數學王子的提醒】

　　　１這個問題看起來好像很難，其實真的動手卻是不難?

　　　　為什麼？由最大公因數與最小公倍數的定義下手。

　　　　設A，B的最大公因數為d，則一定存在p，q

　　　　　滿足　A=pd ，B=qd 　　其中(p,q)=1

　　　２複習了以上的最大公因數的概念後，那最小公倍數也就解決了

　　　　若A=pd ，B=qd　其中(p,q)=1

　　　　　則[A ,B]=dpq

　 　　【例如】

　　　　　　　　20=4×5 　　32=4×8

　　　　　　∴(20 , 32) = 4 　 且5 , 8互質　 【(5,8)=1】

　　　　　　[20 , 32] = 4×5×8=160

　　　　　　還不太了解，用短除作一次就知道了

　　　　　　　　　　　　　　　

　　　３假設 A @ B 表示A、B兩數的最小公倍數減去最大公因數的值

　　　　若 6 @ x = 87 求 x = ?

　　　　【作法】

　　　　　設A=pd ，B=qd　其中(p,q)=1

　　　　　（A ,B）= d 　[A ,B]=dpq

　　　　　　 6 @ x = 87

　　　　　　[6 ,x]-(6 ,x) = 87

　　　　　　 dpq－d=87

　　　　　　 d(pq-1)=87=3*29

　　　　　　故（6 ,x）= 3　且　(pq-1)=29

　　　　　　∴pq=30=1×30=2×15=3×10

　　　　　　　p=2 , q=15

　　　　　　　兩數為　３×２=６

　　　　　　　　　　　３×15=４５