🔢 Теорія чисел: розв'язані задачі

П'ять класичних задач теорії чисел — від алгоритму Евкліда до функції Ейлера — з повним покроковим розв'язанням.

📚 5 задач 🎓 Рівень: університет ⏱ ~20 хвилин
Головна → Розв'язані задачі → Теорія чисел
Задача 1 із 5

НСД і НСК методом Евкліда: gcd(252, 105)

🔑 Алгоритм Евкліда
1
Алгоритм Евкліда: НСД(a, b) = НСД(b, a mod b). Ділимо більше на менше і беремо остаток.
НСД(252, 105) = НСД(105, 252 mod 105) = НСД(105, 42) = НСД(42, 105 mod 42) = НСД(42, 21) = НСД(21, 42 mod 21) = НСД(21, 0) = 21
2
НСК через НСД: НСК(a,b) = a·b / НСД(a,b)
НСК(252, 105) = 252 × 105 / 21 = 26460 / 21 = 1260
Відповідь
НСД = 21, НСК = 1260
Пам'ятка: Алгоритм Евкліда виконується за O(log min(a,b)) кроків — дуже ефективний навіть для великих чисел.
Задача 2 із 5

Решето Ератосфена: знайти всі прості числа до 50

♟ Просівання
1
Ідея: Починаємо з 2, закреслюємо всі кратні 2. Переходимо до наступного незакресленого — 3, закреслюємо кратні 3. Так до √50 ≈ 7.
Кроки: Крок 1 (p=2): 4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50 Крок 2 (p=3): 9,15,21,27,33,39,45 (6,12,18... вже закреслені) Крок 3 (p=5): 25,35 (10,15,20... вже закреслені) Крок 4 (p=7): 49 (14,21... вже закреслені) Залишилися: 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47
Всі прості числа ≤50
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 (15 чисел)
Складність: O(n·log(log n)) за часом, O(n) за пам'яттю. Для n ≤ 10⁷ — дуже швидко.
Задача 3 із 5

Мала теорема Ферма: знайти 3²⁸ mod 7

🔐 Модульна арифметика
1
Теорема Ферма: Якщо p — просте і gcd(a,p)=1, то a^(p-1) ≡ 1 (mod p).
p = 7, a = 3, gcd(3,7) = 1 ✓ 3^(7−1) = 3^6 ≡ 1 (mod 7)
2
Розкладаємо 28 через 6: 28 = 4·6 + 4, тому 3²⁸ = (3⁶)⁴ · 3⁴.
3^28 = (3^6)^4 · 3^4 ≡ 1^4 · 3^4 (mod 7) 3^1 = 3 3^2 = 9 ≡ 2 (mod 7) 3^4 = (3^2)^2 ≡ 2^2 = 4 (mod 7) 3^28 ≡ 1 · 4 = 4 (mod 7)
Відповідь
3²⁸ mod 7 = 4
Застосування: Мала теорема Ферма — основа RSA-шифрування і тестів простоти чисел.
Задача 4 із 5

Функція Ейлера φ(n): обчислити φ(36)

φ Мультиплікативність
1
Формула через канонічний розклад: φ(p₁^a₁·p₂^a₂...) = n·(1−1/p₁)·(1−1/p₂)…
2
Розкладаємо 36: 36 = 4·9 = 2² · 3²
φ(36) = 36 · (1 − 1/2) · (1 − 1/3) = 36 · (1/2) · (2/3) = 36 · 1/3 = 12
3
Перевірка: Числа від 1 до 36, взаємно прості з 36: 1,5,7,11,13,17,19,23,25,29,31,35 — рівно 12.
Відповідь
φ(36) = 12
Теорема Ейлера: a^φ(n) ≡ 1 (mod n) при gcd(a,n)=1 — узагальнення малої теореми Ферма на будь-яке n.
Задача 5 із 5

Китайська теорема про лишки: x ≡ 2 (mod 3), x ≡ 3 (mod 5)

🇨🇳 КТЛ
1
КТЛ: Оскільки gcd(3,5)=1, існує єдине рішення mod(3·5=15).
2
Множники: M₁ = 15/3 = 5, M₂ = 15/5 = 3. Знаходимо обернені: 5·y₁ ≡ 1 (mod 3) → y₁=2; 3·y₂ ≡ 1 (mod 5) → y₂=2.
x = a₁·M₁·y₁ + a₂·M₂·y₂ (mod M) = 2·5·2 + 3·3·2 (mod 15) = 20 + 18 (mod 15) = 38 mod 15 = 8
3
Перевірка: 8 mod 3 = 2 ✓; 8 mod 5 = 3 ✓
Відповідь
x ≡ 8 (mod 15)
Застосування КТЛ: RSA-шифрування, хеш-функції, планування розкладів. Теорема гарантує єдиність рішення коли модулі взаємно прості.
← Лінійна алгебра Математичний аналіз →

Методика розв'язання

Ця сторінка містить докладно розв'язані задачі з покроковими поясненнями. Мета — показати не лише відповідь, а сформувати розуміння методу, яке можна перенести на аналогічні задачі.

Як вчитися на прикладах

Перед переглядом розв'язку спробуйте вирішити задачу самостійно. Якщо застрягли — зверніться до першого кроку, потім знову спробуйте самі. Пояснюйте кожен крок уголос — це радикально покращує засвоєння.

Часті запитання (FAQ)

Які методи розв'язання задач з 🔢 теорія чисел демонструються на цій сторінці?
Сторінка демонструє стандартні та нестандартні методи розв'язання задач з '🔢 Теорія чисел': аналітичні підходи, числові методи та графічні інтерпретації. Кожен крок супроводжується поясненням логіки.
Якого рівня складності задачі з 🔢 теорія чисел представлені?
Представлені задачі охоплюють рівні: типові задачі з підручників (базовий), задачі підвищеної складності (середній) та нетипові варіанти (просунутий). Кожна задача чітко позначена за рівнем.
Як вчитися на розв'язаних задачах з 🔢 теорія чисел найефективніше?
Ефективна техніка: прочитайте умову → спробуйте розв'язати самостійно → порівняйте з розв'язком → якщо помилилися, проаналізуйте де саме → через 2–3 дні повторіть задачу без підказок. Це формує стійкі навички.
Чи є в розв'язках покрокові пояснення всіх перетворень?
Так, кожен розв'язок 🔢 теорія чисел містить детальні покрокові пояснення: записується перетворення, обґрунтовується його правомірність, вказуються використані теореми та формули. Підхід 'показати думку', а не лише відповідь.
Як ці задачі з 🔢 теорія чисел допомагають при підготовці до контрольних та іспитів?
Розв'язані задачі з '🔢 Теорія чисел' покривають типові варіанти університетських контрольних і іспитних завдань. Після їх опрацювання ви будете впізнавати тип задачі та одразу знати метод — це вирішальна перевага на іспиті.