Линейное представление наибольшего общего делителя (функция ExtendedGCD)
(Продолжение таблицы)
| n | m | d= НОД (n, m) | Основание системы счисления а | Цифры НОД в системе счисления с основанием а | Цифры r в системе счисления с основанием а | Цифры s в системе счисления с основанием а |
|---|---|---|---|---|---|---|
| 4 | 1 | 1 | 2 | (1} | {0} | {1} |
| 4 | 1 | 1 | 3 | {2} | {0} | {1} |
| 4 | 1 | 1 | 4 | (3) | {0} | {1} |
| 4 | 1 | 1 | 5 | (4) | {0} | {1} |
| 4 | 1 | 1 | 6 | {5} | (0) | {1} |
| 4 | 1 | 1 | 7 | {6} | {0} | {1} |
| 4 | 2 | 2 | 2 | {1.1} | {0} | {1} |
| 4 | 2 | 2 | 3 | (2.2) | {0} | {1} |
| 4 | 2 | 2 | 4 | (3.3) | {0} | {1} |
| 4 | 2 | 2 | 5 | {4.4} | {0} | {1} |
| 4 | 2 | 2 | 6 | {5.5} | {0} | {1} |
| 4 | 2 | 2 | 7 | {6.6} | {0} | {1} |
| 4 | 2 | 2 | 8 | (7.7} | {0} | {1} |
| 4 | 3 | 1 | 2 | {1} | {1} | -{1.0.} |
| 4 | 3 | 1 | 3 | {2} | {1} | -{1.0} |
| 4 | 3 | 1 | 4 | {3} | {1} | -{1.0} |
| 4 | 3 | 1 | 5 | {4} | {1} | -{1.0} |
| 4 | 3 | 1 | 6 | {5} | {1} | -{1.0} |
| 4 | 3 | 1 | 7 | {6} | {1} | -{1.0} |
| 4 | 3 | 1 | 8 | {7} | {1} | -{1.0} |
| 4 | 3 | 1 | 9 | (8) | (1) | -{1.0} |
| .. | … | … | … | … | ||
| 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} |
| … | … | … | … | … | … |