Делимость: основа теории чисел
«Делится ли 123 456 789 на 9?» Можно разделить в столбик — займёт минуту. Или применить признак: сложить цифры: 1+2+3+4+5+6+7+8+9 = 45; 4+5 = 9. Делится. Признаки делимости — элегантные инструменты, позволяющие проверить делимость без деления. Они — часть теории делимости, фундамента арифметики и теории чисел.
Делимость: целое число a делится на b (b | a), если существует целое число k такое, что a = b·k.
Признаки делимости
- На 2: последняя цифра чётная (0, 2, 4, 6, 8)
- На 4: последние две цифры образуют число, делящееся на 4
- На 8: последние три цифры образуют число, делящееся на 8
- На 5: последняя цифра 0 или 5
- На 10: последняя цифра 0
- На 3: сумма цифр делится на 3
- На 9: сумма цифр делится на 9
- На 11: разность суммы цифр на чётных и нечётных позициях делится на 11. Пример: 14 641: (1+6+1) - (4+4) = 8 - 8 = 0, делится на 11
- На 7, 13, 17...: нет простых признаков; используют алгоритмы
Алгоритм Евклида: НОД за O(log n) шагов
НОД (наибольший общий делитель) a и b — наибольшее число, делящее оба. Алгоритм Евклида (≈ 300 г. до н.э.) — один из древнейших алгоритмов: НОД(a, b) = НОД(b, a mod b), пока b ≠ 0; тогда НОД = a.
Пример: НОД(252, 105): 252 = 2·105 + 42; НОД(105, 42): 105 = 2·42 + 21; НОД(42, 21): 42 = 2·21 + 0; Ответ: НОД = 21. Алгоритм исключительно эффективен: число шагов — O(log min(a,b)).
Расширенный алгоритм Евклида дополнительно находит коэффициенты x, y (теорема Безу): ax + by = НОД(a,b). Незаменим в криптографии RSA.
НОК: наименьшее общее кратное
НОК(a, b) — наименьшее положительное число, делящееся и на a, и на b. Связь с НОД: НОК(a, b) = a·b / НОД(a, b). Применение: нахождение общего знаменателя при сложении дробей, синхронизация периодических процессов.
Основная теорема арифметики: единственность разложения
Каждое натуральное число n ≥ 2 единственным образом (с точностью до порядка) представляется в виде произведения простых чисел: n = p₁^a₁ · p₂^a₂ · ... · pₖ^aₖ. Это называется основным разложением (prime factorization). Пример: 360 = 2³ · 3² · 5. Через разложения легко вычислить НОД и НОК: НОД берёт минимальные степени общих простых, НОК — максимальные.
Криптографическое значение
Разложить произведение двух больших простых чисел на множители вычислительно трудно (задача факторизации). На этой асимметрии (умножить легко — разложить трудно) основана криптосистема RSA. Безопасность RSA-2048 обеспечивается тем, что разложение числа в ~617 цифр — задача, непосильная для любого существующего классического компьютера. Квантовый алгоритм Шора теоретически решает задачу факторизации за полиномиальное время — это угроза для RSA.