2020-2021:teams:farmer_john:裴蜀定理证明
裴蜀定理：若ax+by = z，则 gcd（a，b）| z 再顺手证明一下裴蜀定理： 设k = gcd（a，b），则 k | a， k | b，根据整除的性质，有 k | （ax+by） 设 s为ax+by的最小正数值 再设 q = [a / s]（a整除s的值）；r = a mod s = a-q（ax+by） = a（1 - qx）+b（-qy）； 由此可见r也为a，b的线性组合；（ax+by称为a，b的线性组合） 又因为s为a，b的线性组合的最小正数值，0⇐ r < s，所以r的值为0，即 a mod s = r =0；s | a； 同理可得 s | b，则 s | k； 又因为 k | （ax+by），s为ax+by的最小正数值，所以 k | s； 因为 s | k，k | s，所以s = k； 原命题得证。
2020-2021/teams/farmer_john/裴蜀定理证明.1599291748.txt.gz · 最后更改: 2020/09/05 15:42 由 jjleo
