2020-2021:teams:farmer_john:裴蜀定理证明
|
2020-2021:teams:farmer_john:裴蜀定理证明 [2020/09/05 15:42] jjleo 创建 |
2020-2021:teams:farmer_john:裴蜀定理证明 [2020/09/05 15:42] (当前版本) jjleo |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | 裴蜀定理：若ax+by = z，则 gcd（a，b）| z | + | 裴蜀定理：若ax+by = z，则 gcd（a，b）| z\\ |
| - | 再顺手证明一下裴蜀定理： | + | 再顺手证明一下裴蜀定理：\\ |
| - | 设k = gcd（a，b），则 k | a， k | b，根据整除的性质，有 k | （ax+by） | + | 设k = gcd（a，b），则 k | a， k | b，根据整除的性质，有 k | （ax+by）\\ |
| - | 设 s为ax+by的最小正数值 | + | 设 s为ax+by的最小正数值\\ |
| - | 再设 q = [a / s]（a整除s的值）；r = a mod s = a-q（ax+by） = a（1 - qx）+b（-qy）； | + | 再设 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的线性组合） | + | 由此可见r也为a，b的线性组合；（ax+by称为a，b的线性组合）\\ |
| - | 又因为s为a，b的线性组合的最小正数值，0<= r < s，所以r的值为0，即 a mod s = r =0；s | a； | + | 又因为s为a，b的线性组合的最小正数值，0<= r < s，所以r的值为0，即 a mod s = r =0；s | a；\\ |
| - | 同理可得 s | b，则 s | k； | + | 同理可得 s | b，则 s | k；\\ |
| - | 又因为 k | （ax+by），s为ax+by的最小正数值，所以 k | s； | + | 又因为 k | （ax+by），s为ax+by的最小正数值，所以 k | s；\\ |
| - | 因为 s | k，k | s，所以s = k； | + | 因为 s | k，k | s，所以s = k；\\ |
| - | 原命题得证。 | + | 原命题得证。\\ |
| [[https://blog.csdn.net/leader_one/article/details/75298966?utm_medium=distribute.pc_aggpage_search_result.none-task-blog-2~all~first_rank_v2~rank_v25-2-75298966.nonecase&utm_term=%E8%A3%B4%E8%9C%80%E5%AE%9A%E7%90%86%E7%9A%84%E8%AE%B2%E8%A7%A3|原链接]] | [[https://blog.csdn.net/leader_one/article/details/75298966?utm_medium=distribute.pc_aggpage_search_result.none-task-blog-2~all~first_rank_v2~rank_v25-2-75298966.nonecase&utm_term=%E8%A3%B4%E8%9C%80%E5%AE%9A%E7%90%86%E7%9A%84%E8%AE%B2%E8%A7%A3|原链接]] | ||
2020-2021/teams/farmer_john/裴蜀定理证明.1599291748.txt.gz · 最后更改: 2020/09/05 15:42 由 jjleo
