作业帮 > 数学 > 作业

欧几里德算法证明中,为什么已知d|a且d|b且a=kb+r时,就得到d|r?

来源:学生作业帮 编辑:大师作文网作业帮 分类:数学作业 时间:2024/11/17 14:14:26
欧几里德算法证明中,为什么已知d|a且d|b且a=kb+r时,就得到d|r?
欧几里德算法证明中,为什么已知d|a且d|b且a=kb+r时,就得到d|r?
由d|a知存在整数m1使得a = m1*d;由d|b知存在整数m2使得b = m2 * d.
r = a - k*b = m1*d - k * m2 * d = (m1 - k * m2) * d,m1-k*m2为整数,则d|r.