作业帮 > 数学 > 作业

谁能给我详细的解释一下扩展欧几里德算法,要通俗易懂的啊.

来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/05/09 04:10:32
谁能给我详细的解释一下扩展欧几里德算法,要通俗易懂的啊.
百度里的很难理解,谢谢你的帮助……
1. 若 r 是 a ÷ b 的余数, 则
  gcd(a,b) = gcd(b,r)
  2. a 和其倍数之最大公因子为 a.
  另一种写法是:
  1. a ÷ b,令r为所得余数(0≤r<b)
  若 r = 0,算法结束;b 即为答案.
  2. 互换:置 a←b,b←r,并返回第一步.