「ユークリッドの互除法」の版間の差分
提供: miniwiki
細 |
細 |
||
| 1行目: | 1行目: | ||
'''ユークリッドの互除法'''（ユークリッドのごじょほう、{{Lang-en-short|Euclidean Algorithm}}） | '''ユークリッドの互除法'''（ユークリッドのごじょほう、{{Lang-en-short|Euclidean Algorithm}}） | ||
| − | 二つの[[自然数]] | + | 二つの[[自然数]] |
<i>a</i> | <i>a</i> | ||
| − | + | <sub>1</sub>と <i>a</i> | |
| − | + | <sub>2</sub>の最大公約数（[[約数]]）を求めるための一つの方法。<i>a</i> | |
| − | + | <sub>1</sub>≧<i>a</i> | |
| − | + | <sub>2</sub>として，次の割り算を実行する。 | |
| − | + | <html> | |
| − | |||
<table border="0" cellspacing="10" width="559"> | <table border="0" cellspacing="10" width="559"> | ||
2019/4/27/ (土) 23:08時点における最新版
ユークリッドの互除法（ユークリッドのごじょほう、英: Euclidean Algorithm）
二つの自然数 a 1と a 2の最大公約数（約数）を求めるための一つの方法。a 1≧a 2として，次の割り算を実行する。
| a 1＝a 2 q 1＋a 3 | q 1は商，a 3は余り | |
| a 2＝a 3 q 2＋a 4 | q 2は商，a 4は余り | |
| ………… | ………… | |
| an -1＝a n qn -1＋an +1 | q n -1は商，a n +1は余り | |
| a n＝a n＋1 q n | q nは商，余りはなし |
最後に余りがなかったならば，この an +1が最初の 2数 a 1と a 2の最大公約数である。（整数論，ユークリッド）