Шпаргалки / Математика / Школа / Дискретная математика

Делимость и свойства делимости

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

| 2 | Число делится на 2 тогда и только тогда, когда его последняя цифра чётная. | | — | —————————————————————————————————————————————————————– | | 4 | Число делится на 4 тогда и только тогда, когда две его последние цифры составляют число, которое делится на 4 (также в конце числа могут быть два нуля). | | 5 | Число делится на 5 тогда и только тогда, когда оно оканчивается на 0 или на 5 | | 3 | Число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3. Более того, сумма цифр числа даёт такой же остаток от деления на 3, как и само число. | | 7 | Число делится на 7 тогда и только тогда, когда при вычитании удвоенной последней цифры из этого числа, взятого без последней цифры, результат делится на 7. | | 8 | Число делится на 8 тогда и только тогда, когда три его последние цифры составляют число, которое делится на 8 (также в конце числа могут быть три нуля). | | 9 | Число делится на 9 тогда и только тогда, когда сумма его цифр делится на 9. Более того, сумма цифр числа даёт такой же остаток от деления на 9, как и само число. | | 10 | Число делится на 10 тогда и только тогда, когда оно оканчивается цифрой нуль. | | 11 | Число делится на 11 тогда и только тогда, когда разность суммы цифр, стоящих в нечётных разрядах, и суммы цифр, стоящих в чётных разрядах, делится на 11. | | 25 | Число делится на 25 тогда и только тогда, когда последние две цифры образуют число, которое делится на 25. |

Свойства делимости

  • Если a делится на $b$, то для любого числа $k$ число $ka$ также делится на $b$.
  • Если a делится на $c$ и $b$ делится на c, то сумма, разность и произведение чисел $a$ и $b$ делятся на c. Если a делится на и $b$ делится на c, то a делится на $c$.
  • Если a делится на $c$ и $b$ делится на $d$, то $ab$ делится на $cd$.
  • Число $a$ делится на составное число $b$ тогда и только тогда, когда оно делится на все делители числа $b$.

Свойства чётных и нечётных чисел

  • Сумма двух или нескольких чётных чисел будет чётным числом.
  • Сумма двух нечётных чисел всегда будет чётным числом.
  • Сумма двух чисел разной четности будет являться нечётным числом.
  • Произведение любого натурального числа на чётное число всегда будет чётным числом.
  • Произведение двух или нескольких нечётных чисел всегда является нечётным числом.

Основная теорема арифметики

Каждое натуральное число $n > 1$ либо является простым, либо может быть разложено на простые множители:

\[ n=p_1^{a_1}\cdot p_2^{a_2}\cdot ... \cdot p_k^{a_k} \]

где:

  • $p_1,p_2,\dots,p_k$​ — простые числа,
  • $a_1,a_2,\dots,a_k$​ — положительные целые числа.

Это разложение единственно с точностью до порядка множителей.

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

Взаимно простые числа — это такие два числа, у которых нет общих делителей, кроме 1. То есть их наибольший общий делитель (НОД) равен 1.

Примеры:

  • 8 и 15 — взаимно простые, потому что делители 8 = ${1,2,4,8}$, делители 15 = ${1,3,5,15}$, общий только 1.
  • 12 и 18 — не взаимно простые, потому что у них общий делитель 6.

Делимость с остатками (частный случай Китайской теоремы об остатках)

Если число делится на два взаимно простых числа с равными ненулевыми остатками, то оно делится на произведение этих чисел с такими же остатками.

Примеры:

  • Пусть число $x$ при делении на 3 даёт остаток 2, а при делении на 5 даёт тоже остаток 2.
  • 3 и 5 взаимно простые → число $x$ даёт остаток 2 при делении на $3 \cdot 5 = 15$.
  • Пример: $17 \mod 3 = 2$, $17 \mod 5 = 2$, и $17 \mod 15 = 2$.

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

Простое число — натуральное число больше 1, которое делится только на 1 и на само себя.
Пример: $2, 3, 5, 7, 11, 13, \dots$

Составное число — натуральное число больше 1, которое имеет делители, кроме 1 и самого себя.
Пример: $4, 6, 8, 9, 10, 12, \dots$

Безопасное простое число

Определение: простое число $p$ называется безопасным, если

\[ p = 2q + 1 \]

где $q$ — тоже простое число.

Пример: $p=23$, $q=11$ → $23 = 2\cdot11 + 1$

Используется в криптографии, чтобы строить устойчивые ключи (например, DH, ElGamal).

Псевдопростое число (по Ферма)

Определение: составное число $n$, которое проходит тест Ферма для некоторого основания $a$ (то есть $a^{n-1} \equiv 1 \pmod n$), называется псевдопростым числом по основанию $a$.

Пример: $n=341$, $a=2$

\[ 2^{340} \equiv 1 \pmod{341}, \quad 341 = 11 \cdot 31 \]

Абсолютно псевдопростое число (число Кармайкла)

Определение: составное число $n$, которое проходит тест Ферма для любого числа $a$, взаимно простого с $n$.

Пример: $n=561$

\[ a^{560} \equiv 1 \pmod{561}, \quad \text{для всех } НОД(a,561)=1 \]

Прямое сравнение по модулю и простые числа

Если $p$ — простое число и $НОД(a,p)=1$, то по малой теореме Ферма:

\[ a^{p-1} \equiv 1 \pmod p \]

Используется для проверки простоты числа и вычисления остатков больших степеней.

Число Софи Жермен

Определение: простое число $p$, для которого

\[ 2p + 1 \text{ тоже простое} \]

Пример: $p=2,3,5$

  • $2\cdot2+1=5$
  • $2\cdot3+1=7$
  • $2\cdot5+1=11$

Запись числа в виде суммы разрядных слагаемых

Пусть многозначное число х записано цифрами $a_0,a_1,…,a_k$, то есть:

\[ x=\overline{a_ka_{k-1}...a_1a_0} \]

Десятичной записью натурального числа x называется его представление в виде суммы:

\[ x=a_k\cdot 10^k+a_{k-1}\cdot^{k-1}+...+a_1\cdot 10+a_0 \]

где $a_k\neq0$ и все числа $a_0,a_1,…a_k$ — целые, неотрицательные и не превосходящие 9.

Метод Горнера

Метод Горнера — это способ упростить вычисление многочлена и деление многочлена на (x - a).

Общая форма многочлена

Пусть есть многочлен:

\[ P(x) = a_nx^n + a_{n-1}x^{n-1} + \dots + a_1x + a_0 \]

Цель

Хотим найти значение $P(x_0)$ — подставить $x = x_0$.

Схема Горнера

Вводим промежуточные коэффициенты $b_i$:

\[ \begin{cases} b_n = a_n \\ b_i = a_i + x_0 \cdot b_{i+1}, \quad i = n-1, n-2, \dots, 0 \end{cases} \]

Тогда:

\[ P(x_0) = b_0 \]

Пример

Пусть:

\[ P(x) = 2x^3 - 6x^2 + 2x - 1 \]

и $x_0 = 3$

Составляем схему:

i aᵢ bᵢ = aᵢ + x₀·bᵢ₊₁
3 2 b₃ = 2
2 -6 b₂ = -6 + 3·2 = 0
1 2 b₁ = 2 + 3·0 = 2
0 -1 b₀ = -1 + 3·2 = 5
\[ P(3) = 5 \]

Среднее арифметическое

Среднее арифметическое нескольких чисел равно сумме этих чисел, делённой на их количество:

\[ \frac{a_1+a_2+...+a_n}{n} \]
  1. Среднее арифметическое неравных чисел всегда меньше наибольшего из чисел и больше наименьшего.
  2. Если все числа равны между собой, их среднее арифметическое принимает такое же значение.

Среднее геометрическое

Среднее геометрическое нескольких чисел — число, равное извлеченному корню из их произведения.

\[ \sqrt[n]{a_1\cdot a_2\cdot ... \cdot a_n} \]
  1. Среднее геометрическое неравных чисел всегда меньше наибольшего из чисел и больше наименьшего.
  2. Если все числа равны между собой, их среднее геометрическое принимает такое же значение.

Среднее арифметическое нескольких неотрицательных чисел не меньше их среднего геометрического:

\[ \frac{a_1+a_2+...+a_n}{n}\ge \sqrt[n]{a_1\cdot a_2\cdot ... \cdot a_n} \]

Равенство достигается тогда и только тогда, когда все числа равны.

\[ \frac{a_1+a_2}{2}\ge\sqrt{a_1\cdot a_2} \]

Для любых неотрицательных чисел и выполняется неравенство

Линейные диофантовы уравнения с двумя неизвестными

Линейным диофантовым уравнением с двумя неизвестными называют уравнение вида

\[ Ax + By = C \]

где $A,B,C$ — целые числа, а $x,y$ — целые неизвестные.

  • Решения существуют тогда и только тогда, когда $\gcd(A,B)\mid C$.
  • Если решений нет → конец. Если есть → их бесконечно много.

Общее решение:
Пусть $(x_0,y_0)$ — какое-то одно решение. Тогда все решения имеют вид

\[ x = x_0 + \tfrac{B}{d}t, \qquad y = y_0 - \tfrac{A}{d}t, \qquad t \in \mathbb{Z}, \]

где $d=\gcd(A,B)$.

Пример

\[ 6x + 9y = 30 \]
  • $\gcd(6,9)=3$, а $30$ делится на $3$ → решения есть.
  • Упрощаем: $2x+3y=10$.
  • Частное решение: $x=2,\; y=2$.
  • Общее решение:
\[ x = 2 + 3t, \quad y = 2 - 2t, \quad t \in \mathbb{Z}. \]

Наибольший общий делитель (НОД)

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

Алгоритм Евклида

  Шаги алгоритма Например, найдём $НОД(360;660)$
1 Разложить данные числа на простые множители. $360=2\cdot2\cdot2\cdot3\cdot3\cdot5,660=2\cdot2\cdot3\cdot5\cdot11$,. Запишем разложение данных чисел на простые множители в виде произведения степеней: $360=2^3\cdot3^2\cdot5^1,660=2^2\cdot3^1\cdot5^1\cdot11^1$.
2 Взять степени, основания которых являются общими простыми множителями. В данном примере это основания $2,3$ и $5$.
3 Из каждой пары степеней с одинаковым основанием выбрать степень с меньшим показателем. В данном примере это $2^2,3^1$ и $5^1$.
4 Перемножить выбранные степени; полученное произведение будет являться наибольшим общим делителем данной пары чисел. $НОД(360;660)=2^2\cdot3^1\cdot5^1=60$.

Наименьшее общее кратное (НОК)

Наименьшим общим кратным двух натуральных чисел называют такое наименьшее натуральное число, которое нацело делится на каждое из данных двух чисел.

Для любых двух натуральных чисел $a,b$ верно следующее равенство: $НОД(a;b)\cdotНОК(a;b)=ab$

Алгоритм

  Шаги алгоритма Например, найдём НОК
1 Разложить данные числа на простые множители. $\begin{align}120&=2\cdot2\cdot2\cdot3\cdot5=2^3\cdot3^1\cdot5^1\126&=2\cdot3\cdot3\cdot7=2^1\cdot3^2\cdot7^1\end{align}$
2 В обоих разложениях из каждой пары степеней с одинаковыми основаниями выбрать степень с наибольшим показателем. В нашем примере это $2^3$ и $3^2$
3 Выбрать степени, основания которых встречаются только в одном из разложений. В нашем примере это $5^1$ и $7^1$
4 Перемножить выбранные степени; полученное произведение будет являться наименьшим общим кратным данной пары чисел. $НОК(120;126)=2^3\cdot3^2\cdot5^1\cdot7^1=2520$

Сравнение по модулю

\[ a\equiv b\pmod m \]

Числа $a$ и $b$ называются сравнимыми по модулю $m$, если $a-b$ делится на $m$, то есть

\[ a-b = k \cdot m, \quad k \in \mathbb{Z} \]

Иными словами, $a$ сравнимо с $b$ по модулю $m$, если числа $a$ и $b$ имеют одинаковые остатки при делении на $m$.

Пример:

\[ 13\equiv 37 \pmod 6 \]

Простые свойства сравнений

  1. Рефлексивность:
\[ a \equiv a \pmod m \]
  1. Симметричность:
\[ a \equiv b \pmod m \quad \Rightarrow \quad b \equiv a \pmod m \]
  1. Транзитивность:
\[ a \equiv b \pmod m, \; b \equiv c \pmod m \quad \Rightarrow \quad a \equiv c \pmod m \]

Свойства сравнения, связанные с арифметическими действиями

Сложение и вычитание

Если $a \equiv b \pmod{m}$ и $c \equiv d \pmod{m}$, то:

\[ a + c \equiv b + d \pmod{m}, \quad a - c \equiv b - d \pmod{m} \]

Умножение

Если $a \equiv b \pmod{m}$ и $c \equiv d \pmod{m}$, то:

\[ a \cdot c \equiv b \cdot d \pmod{m} \]

Возведение в степень

Если $a \equiv b \pmod{m}$, то для любого целого $k \ge 0$:

\[ a^k \equiv b^k \pmod{m} \]

Теорема Ферма (малая)

Если $p$ — простое число и $n$ не делится на $p$, то:

\[ n^{p-1} \equiv 1 \pmod{p} \]

Теорема про сумму цифр

Число и его сумма цифр имеют одинаковые остатки при делении на 9.
Если $S(n)$ — сумма цифр числа $n$, то:

\[ n \equiv S(n) \pmod{9} \]

Малая теорема Ферма

Пусть $p$  — простое число, тогда для любого натурального $n$, не кратного $p$, разность $n^{p-1}$ делится на $p$.

$n^{p-1}\equiv1 \pmod p$Малая теорема Ферма помогает быстро находить остатки от деления на простые числа, особенно для больших степеней.

Применение для поиска остатков

Чтобы найти остаток от деления $n^k$ на простое $p$:

  1. Представляем $k$ как $k = q \cdot (p-1) + r$, где $0 \le r < p-1$.
  2. Тогда по теореме Ферма:
\[ n^k = n^{q(p-1)+r} = (n^{p-1})^q \cdot n^r \equiv 1^q \cdot n^r \equiv n^r \pmod p \]
  1. Остаток равен $n^r \mod p$ — вычислять проще, чем $n^k$ полностью.

Проверка на простоту и псевдопростые числа

  1. Для числа $p$ выбираем несколько $n$ не кратных $p$.
  2. Считаем $n^{p-1} \mod p$:
    • Если результат не 1, $p$ точно составное.
    • Если результат = 1, $p$ может быть простым, но иногда срабатывает псевдопростое число.
  3. Числа, которые дают 1 при таком проверочном $n$, но на самом деле составные, называются псевдопростыми числами Ферма.

Великая теорема Ферма

Суть теоремы

Формулировка (простыми словами):

Уравнение
$x^n + y^n = z^n$ не имеет ненулевых целых решений при $n > 2$.

То есть нельзя найти такие целые числа $x, y, z$,
чтобы кубы, четвёртые степени и т.д. складывались,
давая точную степень того же порядка.

Например:

  • Для $n=2$ работает: $3^2 + 4^2 = 5^2$ (это теорема Пифагора).
  • Но для $n=3,4,5,…$ — не работает вообще никогда.

История

  • Пьер Ферма (1607–1665) написал на полях книги Диофанта,
    что у него есть «поистине чудесное доказательство»,
    но «поля книги слишком узкие, чтобы его здесь поместить».
  • Это утверждение стало знаменитым и получило название
    «Великая теорема Ферма».
  • Более 350 лет никто не смог доказать её полностью.

    Доказательство

  • Доказана в 1994 году (опубликована в 1995).
  • Автор — Эндрю Уайлс, британский математик.
  • Использовал современные методы:
    • эллиптические кривые,
    • модульные формы,
    • теорему о модулярности.
  • Доказательство огромное, очень сложное,
    занимает десятки страниц продвинутой математики.

Коротко по сути

Что Содержание
Формула $x^n + y^n = z^n$
Условия $x, y, z, n$ — целые числа, $x, y, z \neq 0$, $n>2$
Утверждение Нет решений
Автор Пьер Ферма
Год идеи около 1637
Год доказательства 1994 (Эндрю Уайлс)
Тип доказательства через эллиптические кривые и модульные формы

Пример для понимания

  • $3^2 + 4^2 = 5^2$ работает (для $n=2$)
  • $3^3 + 4^3 = 5^3$ не работает (не работает)
  • $9^3 + 10^3 = 1729$ — даёт число, но не является точным кубом.