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

Теория чисел

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

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

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}

Среднее арифметическое неравных чисел всегда меньше наибольшего из чисел и больше наименьшего.
Если все числа равны между собой, их среднее арифметическое принимает такое же значение.

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

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

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

Среднее геометрическое неравных чисел всегда меньше наибольшего из чисел и больше наименьшего.
Если все числа равны между собой, их среднее геометрическое принимает такое же значение.

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

\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

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

Рефлексивность:

a \equiv a \pmod m

Симметричность:

a \equiv b \pmod m \quad \Rightarrow \quad b \equiv a \pmod m

Транзитивность:

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$$ :

Представляем $$k$$ как $k = q \cdot (p-1) + r$ , где $0 \le r < p-1$ .
Тогда по теореме Ферма:

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

Остаток равен $n^r \mod p$ — вычислять проще, чем $$n^k$$ полностью.

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

Для числа $$p$$ выбираем несколько $$n$$ не кратных $$p$$ .
Считаем $n^{p-1} \mod p$:
- Если результат не 1, $$p$$ точно составное.
- Если результат = 1, $$p$$ может быть простым, но иногда срабатывает псевдопростое число.
Числа, которые дают 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$$ — даёт число, но не является точным кубом.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Цель

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

Пример

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

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

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

Пример

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

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

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

Алгоритм

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

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

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

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

Умножение

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

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

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

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

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

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

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

Суть теоремы

История

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

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

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