Определим qi=[di-2/di-1], где[ ] означает целую часть дроби di-2/di-1.
Теперь общее выражение для fi, gi и di может быть представлено в следующем виде: Ei =Ei-2 - qiEi-1.
Для подтверждения этого представим процесс нахождения НОД(186,66) в виде таблицы:
|
Шаг i |
fi |
gi |
di |
qi |
fi·a+gi·b=di |
|
-1 |
1 |
0 |
186 |
- |
1·186+0·66=186 |
|
0 |
0 |
1 |
66 |
- |
0·186+1·66=66 |
|
1 |
1 |
-2 |
54 |
[186/66]=2 |
1·186-2·66=54 |
|
2 |
-1 |
3 |
12 |
[66/54]=1 |
-1·186+3·66=12 |
|
3 |
5 |
-14 |
6 |
[54/12]=4 |
5·186-14·66=6 |
|
4 |
-11 |
31 |
0 |
[12/6]=2 |
-11·186+31·66=0 |
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.