| ■41279 / ) |
Re[1]: 最大公約数に関する問題です
|
□投稿者/ miyup 大御所(1064回)-(2010/03/31(Wed) 22:34:44)
 | ■No41276に返信(SATYさんの記事)
> ２つの整数6186と4709の最大公約数(6189,4709)を求めよ。また、この最大公約数に対して、(6189,4709)=6186X+4709YとなるX,Yを見つけよ。という問題です。最大公約数は1と求められたのですが、後半の(6189,4709)=6186X+4709YとなるX,Yを見つけよ。はどうしたら良いのでしょうか？
互除法を利用
6189=4709*1+1480
4709=1480*3+269
1480=269*5+135
269=135*1+134
135=134*1+1
より
1480=6189-4709*1 …①
269=4709-1480*3 …②
135=1480-269*5 …③
134=269-135*1 …④
1=135-134*1 …⑤
として
⑤に④③②①の順に代入していくと
1=6189*35-4709*46
となるので
X=35, Y=-46
|
|