Евклидовы каракули

Вы могли бы сделать это вручную с использованием разложения на простые множители, если бы потратили на это день-другой. Вам пришлось бы выяснить, что

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.