若a,b是自然数,(a,b)=d,则存在整数s,t.满足sa+tb=d.为什么写在纸上的,
来源:学生作业帮助网 编辑:作业帮 时间:2024/08/29 02:24:12
若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第2步,再做 b 和 r_1 的辗转相除:b = r_1 * m_2 + r_2
第3步:r_1 = r_2 * m_3 + r_3
……...
全部展开
这个其实很简单,就是辗转相除法的原理,我一般叫它“欧几里德定理”。
s和t可以作为辗转相除法的副产品算出来。
辗转相除时:
不妨设a>b
第1步:a = b * m_1 + r_1,其中,0<=r_1第2步,再做 b 和 r_1 的辗转相除:b = r_1 * m_2 + r_2
第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)
收起