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

Теория чисел

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

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) и позволяет сокращать показатели точнее, чем одна теорема Эйлера.