🔢 Теорія чисел
Шпаргалка: Теорія чисел
Подільність, НСД/НСК, прості числа, модульна арифметика та діофантові рівняння — повна довідка
Ознаки подільності
На 2
Остання цифра парна (0,2,4,6,8)
На 3
Сума цифр ділиться на 3
На 4
Число з останніх 2 цифр ділиться на 4
На 5
Остання цифра 0 або 5
На 6
Ділиться і на 2, і на 3
На 8
Число з останніх 3 цифр ділиться на 8
На 9
Сума цифр ділиться на 9
На 11
Знакозмінна сума цифр ділиться на 11
✦ Ознака на 11: (сума цифр на непарних позиціях) − (сума цифр на парних позиціях) кратна 11 (включно з 0)
НСД і НСК
Алгоритм Евкліда: gcd(a, b) = gcd(b, a mod b), поки b ≠ 0; gcd(a, 0) = a
НСК через НСД: lcm(a, b) = a · b / gcd(a, b)
| Крок | Приклад: gcd(48, 18) |
|---|
| 1 | gcd(48, 18) = gcd(18, 48 mod 18) = gcd(18, 12) |
| 2 | gcd(18, 12) = gcd(12, 18 mod 12) = gcd(12, 6) |
| 3 | gcd(12, 6) = gcd(6, 12 mod 6) = gcd(6, 0) = 6 |
| Результат | gcd(48, 18) = 6; lcm(48, 18) = 48·18/6 = 144 |
✦ Властивості: gcd(a,b)·lcm(a,b) = a·b; gcd(a,b) = gcd(a, b−a) = gcd(a, b+ka) для будь-якого цілого k
Прості числа
Означення: натуральне число p > 1, що має рівно два дільники — 1 і саме себе
Решето Ератосфена: викреслюємо з ряду чисел усі кратні кожного знайденого простого числа, починаючи з 2 — числа, що лишилися невикресленими, є простими
| Перші 20 простих чисел |
|---|
| 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71 |
✦ 1 не є ні простим, ні складеним числом. 2 — єдине парне просте число, усі інші прості числа непарні
Основна теорема арифметики
Кожне натуральне число n > 1 можна єдиним чином (з точністю до порядку множників) розкласти на добуток простих чисел: n = p₁^k₁ · p₂^k₂ · ... · pₘ^kₘ
✦ Приклад: 360 = 2³ · 3² · 5. Розклад єдиний — інакше розкласти 360 на прості множники неможливо
Модульна арифметика
Означення: a ≡ b (mod n) ⟺ n ділить (a − b) без остачі
| Властивість | Формула |
|---|
| Додавання | (a + b) mod n = ((a mod n) + (b mod n)) mod n |
| Віднімання | (a − b) mod n = ((a mod n) − (b mod n)) mod n |
| Множення | (a · b) mod n = ((a mod n) · (b mod n)) mod n |
| Піднесення до степеня | (aᵏ) mod n = ((a mod n)ᵏ) mod n |
| Мала теорема Ферма | якщо p — просте і gcd(a,p)=1, то a^(p−1) ≡ 1 (mod p) |
| Наслідок теореми Ферма | для будь-якого цілого a: aᵖ ≡ a (mod p) |
✦ Модульна арифметика — основа криптографії з відкритим ключем (RSA, Діффі-Геллан) та контрольних сум
Діофантові рівняння
Лінійне рівняння ax + by = c має цілочисельні розв'язки тоді й лише тоді, коли gcd(a,b) ділить c
Розширений алгоритм Евкліда знаходить x₀, y₀ такі, що a·x₀ + b·y₀ = gcd(a,b)
| Умова | Наслідок |
|---|
| gcd(a,b) | c | Рівняння має нескінченно багато цілих розв'язків |
| gcd(a,b) ∤ c | Цілих розв'язків немає |
| Загальний розв'язок | x = x₀ + (b/gcd)·t, y = y₀ − (a/gcd)·t, t ∈ ℤ |
✦ Приклад: 6x + 9y = 15 — розв'язки є, бо gcd(6,9)=3 і 3 ділить 15. Для 6x + 9y = 10 розв'язків немає, бо 3 не ділить 10
Як користуватися шпаргалкою
Ця шпаргалка зосереджує найважливіші формули, правила та визначення теорії чисел у компактному форматі для швидкого пошуку та підготовки до іспитів. Матеріал систематизований від ознак подільності до модульної арифметики та діофантових рівнянь.
Ефективне використання
Використовуйте шпаргалку поряд з розв'язуванням задач — не для списування, а як довідник формул. Спершу спробуйте пригадати формулу самостійно, потім звіртеся з довідником. Регулярне повторення формує стійку пам'ять.
Часті запитання (FAQ)
Що вивчає теорія чисел?
Теорія чисел — розділ математики, що досліджує властивості цілих чисел: подільність, прості числа та їх розподіл, НСД і НСК, конгруенції (модульну арифметику), діофантові рівняння та інші структури, пов'язані з цілими числами.
Як обчислити НСД і НСК двох чисел?
НСД (найбільший спільний дільник) обчислюється алгоритмом Евкліда: gcd(a,b) = gcd(b, a mod b), поки залишок не стане 0 — останнє ненульове значення і є НСД. НСК (найменше спільне кратне) знаходиться за формулою lcm(a,b) = a·b / gcd(a,b).
Чому розклад числа на прості множники єдиний?
Це стверджує основна теорема арифметики: кожне натуральне число більше 1 можна розкласти на прості множники, і цей розклад єдиний з точністю до порядку множників. Саме тому прості числа називають 'будівельними блоками' натуральних чисел.
Де застосовується модульна арифметика?
Модульна арифметика (арифметика за модулем) широко застосовується в криптографії (RSA, обмін ключами Діффі-Геллана), контрольних сумах, генераторах псевдовипадкових чисел, хешуванні та в задачах на подільність і залишки.
Що означає мала теорема Ферма?
Мала теорема Ферма стверджує: якщо p — просте число, а a — ціле число, не кратне p, то a^(p−1) ≡ 1 (mod p). Ця теорема лежить в основі багатьох тестів на простоту та криптографічних алгоритмів, зокрема RSA.