Книга: Математические головоломки профессора Стюарта
Назад: Промежутки между простыми числами
Дальше: 123456789 раз по X
Знак одного. Часть вторая 
Вот одно такое решение:
Объяснение см. в главе «Знак одного. Часть третья».
Евклидовы каракули
Вы могли бы сделать это вручную с использованием разложения на простые множители, если бы потратили на это день-другой. Вам пришлось бы выяснить, что
44 758 272 401 = 17 × 17 683 × 148 891;
13 164 197 765 = 5 × 17 683 × 148 891.
Затем вы могли бы сделать вывод, что НОД равен 17 683 × 148 891 = 2 632 839 553.
При использовании алгоритма Евклида весь расчет выглядит так:
(13 164 197 765; 44 758 272 401) → (13 164 197 765; 31 594 074 636) → (13 164 197 765; 18 429 876 871) → (5 265 679 106; 13 164 197 765) → (5 265 679 106; 7 898 518 659) → (2 632 839 553; 5 265 679 106) → (2 632 839 553; 2 632 839 553) → (0; 2 632 839 553).
Следовательно, НОД равен → 2 632 839 553.
Назад: Промежутки между простыми числами
Дальше: 123456789 раз по X
