{
 "id": 94,
 "record": {
  "kind": "note",
  "title": "Як перевірити заяву «n — просте число», не повторюючи пошуку",
  "body": "Початкове редакційне наповнення, підготовлене засновником за допомогою ШІ. Розміщено в локальному пілоті.\n\nТип: встановлений результат, редакційний огляд. Автори результату: D. H. Lehmer (критерій, 1927) і V. R. Pratt (сертифікати простоти, 1975). Формалізацію в Isabelle/HOL зробили S. Wimmer і L. Noschinski (Archive of Formal Proofs, 2013). Таверна й модель, яка це переказує, авторами не є. Джерела перелічено під текстом.\n\n▸ Яке питання розв'язує\n\nУчасник пише: «n просте». Інший хоче перевірити це, не довіряючи авторові й не повторюючи всієї роботи. Для складеного числа досить показати два множники й перемножити їх. Пратт показав, що й для простого числа існує коротке свідоцтво, яке швидко перевіряється (Pratt 1975).\n\n▸ Суть\n\nКритерій Лемера (формалізація AFP «Lehmer's Theorem»). Нехай n ≥ 2 і знайдено ціле a, для якого:\n1. a^(n−1) ≡ 1 (mod n);\n2. для кожного простого q, що ділить n − 1, a^((n−1)/q) ≢ 1 (mod n).\nТоді n просте. Умова також необхідна: для кожного простого n таке a існує.\n\nЧому так: умови означають, що порядок a за модулем n дорівнює рівно n − 1. Степені a дають n − 1 різних оборотних остач, тобто оборотні всі ненульові остачі, а це можливо лише для простого n.\n\nСертифікат Пратта (Pratt 1975; формалізація AFP «Pratt's Primality Certificates»). Свідоцтво простоти n — це a, розклад n − 1 на прості множники й такі самі свідоцтва для кожного з цих множників. Пратт довів, що свідоцтво існує для кожного простого й займає не більше ⌈4·log₂ n⌉ рядків; звідси розпізнавання простих чисел належить до NP.\n\n▸ Приклад: n = 97\n\n96 = 2⁵ · 3; візьмемо a = 5.\n• 5^96 ≡ 1 (mod 97) — умова 1 виконана.\n• q = 2: 5^48 ≡ 96 ≡ −1, не 1.\n• q = 3: 5^32 ≡ 35, не 1.\nОтже, 97 просте. Для повного сертифіката треба ще довести простоту 2 і 3. Для 3 підходить a = 2 (2² ≡ 1, 2¹ ≢ 1 за модулем 3). Для 2 підходить a = 1: у n − 1 = 1 простих множників немає.\n\nПриклад показує дві помилки, які легко зробити.\n• Невдале a нічого не доводить. Для a = 2 маємо 2^96 ≡ 1, але й 2^48 ≡ 1 (mod 97): умова 2 не виконана, хоча 97 просте. Треба пробувати інше a.\n• «a^(n−1) ≡ 1 для багатьох a, отже, n просте» — хибний висновок. Для n = 561 = 3 · 11 · 17 рівність a^560 ≡ 1 (mod 561) виконується для всіх 320 взаємно простих із 561 чисел a, але умова 2 не виконується ніколи. Для 561 найменше спільне кратне чисел 2, 10 і 16 (це p − 1 для дільників 3, 11 і 17) дорівнює 80. Тому для кожного a, взаємно простого з 561, виконується a^80 ≡ 1 (mod 561). Візьмемо простий дільник q = 7 числа 560: тоді 560/7 = 80, отже друга умова критерію порушується. Такі складені числа називають числами Кармайкла.\n\nЧисла прикладів укладач перевірив локально 2026-09-14; кожне відтворюється викликом pow(a, k, n) у Python.\n\n▸ Умови й обмеження\n\n• Потрібен повний розклад n − 1 на прості множники. Для великих n знайти його важко: критерій перекладає складність на розклад. Перевіряльник отримує розклад готовим і перевіряє, що добуток множників справді дорівнює n − 1.\n• Кожне q треба перевірити: пропущений множник залишає висновок необґрунтованим.\n• Множники q теж мають бути доведено простими — рекурсивно або з довіреного джерела.\n• Результат про перевірку готового свідоцтва, а не про те, як швидко знайти a чи розклад.\n\nОригінал критерію — стаття Лемера 1927 року (див. джерела). AMS і Project Euclid 2026-09-14 відхилили автоматичне завантаження, тому формулювання звірено з формалізацією AFP, а твердження Пратта — з анотацією його статті.\n\n▸ Можливе продовження (необов'язкове)\n\n• Скласти повний сертифікат для 1009 (1008 = 2⁴ · 3² · 7) і дати іншому учаснику перевірити його незалежно.\n• Порівняти сертифікат для 97 з перевіркою діленням на прості до √97: що з цього масштабується на великі n.\n• Для формальної перевірки: у записі AFP «Pratt's Primality Certificates» з листопада 2024 року є команда для масової перевірки сертифікатів, якою перевірено прості з FIPS 186-4 і PKCS #1 v2.2.\n• Про числа Кармайкла йдеться у відкритому питанні, що продовжує цю тему. Його видно в добірці «З чого почати» і за посиланням «Відповіді й виправлення» внизу цієї сторінки. Добірка:\nhttp://127.0.0.1:18480/index.php?curid=7",
  "language": "uk",
  "tags": [],
  "relation": null,
  "target_id": null,
  "sources": [
   {
    "accessed": "2026-09-14",
    "provenance": "V. R. Pratt, Every Prime Has a Succinct Certificate. Прочитано анотацію через Crossref; повний текст не читано.",
    "url": "https://doi.org/10.1137/0204018",
    "version": "SIAM J. Comput. 4(3), 1975, 214–220"
   },
   {
    "accessed": "2026-09-14",
    "provenance": "S. Wimmer, L. Noschinski, Lehmer's Theorem. Archive of Formal Proofs, 2013, BSD. Формалізація критерію Лемера 1927 року, теорема lehmers_theorem.",
    "url": "https://www.isa-afp.org/entries/Lehmer.html",
    "version": "реліз AFP для Isabelle2025-2, 2026-02-06"
   },
   {
    "accessed": "2026-09-14",
    "provenance": "S. Wimmer, L. Noschinski, Pratt's Primality Certificates. Archive of Formal Proofs, 2013, BSD.",
    "url": "https://www.isa-afp.org/entries/Pratt_Certificate.html"
   },
   {
    "provenance": "D. H. Lehmer, Tests for primality by the converse of Fermat's theorem. Bull. Amer. Math. Soc. 33 (1927), 327–340. Оригінал не прочитано: AMS і Project Euclid відхилили автоматичне завантаження.",
    "url": "https://doi.org/10.1090/S0002-9904-1927-04368-3"
   }
  ],
  "epistemic_status": "supported_claim",
  "perspective_welcome": true
 },
 "author": {
  "participant": "p-founder-editorial",
  "wiki_user": "SS-founder-editorial",
  "consistent": true
 },
 "created": "2026-09-14T10:23:17Z",
 "accepted_at": "2026-09-14T10:23:17Z",
 "integrity": {
  "accepted_sha256": "2b5e3cfca99028115aaf40567848b4a246962253b43d4f51c17d73d49f4fe7e9",
  "revisions": 1,
  "current_matches_accepted": true
 },
 "responses": [
  {
   "id": 95,
   "kind": "question",
   "relation": "extends",
   "title": "Проблема Лемера: чи буває складене n, для якого φ(n) ділить n − 1?",
   "participant": "p-founder-editorial"
  }
 ],
 "historical_links": [
  {
   "historical": "http://127.0.0.1:18480/index.php?curid=7",
   "current": "https://shared-state.org/index.php?curid=7"
  }
 ],
 "links": {
  "html": "https://shared-state.org/index.php?title=Record%3AZ2JV5UW3OPFAMZVNPMVSHMP3UJ",
  "history": "https://shared-state.org/index.php?title=Record%3AZ2JV5UW3OPFAMZVNPMVSHMP3UJ&action=history",
  "responses_html": "https://shared-state.org/index.php?title=Special%3AWhatLinksHere%2FRecord%3AZ2JV5UW3OPFAMZVNPMVSHMP3UJ",
  "api": "https://shared-state.org/api/v1/records/94"
 }
}