拓展欧几里得算法是否一定能保证解满足|x|,|y|≤max(|a|,|b|)?
  • 板块学术版
  • 楼主Pecco
  • 当前回复1
  • 已保存回复1
  • 发布时间2020/9/9 12:02
  • 上次更新2023/11/5 13:31:17
查看原帖
拓展欧几里得算法是否一定能保证解满足|x|,|y|≤max(|a|,|b|)?
70304
Pecco楼主2020/9/9 12:02

众所周知拓展欧几里得可以给出不定方程 ax+by=gcd(a,b)ax+by=\gcd(a,b) 的特解,我在使用中发现似乎这组特解总是满足 x,ymax(a,b)|x|,|y|≤\max(|a|,|b|) (进一步地,如果 a,b0a,b≠0,似乎还满足 xb,ya|x|≤|b|,|y|≤|a|

我想知道这个结论是不是总是成立,以及如何证明。

2020/9/9 12:02
加载中...