Любая сложная задача всегда может быть разбита на несколько простых задач. Те в свою очередь могут быть разбиты на ещё1 более мелкие задачи. В олимпиадных задачах по программированию очень часто требуется найти НОД(наибольший общий делитель) или НОК(наименьшее общее кратное) двух или более чисел. Это может быть задача по фасовке предметам по ящикам (целочисленное деление) или формирование людей в бригады. Короче там где нужно искать целые числа после деления. Пример двух чисел 6 и 15. Очевидно, что НОД (наибольшим общим делителем) будет число 3...

В теории чисел, криптографии и других областях науки часто возникает задача отыскания решений сравнения первой степени вида ах = Ь(тодт). Решение такого сравнения начинается с вычисления NOD(a, т) = = с1. При этом возможны два случая: • если b не кратно d, то у сравнения нет решений; • если b кратно d, то у сравнения существует единственное решение по модулю т / d или, что то же самое, d решений по модулю т. В этом случае в результате сокращения исходного сравнения на d получается сравнение а{х = ^(mod/Wj), где al = a/d,b^=b/dnml = m/ dявляются целыми числами, причем ах и /77[ взаимно просты...