Линейное представление наибольшего общего делителя (функция ExtendedGCD)
(Продолжение таблицы)
| n | m | d= НОД (n, m) | Основание системы счисления а | Цифры НОД в системе счисления с основанием а | Цифры r в системе счисления с основанием а | Цифры s в системе счисления с основанием а |
|---|---|---|---|---|---|---|
| … | … | … | … | … | … | |
| 8 | 5 | 1 | 2 | {1} | {1.0.0.1} | -{1.0.0.1.0.1.0} |
| 8 | 5 | 1 | 3 | (2). | {1.0.0.1} | -{1.0.0.1.0.1.0} |
| 8 | 5 | 1 | 4 | {3} | {1.0.0.1} | -{1.0.0.1.0.1.0} |
| 8 | 5 | 1 | 5 | {4} | {1.0.0.1} | -{1.0.0.1.0.1.0} |
| 8 | 5 | 1 | 6 | (5} | {1.0.0.1} | -{1.0.0.1.0.1.0} |
| 8 | 5 | 1 | 7 | {6} | {1.0.0.1} | -{1.0.0.1.0.1.0} |
| 8 | 5 | 1 | 8 | {7} | {1.0.0.1} | -{1.0.0.1.0.1.0} |
| 8 | 5 | 1 | 9 | {8} | {1.0.0.1} | -{1.0.0.1.0.1.0} |
| 8 | 5 | 1 | 10 | {9} | {1.0.0.1} | -{1.0.0.1.0.1.0} |
| 8 | 5 | 1 | 11 | {10} | {1.0.0.1} | -{1.0.0.1.0.1.0} |
| 8 | 5 | 1 | 12 | (11) | {1.0.0.1} | -{1.0.0.1.0.1.0} |
| 8 | 5 | 1 | 13 | {12} | {1.0.0.1} | -{1.0.0.1.0.1.0} |
| 8 | 5 | 1 | 14 | {13} | {1.0.0.1} | -{1.0.0.1.0.1.0} |
| 8 | 5 | 1 | 15 | {14} | {1.0.0.1} | -(1.0.0.1.0.1.0) |
| … | … | … | … | … | … | |
| 10 | 6 | 2 | 2 | (1.1) | -{1.0.0} | {1.0.0.0.0.0.1} |
| 10 | 6 | 2 | 3 | {2.2} | -{1.0.0} | {1.0.0.0.0.0.1} |
| 10 | 6 | 2 | 4 | {3.3} | -{1.0.0} | {1.0.0.0.0.0.1} |
| 10 | 6 | 2 | 5 | {4.4} | -{1.0.0} | {1.0.0.0.0.0.1} |
| 10 | 6 | 2 | 6 | {5.5} | -{1.0.0} | {1.0.0.0.0.0.1} |
| 10 | 6 | 2 | 7 | {6.6} | -{1.0.0} | {1.0.0.0.0.0.1} |
| id | 6 | 2 | 8 | (7.7) | -(1.0.0) | (1.0.0.0.0.0.1) |
| 10 | 6 | 2 | 9 | (8.8} | -(1.0.0) | (1.0.0.0.0.0.1) |
| 10 | 6 | 2 | 10 | (9.9) | -(1.0.0) | (1.0.0.0.0.0.1) |
| 10 | 6 | 2 | 11 | (10.10} | -(1.0.0) | (1.0.0.0.0.0.1) |
| 10 | 6 | 2 | 12 | (11.11} | -(1.0.0) | (1.0.0.0.0.0.1) |
| 10 | 6 | 2 | 13 | (12.12} | -(1.0.0) | (1.0.0.0.0.0.1) |
| 10 | 6 | 2 | 14 | (13.13} | -(1.0.0) | (1.0.0.0.0.0.1) |
| 10 | 6 | 2 | 15 | (14.14} | -(1.0.0) | (1.0.0.0.0.0.1) |
| 10 | 6 | 2 | 16 | (15.15} | -(1.0.0) | (1.0.0.0.0.0.1) |
| 10 | 6 | 2 | 17 | (16.16) | -(1.0.0) | (1.0.0.0.0.0.1) |
| 10 | 6 | 2 | 18 | (17.17) | -(1.0.0) | (1.0.0.0.0.0.1) |
| 10 | 7 | 1 | 2 | (1) | -(1.0.0.1.0) | (1.0.0.1.0.0.0.1) |
| 10 | 1 | 1 | 3 | (2} | -(1.0.0.1.0) | (1.0.0.1.0.0.0.1) |
| 10 | 1 | 1 | 4 | (3} | -(1.0.0.1.0) | (1.0.0.1.0.0.0.1) |
| 10 | 1 | 1 | 5 | (4} | -(1.0.0.1.0) | (1.0.0.1.0.0.0.1) |
| 10 | 1 | 1 | 6 | (5} | -(1.0.0.1.0) | {1.00, 1.0, 0.0.1} |
| 10 | 1 | 1 | 7 | (6} | -(1.0.0.1.0) | {1.0.10.1.0.0.0.1} |
| 10 | 1 | 1 | 8 | (7) | -(1.0.0.1.0) | {1.0,:0, 1.0, 0.0.1} |
| 10 | 7 | 1 | 9 | (8} | -(1.0.0.1.0) | {1.0.0.1.0.0.0.1} |
| 10 | 7 | 1 | 10 | (9) | -{1.0.0.1.0} | (1.0.0.1.0.0.0.1) |
| 10 | 7 | 1 | 11 | (10} | -(1.0.0.1.0} | (1.0.0.1.0.0.0.1) |
| 10 | 7 | 1 | 12 | (11) | -(1.0.0.1.0) | (1.0.0.1.0.0.0.1) |
| 10 | 7 | 1 | 13 | (12) | -(1.0.0.1.0} | (1.0.0.1.0.0.0.1) |
| 10 | 7 | 1 | 14 | (13) | -(1.0.0.1.0} | (1.0.0.1.0.0.0.1) |
| 10 | 7 | 1 | 15 | (14) | -(1, 0.0.1.0} | (1.0.0.1.0.0.0.1) |
| 10 | 7 | 1 | 16 | (15) | -{1, 0.0.1.0} | (1.0.0.1.0.0,-0.1) |
| 10 | 7 | 1 | 17 | (16) | -(1.0.0.1.0) | {1.0.0.1.0.0.0.1} |
| 10 | 7 | 1 | 18 | (17} | -(1.0.0.1.0) | (1.0.0.1.0.0.0.1} |
| 10 | 7 | 1 | 19 | (18} | -(1.0.0.1.0) | (1.0.0.1.0.0.0.1} |
| … | … | … | … | … |