Математика

Арифметика и теория чисел

Делимость, простые числа, НОД, НОК, дроби, остатки и числовые закономерности.

14 формул

Формулы темы

Признаки делимости на 2, 5 и 10

Признаки делимости на 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$

Признаки делимости на 3 и 9

Число делится на 3 или 9 тогда и только тогда, когда сумма его цифр делится соответственно на 3 или 9, поэтому большое число можно проверить коротким сложением цифр.

$n\vdots3\Leftrightarrow S(n)\vdots3,\quad n\vdots9\Leftrightarrow S(n)\vdots9$

Простые и составные числа

Простое число имеет ровно два натуральных делителя: 1 и само число; составное число имеет больше двух натуральных делителей.

$p>1,\;D(p)=\{1,p\}$

Разложение числа на простые множители

Разложение на простые множители представляет составное число как произведение простых чисел, часто с использованием степеней одинаковых множителей.

$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)}$

Процент от числа в задачах 7 класса

Процент от числа показывает, какая часть величины соответствует p сотым долям. Формула переводит проценты в дробь и умножает эту дробь на исходное число.

$p\%\text{ от }a=\frac{p}{100}\cdot a$

Число по его проценту

Число по его проценту находят, когда известна часть b и известно, что эта часть составляет p% от целого. Формула восстанавливает исходное целое делением на долю.

$a=\frac{b\cdot100}{p}$

Процентное изменение

Процентное изменение показывает, на сколько процентов новая величина b отличается от исходной величины a. Знак результата показывает рост или уменьшение.

$r=\frac{b-a}{a}\cdot100\%$

Функция Эйлера: произведение по простым делителям

Функция Эйлера φ(n) считает положительные целые числа от 1 до n, взаимно простые с n. Для вычисления достаточно знать различные простые делители n: каждый входит в произведение ровно один раз.

$\varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right)$

Число делителей по разложению на простые множители

Число положительных делителей n равно произведению увеличенных на единицу показателей в его простом разложении. Каждый делитель получается независимым выбором допустимой степени каждого простого множителя.

$n=\prod_{i=1}^{r}p_i^{a_i},\qquad \tau(n)=\prod_{i=1}^{r}(a_i+1)$

Сумма делителей по простому разложению числа

Сумма положительных делителей n получается перемножением сумм степеней каждого простого множителя от нуля до его показателя. В сумму входят единица и само число; для собственных делителей затем вычитают 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})$

Обратный элемент по модулю через расширенный алгоритм Евклида

Обратный к a по модулю m — это остаток, произведение которого с a даёт единицу по модулю m. Расширенный алгоритм Евклида находит его как коэффициент при a в целочисленном равенстве Безу.

$au+mv=1\quad\Longrightarrow\quad a^{-1}\equiv u\pmod m$

Китайская теорема об остатках для двух взаимно простых модулей

Китайская теорема об остатках восстанавливает общий класс чисел по остаткам r и s при делении на взаимно простые m и n. Решение существует для любой пары остатков и единственно по модулю произведения mn.

$x\equiv r+m\bigl((s-r)m^{-1}\bmod n\bigr)\pmod{mn}$