Re: [中學]

[julang (君語)]

※ 引述《AAJJBurnett (叫我投手)》之銘言：
:  設a=3^50-3 b=3^49+3^48+1
:  則a與b的最大公因數為何?

提供另種想法

由線性組合知,gcd(a,b)整除 C1 a + C2 b
取 a-3b=-6 => gcd只能為 6, 3 , 2 ,1

又顯然地 a= (-3) = 1 mod2
         b= 0 + 0 + 1 = 1  mod3

故知 gcd只能為 1

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.26.161.79
→ theoculus   :a-3b=-6 ???  a= (-3) = 1 mod2 ?????
→ julang      :同餘的概念能推廣到負整數,但是決定因數時要記得取正
→ julang      :餘數最後也是得取正
→ julang      :太急著打 ,打錯了XD
→ julang      :雖然不小心打錯,不過我要補充一下幾點
→ julang      :1.輾轉相除法只需要做到某數夠好看,判斷出gcd即可
→ julang      :2.同餘可以推廣到負整數
→ julang      :唯最後運算取餘數時,要記得取正,且要小於除數
→ theoculus   :除數b, 餘數r    ;   0 ≦ r <  | b |