Линейное представление наибольшего общего делителя (функция ExtendedGCD)
(Продолжение таблицы)
| n | m | d= НОД (n, m) | Основание системы счисления а | Цифры НОД в системе счисления с основанием а | Цифры r в системе счисления с основанием а | Цифры s в системе счисления с основанием а |
|---|---|---|---|---|---|---|
| .. | … | … | … | … | ||
| 5 | 2 | 1 | 2 | {1} | {1} | -{1.0.1.0} |
| 5 | 2 | 1 | 3 | (2) | {1} | -{1.0.1.0} |
| 5 | 2 | 1 | 4 | (3} | {1} | -{1.0.1.0} |
| 5 | 2 | 1 | 5 | (4) | {1} | -{1.0.1.0} |
| 5 | 2 | 1 | 6 | {5} | {1} | -{1.0.1.0} |
| 5 | 2 | 1 | 7 | {6} | {1} | -{1.0.1.0} |
| 5 | 2 | 1 | 8 | {7} | {1} | -{1.0.1.0} |
| 5 | 2 | 1 | 9 | (8) | {1} | -{1.0.1.0} |
| 5 | 3 | 1 | 2 | (1) | -{1.0} | {1.0.0.1} |
| 5 | 3 | 1 | 3 | {2} | -{1.0} | {1.0.0.1} |
| 5 | 3 | 1 | 4 | (3} | -{1.0} | {1.0.0.1} |
| 5 | 3 | 1 | 5 | {4} | -{1.0} | {1.0.0.1} |
| 5 | 3 | 1 | 6 | {5} | -{1.0} | {1.0.0.1} |
| 5 | 3 | 1 | 7 | {6} | -{1.0} | {1.0.0.1} |
| 5 | 3 | 1 | 8 | {7} | -{1.0} | {1.0.0.1} |
| 5 | 3 | 1 | 9 | (8) | -{1.0} | {1.0.0.1} |
| 5 | 3 | 1 | 10 | {9} | -{1.0} | {1.0.0.1} |
| 5 | 4 | 1 | 2 | {1} | {1} | -{1.0} |
| 5 | 4 | 1 | 3 | {2} | {1} | -{1.0} |
| 5 | 4 | 1 | 4 | (3) | {1} | -{1.0} |
| 5 | 4 | 1 | 5 | {4} | {1} | -{1.0} |
| 5 | 4 | 1 | 6 | (5} | {1} | -{1.0} |
| 5 | 4 | 1 | 7 | {6) | {1} | -{1.0} |
| 5 | 4 | 1 | 8 | {1} | {1} | -{1.0} |
| 5 | 4 | 1 | 9 | {8} | {1} | -{1.0} |
| 5 | 4 | 1 | 10 | {9} | {1} | -{1.0} |
| 5 | 4 | 1 | 11 | {10} | {1} | -{1.0} |
| … | … | … | … | … | … | |
| 7 | 2 | 1 | 2 | {1} | 11} | -{1.0.1.0.1.0} |
| 7 | 2 | 1 | 3 | (2) | {1} | -{1.0.1.0.1.0} |
| 7 | 2 | 1 | 4 | {3} | {1} | -{1.0.1.0.1.0} |
| 7 | 2 | 1 | 5 | {4} | {1} | -{1.0.1.0.1.0} |
| 7 | 2 | 1 | 6 | {5} | {1} | -{1.0.1.0.1.0} |
| 7 | 2 | 1 | 7 | {6} | {1} | -{1.0.1.0.1.0} |
| 7 | 2 | 1 | 8 | (7) | (1) | -{1.0.1.0.1.0} |
| 7 | 2 | 1 | 9 | {8) | {1} | -{1.0.1.0, 1.0} |
| 7 | 2 | 1 | 10 | {9} | {1} | -{1.0.1.0.1.0} |
| 7 | 2 | 1 | 11 | {10} | {1} | -{1.0.1.0.1.0} |