Признаки делимости на 2, 5 и 10
Признаки делимости на 2, 5 и 10 позволяют определить делимость натурального числа по последней цифре, не выполняя деление столбиком.
Математика
Делимость, остатки, НОД/НОК, сравнения и теоретико-числовые методы.
27 формул
Признаки делимости на 2, 5 и 10 позволяют определить делимость натурального числа по последней цифре, не выполняя деление столбиком.
Число делится на 3 или 9 тогда и только тогда, когда сумма его цифр делится соответственно на 3 или 9, поэтому большое число можно проверить коротким сложением цифр.
Простое число имеет ровно два натуральных делителя: 1 и само число; составное число имеет больше двух натуральных делителей.
Разложение на простые множители представляет составное число как произведение простых чисел, часто с использованием степеней одинаковых множителей.
Наибольший общий делитель двух чисел равен произведению общих простых множителей, взятых в меньших степенях, и показывает самую большую общую меру чисел.
Наименьшее общее кратное двух чисел равно произведению всех простых множителей из разложений, взятых в больших степенях.
Процент от числа показывает, какая часть величины соответствует p сотым долям. Формула переводит проценты в дробь и умножает эту дробь на исходное число.
Число по его проценту находят, когда известна часть b и известно, что эта часть составляет p% от целого. Формула восстанавливает исходное целое делением на долю.
Процентное изменение показывает, на сколько процентов новая величина b отличается от исходной величины a. Знак результата показывает рост или уменьшение.
Функция Эйлера φ(n) считает положительные целые числа от 1 до n, взаимно простые с n. Для вычисления достаточно знать различные простые делители n: каждый входит в произведение ровно один раз.
Число положительных делителей n равно произведению увеличенных на единицу показателей в его простом разложении. Каждый делитель получается независимым выбором допустимой степени каждого простого множителя.
Сумма положительных делителей n получается перемножением сумм степеней каждого простого множителя от нуля до его показателя. В сумму входят единица и само число; для собственных делителей затем вычитают n.
Обратный к a по модулю m — это остаток, произведение которого с a даёт единицу по модулю m. Расширенный алгоритм Евклида находит его как коэффициент при a в целочисленном равенстве Безу.
Китайская теорема об остатках восстанавливает общий класс чисел по остаткам r и s при делении на взаимно простые m и n. Решение существует для любой пары остатков и единственно по модулю произведения mn.
Двоичный метод вычисляет остаток большой степени, многократно возводя основание в квадрат и используя биты показателя. После каждого умножения можно брать остаток, не создавая огромного целого aⁿ.
Малая теорема Ферма утверждает, что ненулевой остаток по простому модулю в степени p−1 даёт единицу. Она помогает сокращать большие показатели, если основание не делится на этот простой модуль.
Теорема Эйлера даёт единичный остаток для основания, взаимно простого с модулем, в степени φ(m). Она работает и с составным модулем, но не позволяет без проверки сокращать показатель любого основания.
Сравнение ax ≡ b по модулю m имеет решения тогда и только тогда, когда НОД(a,m) делит b. При выполнении условия получается ровно d разных классов по исходному модулю, где d — этот НОД.
Мультипликативный порядок обратимого остатка — наименьшая положительная степень, в которой он возвращается к единице. Этот период делит φ(m) и позволяет сокращать показатели точнее, чем одна теорема Эйлера.
Чтобы узнать, имеет ли сравнение x² ≡ a решение по нечётному простому модулю p, достаточно вычислить степень a^((p−1)/2) по модулю p и прочитать её остаток.
Закон квадратичной взаимности связывает два символа Лежандра при перестановке нечётных простых чисел. Знак меняется, только если оба числа дают остаток 3 при делении на 4.
Символ Якоби перемножает символы Лежандра по простым множителям нечётного модуля. Значение −1 исключает квадрат, а значение 1 по составному модулю ещё требует проверки.
Лемма Гензеля позволяет уточнить корень сравнения от модуля pᵏ до pᵏ⁺¹. Если производная обратима по модулю p, нужная поправка определяется одним линейным сравнением.
Целое число p>1 простое тогда и только тогда, когда (p−1)! ≡ −1 (mod p). Для простого p каждый множитель 1,…,p−1 имеет обратный по модулю p, и почти все пары взаимно сокращаются; остаются только 1 и p−1.
Бинарный алгоритм Евклида, или алгоритм Стейна, находит наибольший общий делитель двух целых чисел с помощью чётности, деления пополам и вычитания. Он заменяет дорогие остатки последовательностью простых операций над битами.
Метод Полларда rho ищет нетривиальный делитель составного числа, строя псевдослучайную последовательность по модулю n и вычисляя НОД разностей состояний с n. Совпадение по неизвестному простому множителю обнаруживает делитель раньше полного перебора.
Алгоритм baby-step giant-step находит x из a^x ≡ b (mod p), если a имеет подходящий конечный порядок. Он разбивает показатель на блоки размера m≈√n, сохраняет малые шаги и сопоставляет их с крупными шагами обратной степени.