因數與倍數證明題

設 a , b 是非零整數 , c 是整數 , ax + by = c 有整數解的充分必要條件為(a，b)的最大公因數為 c 的因數。
先證必要性 :令 d 為(a，b)的最大公因數 ,則 d 明顯整除 ax 及 by,
故 d 整除左方 ax + by , 即 d 整除 c 。
再證充分性 :令 c = dk 。可知 ax + by = d 必有整數解
(因 d 是 a , b 的最大公因數 , a , b 可通過輾轉相除最後求得 d )令 ax + by = d 的整數解為 x" , y" ,則 ax" + by" = da(kx") + b(ky") = dka(kx") + b(ky") = c故 ax + by = c 有整數解 (kx" , ky")

根據輾轉相除法原理的反推過程

我們有了以下的定理

若(a,b)=d, 則可以找到一組整數m,n

使得 ma+nb=d



所以,若(a，b)的最大公因數 d 為c的因數

令 c=dt

則 mta+ntb=dt=c

所以,可以找到一組整數 mt, nt

為 ax+by=c的整數解