Математика: темы

Теория чисел

Формулы и правила по теме «Теория чисел».

12 формул

Таблица формул

Формула	Запись	Тема	Для чего нужна
Признаки делимости на 2, 5 и 10	$n\vdots2\Leftrightarrow a_0\in\{0,2,4,6,8\},\quad n\vdots5\Leftrightarrow a_0\in\{0,5\},\quad n\vdots10\Leftrightarrow a_0=0$	Арифметика и теория чисел	Признаки делимости на 2, 5 и 10 позволяют определить делимость натурального числа по последней цифре, не выполняя деление столбиком.
Признаки делимости на 3 и 9	$n\vdots3\Leftrightarrow S(n)\vdots3,\quad n\vdots9\Leftrightarrow S(n)\vdots9$	Арифметика и теория чисел	Число делится на 3 или 9 тогда и только тогда, когда сумма его цифр делится соответственно на 3 или 9, поэтому большое число можно проверить коротким сложением цифр.
Простые и составные числа	$p>1,\;D(p)=\{1,p\}$	Арифметика и теория чисел	Простое число имеет ровно два натуральных делителя: 1 и само число; составное число имеет больше двух натуральных делителей.
Разложение числа на простые множители	$n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_k^{\alpha_k}$	Арифметика и теория чисел	Разложение на простые множители представляет составное число как произведение простых чисел, часто с использованием степеней одинаковых множителей.
Наибольший общий делитель	$\gcd(a,b)=\prod p_i^{\min(\alpha_i,\beta_i)}$	Арифметика и теория чисел	Наибольший общий делитель двух чисел равен произведению общих простых множителей, взятых в меньших степенях, и показывает самую большую общую меру чисел.
Наименьшее общее кратное	$\operatorname{lcm}(a,b)=\prod p_i^{\max(\alpha_i,\beta_i)}$	Арифметика и теория чисел	Наименьшее общее кратное двух чисел равно произведению всех простых множителей из разложений, взятых в больших степенях.
Процентное изменение	$r=\frac{b-a}{a}\cdot100\%$	Арифметика и теория чисел	Процентное изменение показывает, на сколько процентов новая величина b отличается от исходной величины a. Знак результата показывает рост или уменьшение.
Функция Эйлера: произведение по простым делителям	$\varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right)$	Арифметика и теория чисел	Функция Эйлера φ(n) считает положительные целые числа от 1 до n, взаимно простые с n. Для вычисления достаточно знать различные простые делители n: каждый входит в произведение ровно один раз.
Число делителей по разложению на простые множители	$n=\prod_{i=1}^{r}p_i^{a_i},\qquad \tau(n)=\prod_{i=1}^{r}(a_i+1)$	Арифметика и теория чисел	Число положительных делителей n равно произведению увеличенных на единицу показателей в его простом разложении. Каждый делитель получается независимым выбором допустимой степени каждого простого множителя.
Сумма делителей по простому разложению числа	$n=\prod_{i=1}^{r}p_i^{a_i},\qquad \sigma(n)=\prod_{i=1}^{r}(1+p_i+\cdots+p_i^{a_i})$	Арифметика и теория чисел	Сумма положительных делителей n получается перемножением сумм степеней каждого простого множителя от нуля до его показателя. В сумму входят единица и само число; для собственных делителей затем вычитают n.
Обратный элемент по модулю через расширенный алгоритм Евклида	$au+mv=1\quad\Longrightarrow\quad a^{-1}\equiv u\pmod m$	Арифметика и теория чисел	Обратный к a по модулю m — это остаток, произведение которого с a даёт единицу по модулю m. Расширенный алгоритм Евклида находит его как коэффициент при a в целочисленном равенстве Безу.
Китайская теорема об остатках для двух взаимно простых модулей	$x\equiv r+m\bigl((s-r)m^{-1}\bmod n\bigr)\pmod{mn}$	Арифметика и теория чисел	Китайская теорема об остатках восстанавливает общий класс чисел по остаткам r и s при делении на взаимно простые m и n. Решение существует для любой пары остатков и единственно по модулю произведения mn.