Dramtezi Calc

Теория чисел — калькуляторы и основные операции

НОД, расширенный Евклид, простота, φ(n), обратный и степень по модулю, китайская теорема об остатках, делители и сумма цифр. Калькуляторы делимости целых чисел.

Калькуляторы раздела

НОДКалькулятор находит наибольший общий делитель целых чисел. Для двух чисел работает алгоритм Евклида; для нескольких — НОД считается последовательно.НОККалькулятор считает наименьшее общее кратное целых чисел. Для пары используется связь НОК = |a·b| / НОД; для нескольких чисел кратное набирается по шагам.ФакториалФакториал n! — произведение всех натуральных чисел от 1 до n. По определению 0! = 1. Калькулятор считает только целые неотрицательные n.Проверка на простотуЧисло простое, если оно больше 1 и не делится ни на одно целое от 2 до √n. Калькулятор выдаёт 1 (простое) или 0 (составное, 0 или 1).Разложение на простыеКалькулятор раскладывает n ≥ 2 на простые с повторами: 12 = 2 · 2 · 3. Числовой ответ — сколько множителей с учётом кратности; само разложение — в шагах.Делители числаНатуральный делитель n делит n без остатка. Калькулятор считает, сколько их (функция τ), и перечисляет список в шагах. Для простых τ = 2: единица и само число.Взаимная простотаДва целых взаимно просты, когда их наибольший общий делитель равен 1. Калькулятор отвечает 1 или 0 и показывает НОД. 1 и n всегда взаимно просты.Целочисленное делениеЦелочисленное деление даёт неполное частное q из равенства a = b q + r с евклидовым остатком. Для 17 и 5 получите q = 3 (остаток 2 — в шагах).Функция Эйлераφ(n) — количество целых от 1 до n, взаимно простых с n. φ(1) = 1, для простого p значение p − 1. Калькулятор считает φ(n) по простым множителям.Обратный по модулюОбратный к a по модулю m — такое x, что a x даёт остаток 1 при делении на m. Он есть только если a и m взаимно просты. Калькулятор выдаёт x от 0 до m − 1.Возведение в степень по модулюСтепень по модулю — остаток от деления aᵉ на m. Калькулятор считает y = aᵉ mod m для целого e ≥ 0 и модуля m ≥ 2.Сумма цифрСумма цифр — сложение десятичных цифр числа n. Калькулятор считает одну сумму, без повторного сведения к одной цифре. Для нуля ответ 0.Следующее простоеСледующее простое — наименьшее простое p, строго большее n. Калькулятор не проверяет само n: для проверки откройте страницу простоты. n от 0 до 10⁷.Расширенный алгоритм ЕвклидаРасширенный алгоритм Евклида даёт НОД(a, b) и целые x, y, для которых a x + b y равно этому НОД. Калькулятор показывает все три числа.Китайская теорема об остаткахКитайская теорема об остатках ищет x, дающий заданные остатки по двум модулям. Калькулятор выдаёт x по модулю НОК(m₁, m₂). Если система несовместна, расчёт останавливается.

Теория чисел — калькуляторы делимости и целых

Раздел про целые: НОД, расширенный Евклид, НОК, факториал, простота, следующее простое, разложение, делители, взаимная простота, φ(n), целочисленное деление, сумма цифр, обратный по модулю, степень по модулю и китайская теорема об остатках. Рядом — остаток в арифметике. Родитель — математика.

Эти операции нужны, чтобы сокращать дроби, решать сравнения, проверять делимость и раскладывать n. Это не среднее и не алгебраическое уравнение в действительных числах.

Простые и множители

Проверка на простоту отвечает 1 или 0. Единица не простое, два — простое. Следующее простое идёт строго вперёд по прямой. Разложение пишет n = p₁ p₂ … с повторами.

Простое даёт один множитель — само себя. Составное 12 даёт 2·2·3. Не путайте число множителей с числом делителей и с φ(n).

Сравнения и модуль

Обратный ax ≡ 1 (mod m) существует при взаимной простоте. Степень по модулю считает aᵉ mod m без гигантского aᵉ. КТО собирает два сравнения в одно x.

Остаток одного деления — в арифметике. Коэффициенты Безу без модуля — расширенный Евклид.

Делители

Делители n перечисляют все натуральные d с нулевым остатком и считают τ(n). У 12 их шесть. У простого — два. Список в шагах, в поле ответа — количество.

НОД, Безу, взаимная простота

Наибольший общий делитель — калькулятор НОД. Если нужны x, y из ax + by = НОД, откройте расширенный алгоритм. Если НОД равен 1, числа взаимно простые: признак 1/0 и сколько таких k до n.

НОК для пары: |a·b| / НОД. Не путайте НОК с произведением: для 4 и 6 произведение 24, НОК равен 12.

Факториал и сумма цифр

n! = 1·2·…·n, и 0! = 1. Подробности: факториал. Сумма цифр складывает разряды один раз, без цифрового корня. Неполное частное q из a = bq + r.

Степени в действительных — в алгебре. Степень по модулю остаётся в этом хабе.

Вернуться к разделу Математика.

Частые вопросы

Что такое НОД?
Наибольший общий делитель — самое большое натуральное число, на которое делятся все заданные целые без остатка. Расширенный алгоритм ещё находит коэффициенты Безу.
Как связаны НОД и НОК?
Для двух чисел НОК(a, b) = |a·b| / НОД(a, b). Сокращать дробь удобно через НОД, общий знаменатель — через НОК.
Почему 1 не простое?
У единицы только один делитель. Простое должно иметь ровно два: 1 и само число. Двойка — простое. Следующее после 1 — тоже 2.
Что такое функция Эйлера?
φ(n) — сколько целых от 1 до n взаимно просты с n. Обратный по модулю существует как раз при взаимной простоте.
Где остаток от деления?
Неполное частное — в этом разделе. Остаток r — в арифметике. Степень по модулю и два сравнения — снова здесь.
Что такое 0! ?
По определению 0! = 1. Калькулятор факториала это учитывает.