作业帮若a,b是自然数,(a,b)=d,则存在整数s,t.满足sa+tb=d.为什么写在纸上的,
来源：学生作业帮助网 编辑：作业帮 时间：2024/04/20 14:48:29
若a,b是自然数,(a,b)=d,则存在整数s,t.满足sa+tb=d.为什么写在纸上的,
若a,b是自然数,(a,b)=d,则存在整数s,t.满足sa+tb=d.为什么
写在纸上的,
若a,b是自然数,(a,b)=d,则存在整数s,t.满足sa+tb=d.为什么写在纸上的,
其中有一个写的有点歧义,m^1,m^2,m^3,...,m^n,n个数
这个其实很简单，就是辗转相除法的原理，我一般叫它“欧几里德定理”。
s和t可以作为辗转相除法的副产品算出来。
辗转相除时：
不妨设a>b
第1步：a = b * m_1 + r_1，其中，0<=r_1
第3步：r_1 = r_2 * m_3 + r_3
……...
全部展开
这个其实很简单，就是辗转相除法的原理，我一般叫它“欧几里德定理”。
s和t可以作为辗转相除法的副产品算出来。
辗转相除时：
不妨设a>b
第1步：a = b * m_1 + r_1，其中，0<=r_1
第3步：r_1 = r_2 * m_3 + r_3
……
倒数第2步（第 n-1 步）：r_(n-3) = r_(n-2) * m_(n-1) + r_(n-1)
最后1步（第 n 步）：r_(n-2) = r_(n-1) * m_n，正好整除，于是：r_(n-1) 就是最大公约数。
由第1步，得到：r_1 = a - b * m_1
再代入第2步，得到：
r_2 = b - r_1 * m_2 = b - (a - b * m_1) * m_2 = - m_2 * a + (1 + m_1 m_2) b
也就是，将 r_2 写成：x_2 a + y_2 b 的形式，其中 x_2、y_2 都是整数
再代入第3步，得到：
r_3 = r_1 - r_2 * m_3 = a - b * m_1 - (- m_2 * a + (1 + m_1 m_2) b) * m_3
=(1 + m_2 m_3) a + (- m_1 - m_3 - m_1 m_2 m_3) b
也就是，将 r_3 写成：x_3 a + y_3 b 的形式，其中 x_3、y_3 都是整数
……
总之，这么写下去，可以把所有的 r_i 都写成 a 与 b 的整系数组合的形式，也就是：
r_i = x_i a + y_i b ，其中 x_i 和 y_i 都是整数。
最后，到第 n-1 步时，r_(n-1) 也就是最大公约数 d，也能写成这个形式：
d = r_(n-1) = r_(n-3) - r_(n-2) * m_(n-1) = ... = x_(n-1) a + y_(n-1) b
于是，就求得了：s = x_(n-1)，t = y_(n-1)
收起