※ 引述《AAJJBurnett (叫我投手)》之銘言:
: 設a=3^50-3 b=3^49+3^48+1
: 則a與b的最大公因數為何?
用輾轉相除法
因為b不是3的倍數 所以把a改成a'=3^49-1
所以 b=a'+(3^48+2)
a'=3(3^48+2)-7
故最大公因數為7或1
用費馬小定理得到 b=3(3^6)^8+(3^6)^8+1=3+1+1=5 mod 7
因此b不被7整除
所以最大公因數為1
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.192.216.62