Математика: темы
Теория чисел
Формулы и правила по теме «Теория чисел».
17 формул
Таблица формул
| Формула | Запись | Тема | Для чего нужна |
|---|---|---|---|
| Признаки делимости на 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. |
| Быстрое возведение в степень по модулю двоичным методом | $a^n\bmod m,\qquad a^{2q}=(a^q)^2,\quad a^{2q+1}=a(a^q)^2$ | Арифметика и теория чисел | Двоичный метод вычисляет остаток большой степени, многократно возводя основание в квадрат и используя биты показателя. После каждого умножения можно брать остаток, не создавая огромного целого aⁿ. |
| Малая теорема Ферма: степени по простому модулю | $a^{p-1}\equiv1\pmod p,\quad p\text{ простое},\quad p\nmid a$ | Арифметика и теория чисел | Малая теорема Ферма утверждает, что ненулевой остаток по простому модулю в степени p−1 даёт единицу. Она помогает сокращать большие показатели, если основание не делится на этот простой модуль. |
| Теорема Эйлера: сокращение степени по составному модулю | $a^{\varphi(m)}\equiv1\pmod m,\qquad \gcd(a,m)=1,\quad m>1$ | Арифметика и теория чисел | Теорема Эйлера даёт единичный остаток для основания, взаимно простого с модулем, в степени φ(m). Она работает и с составным модулем, но не позволяет без проверки сокращать показатель любого основания. |
| Линейное сравнение: решения через НОД коэффициента и модуля | $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$ | Арифметика и теория чисел | Сравнение ax ≡ b по модулю m имеет решения тогда и только тогда, когда НОД(a,m) делит b. При выполнении условия получается ровно d разных классов по исходному модулю, где d — этот НОД. |
| Мультипликативный порядок: минимальный период степеней | $\operatorname{ord}_m(a)=\min\{k\ge1:a^k\equiv1\pmod m\},\qquad\operatorname{ord}_m(a)\mid\varphi(m)$ | Арифметика и теория чисел | Мультипликативный порядок обратимого остатка — наименьшая положительная степень, в которой он возвращается к единице. Этот период делит φ(m) и позволяет сокращать показатели точнее, чем одна теорема Эйлера. |