Warning: session_start(): open(/tmp/sess_7463a51c8d9a5a6fac59652b7a450e1e, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103 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；
原命题得证。