Математика

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

Делимость, остатки, НОД/НОК, сравнения и теоретико-числовые методы.

Как выбрать подходящий материал

  1. Делимость, остатки, НОД/НОК, сравнения и теоретико-числовые методы.
  2. Разность двух чисел начальной школы не относится сюда по слову «число».

27 формул

Формулы темы

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

Быстрое возведение в степень по модулю двоичным методом

Двоичный метод вычисляет остаток большой степени, многократно возводя основание в квадрат и используя биты показателя. После каждого умножения можно брать остаток, не создавая огромного целого aⁿ.

$a^n\bmod m,\qquad a^{2q}=(a^q)^2,\quad a^{2q+1}=a(a^q)^2$

Малая теорема Ферма: степени по простому модулю

Малая теорема Ферма утверждает, что ненулевой остаток по простому модулю в степени p−1 даёт единицу. Она помогает сокращать большие показатели, если основание не делится на этот простой модуль.

$a^{p-1}\equiv1\pmod p,\quad p\text{ простое},\quad p\nmid a$

Теорема Эйлера: сокращение степени по составному модулю

Теорема Эйлера даёт единичный остаток для основания, взаимно простого с модулем, в степени φ(m). Она работает и с составным модулем, но не позволяет без проверки сокращать показатель любого основания.

$a^{\varphi(m)}\equiv1\pmod m,\qquad \gcd(a,m)=1,\quad m>1$

Линейное сравнение: решения через НОД коэффициента и модуля

Сравнение ax ≡ b по модулю m имеет решения тогда и только тогда, когда НОД(a,m) делит b. При выполнении условия получается ровно d разных классов по исходному модулю, где d — этот НОД.

$ax\equiv b\pmod m\text{ разрешимо}\iff d\mid b,\quad d=\gcd(a,m);\quad x=x_0+k\frac md,\ k=0,\ldots,d-1$

Мультипликативный порядок: минимальный период степеней

Мультипликативный порядок обратимого остатка — наименьшая положительная степень, в которой он возвращается к единице. Этот период делит φ(m) и позволяет сокращать показатели точнее, чем одна теорема Эйлера.

$\operatorname{ord}_m(a)=\min\{k\ge1:a^k\equiv1\pmod m\},\qquad\operatorname{ord}_m(a)\mid\varphi(m)$

Критерий Эйлера для квадратичных вычетов

Чтобы узнать, имеет ли сравнение x² ≡ a решение по нечётному простому модулю p, достаточно вычислить степень a^((p−1)/2) по модулю p и прочитать её остаток.

$\left(\frac ap\right)\equiv a^{(p-1)/2}\pmod p,\qquad \left(\frac ap\right)\in\{-1,0,1\}$

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

Закон квадратичной взаимности связывает два символа Лежандра при перестановке нечётных простых чисел. Знак меняется, только если оба числа дают остаток 3 при делении на 4.

$\left(\frac pq\right)\left(\frac qp\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}}$

Символ Якоби по нечётному составному модулю

Символ Якоби перемножает символы Лежандра по простым множителям нечётного модуля. Значение −1 исключает квадрат, а значение 1 по составному модулю ещё требует проверки.

$n=\prod_{j=1}^r p_j^{e_j},\qquad \left(\frac an\right)=\prod_{j=1}^r\left(\frac{a}{p_j}\right)^{e_j}$

Лемма Гензеля: подъём простого корня по степеням p

Лемма Гензеля позволяет уточнить корень сравнения от модуля pᵏ до pᵏ⁺¹. Если производная обратима по модулю p, нужная поправка определяется одним линейным сравнением.

$r_{k+1}=r_k+t p^k,\qquad t\equiv-\frac{f(r_k)}{p^k}\bigl(f\prime(r_k)\bigr)^{-1}\pmod p$

Теорема Вильсона: факториал по простому модулю

Целое число p>1 простое тогда и только тогда, когда (p−1)! ≡ −1 (mod p). Для простого p каждый множитель 1,…,p−1 имеет обратный по модулю p, и почти все пары взаимно сокращаются; остаются только 1 и p−1.

$p\text{ простое}\iff(p-1)!\equiv-1\pmod p$

Бинарный алгоритм Евклида: НОД через деление пополам

Бинарный алгоритм Евклида, или алгоритм Стейна, находит наибольший общий делитель двух целых чисел с помощью чётности, деления пополам и вычитания. Он заменяет дорогие остатки последовательностью простых операций над битами.

$\gcd(a,b)=2^s\gcd(u,v),\quad a=2^s u,\ b=2^s v,\quad u,v\text{ не оба чётные}$

Метод Полларда rho: вероятностный поиск делителя

Метод Полларда rho ищет нетривиальный делитель составного числа, строя псевдослучайную последовательность по модулю n и вычисляя НОД разностей состояний с n. Совпадение по неизвестному простому множителю обнаруживает делитель раньше полного перебора.

$x_{i+1}=x_i^2+c\pmod n,\quad y_{i+1}=f(f(y_i)),\quad d_i=\gcd(|x_i-y_i|,n)$

Алгоритм baby-step giant-step для дискретного логарифма

Алгоритм baby-step giant-step находит x из a^x ≡ b (mod p), если a имеет подходящий конечный порядок. Он разбивает показатель на блоки размера m≈√n, сохраняет малые шаги и сопоставляет их с крупными шагами обратной степени.

$x=im+j,\quad a^j=b\,a^{-im}\pmod p,\quad m=\lceil\sqrt n\rceil$