In addition to easily finding the gcd the Euclidean algorith
来源:学生作业帮 编辑:作业帮 分类:英语作业 时间:2024/05/15 08:48:04
In addition to easily finding the gcd the Euclidean algorithm does something else.Let's
see how this works for our example.We now know that (3589,2522) = 97 which means
that we know that there must be integers m and n such that 3589m+ 2522n = 97 .The
proof of this is a purely theoretical result that gives no hint as to how to find these
integers.But the Euclidean algorithm finds them for us!Let's see how this works.
We will start with the last equation 388 = 291×1+ 97 .From this equation we were able to
conclude that (388,291) = 97 but it is also easy to see that we can use the equation to
write 97 as a linear combination of 388 and 291.We just solve for 97 to get:
(*) 97 = 388×(1) + 291×(-1)
We can now use the previous equation 1067 = 388× 2 + 291 to express 291 as a linear
combination of 1067 and 388.
(**) 291 =1067×(1) + 388×(-2)
We now use (**) to substitute into (*) to express 97 as a linear combination of 388 and
1067.
(***) 97 = 388×(1) + [1067×(1) + 388×(-2)] ×(-1) = 388(3) +1067 ×(-1)
We can now use the equation 2522 =1067 ×2 + 388 to express 388 as a linear
combination of 2522 and 1067 and then substitute that into (***) to express 97 as a linear
combination of 2522 and 1067.
最后问题是:
Exercise 9:Continue this process until you have found the integers m and n so that
3589m+ 2522n = 97
see how this works for our example.We now know that (3589,2522) = 97 which means
that we know that there must be integers m and n such that 3589m+ 2522n = 97 .The
proof of this is a purely theoretical result that gives no hint as to how to find these
integers.But the Euclidean algorithm finds them for us!Let's see how this works.
We will start with the last equation 388 = 291×1+ 97 .From this equation we were able to
conclude that (388,291) = 97 but it is also easy to see that we can use the equation to
write 97 as a linear combination of 388 and 291.We just solve for 97 to get:
(*) 97 = 388×(1) + 291×(-1)
We can now use the previous equation 1067 = 388× 2 + 291 to express 291 as a linear
combination of 1067 and 388.
(**) 291 =1067×(1) + 388×(-2)
We now use (**) to substitute into (*) to express 97 as a linear combination of 388 and
1067.
(***) 97 = 388×(1) + [1067×(1) + 388×(-2)] ×(-1) = 388(3) +1067 ×(-1)
We can now use the equation 2522 =1067 ×2 + 388 to express 388 as a linear
combination of 2522 and 1067 and then substitute that into (***) to express 97 as a linear
combination of 2522 and 1067.
最后问题是:
Exercise 9:Continue this process until you have found the integers m and n so that
3589m+ 2522n = 97
m=-7,n=10
因为2522=1067 ×2 + 388...(1) ;同理3589=1067 ×3+ 388.(2)
又因为97=388×3 +1067 ×(-1)
3589m+2522n=97 .(3)将(1) (2)代入(3)得
(2n+3m)×1067+(n+m)×388=97 所以
2n+3m=-1
n+m=3得到答案
也可以直接根据这个程序 一直运算
因为2522=1067 ×2 + 388...(1) ;同理3589=1067 ×3+ 388.(2)
又因为97=388×3 +1067 ×(-1)
3589m+2522n=97 .(3)将(1) (2)代入(3)得
(2n+3m)×1067+(n+m)×388=97 所以
2n+3m=-1
n+m=3得到答案
也可以直接根据这个程序 一直运算
In addition to easily finding the gcd the Euclidean algorith
英语翻译In addition to the general difficulty in bringing invest
英语翻译change the current DRIVE in addition to changing folder.
In addition to the distance between you and me not
In addition to n______ rivers,the ancient Chinese people als
英语翻译in addition to the interface designer are directors,prod
翻译In addition to the satisfaction of supporting our work.
英语翻译In addition to the exuberances and deficiencies introduc
Xin Yi Xi' An store,in addition to the scar
英语翻译In addition to finding an increase of suitable browse,li
英语翻译In addition to finding an increase of suitable browse,x,
英语翻译In addition the ability to link the spare parts costs to