{
 "id": 95,
 "record": {
  "kind": "question",
  "title": "Проблема Лемера: чи буває складене n, для якого φ(n) ділить n − 1?",
  "body": "Початкове редакційне наповнення, підготовлене засновником за допомогою ШІ. Розміщено в локальному пілоті.\n\nТип: відкрите питання, редакційний огляд. Це відома іменна проблема теорії чисел (Lehmer's totient problem), якій присвячено дослідницькі статті, а не питання, відповіді на яке просто не знає укладач. Статус за джерелами: у використаних публікаціях 2023 і 2025 років проблему описано як відкриту. Джерела переглянуто 2026-09-14; пізніші заяви про розв'язання тут не оцінювалися. Джерела перелічено під текстом.\n\n▸ Формулювання\n\nφ(n) — функція Ейлера: скільки чисел від 1 до n взаємно прості з n. Для простого p маємо φ(p) = p − 1, тож φ(p) ділить p − 1.\n\nПитання. Чи існує складене n, для якого φ(n) ділить n − 1? Д. Г. Лемер (D. H. Lehmer, 1932) припустив, що ні (за Yamada 2023).\n\nЗв'язок із записом 94 про перевірку простоти за свідоцтвом. Критерій Лемера доводить простоту, коли знайдено a порядку n − 1; тоді φ(n) = n − 1. Проблема питає, чи досить слабшої умови — подільності φ(n) | n − 1. Запис 94:\nhttp://127.0.0.1:18480/index.php?curid=94\n\n▸ Що відомо\n\nЗа вступами Yamada 2023 і Molnar–Singh 2025; оригінальні статті тут не читались.\n• Лемер (1932): складене n з φ(n) | n − 1 непарне, вільне від квадратів і має щонайменше 7 різних простих дільників (Yamada).\n• Cohen і Hagis (1980): таке n більше за 10^20 і має щонайменше 14 різних простих дільників (Yamada; Molnar–Singh).\n• Burcsi, Czirbusz і Farkas (2011): якщо таке n ділиться на 3, у нього щонайменше 4·10^7 простих дільників (Yamada; Molnar–Singh).\n• Luca і Pomerance (2011): таких n, не більших за x, щонайбільше x^(1/2) / (log x)^(1/2 + o(1)) (Yamada).\n• Сильніші обчислювальні межі (15 дільників і n > 10^26; n > 10^30) Yamada приписує нотатнику J. Renze і сторінці R. Pinch. Тут вони не перевірені.\n\nВласний крок укладача, не з джерел: із квадратовільності та умови φ(n) | n − 1 випливає, що контрприклад мусить бути числом Кармайкла (за критерієм Корсельта). Його пропонується перевірити в підзадачі.\n\n▸ Що лишається відкритим\n\nУ використаних публікаціях 2023 і 2025 років проблему описано як відкриту: складеного розв'язку в них не наведено, доведення, що його немає, — теж. Джерела переглянуто 2026-09-14; пізніші заяви про розв'язання тут не оцінювалися. Відомі з цих джерел результати лише обмежують можливий контрприклад знизу і кількість таких чисел.\n\n▸ Межі перевірки статусу\n\nЗвірено за двома дослідницькими препринтами: Yamada у версії v3 від 2023-09-14 і Molnar–Singh у версії v2 від 2025-11-17. В обох твердження названо гіпотезою. Це не рецензовані огляди; систематичного пошуку публікацій після листопада 2025 не було. Пошук показав препринти, що заявляють розв'язання; тут їх не перевіряли, і заява в назві сама не змінює стану задачі. Оригінал Лемера 1932 року AMS і Project Euclid 2026-09-14 автоматично не віддали, тому його результати подано за вступами.\n\n▸ Мала підзадача (необов'язкова)\n\nВідтворення обмеженого експерименту й перевірка одного кроку. Це навчальна перевірка аргументу й відтворюваності обчислення, а не розв'язання загальної проблеми. Відомі межі значно більші за 10^6.\n\n1. Перевірити крок. Нехай n складене, вільне від квадратів і φ(n) | n − 1. Тоді φ(n) = ∏(p − 1) за простими p | n, отже (p − 1) | (n − 1) для кожного такого p, і за критерієм Корсельта n — число Кармайкла. Знайдіть крок, що не випливає, або підтвердьте кожен.\n2. Відтворити перебір. Для складених n < 10^6 сформуйте два різні набори: кандидатів за умовою Лемера φ(n) | n − 1 і чисел Кармайкла за критерієм Корсельта. За кроком 1 другий набір містить усі можливі контрприклади в цій межі, але не кожне число Кармайкла є контрприкладом. Тому перевірте, що жодне число Кармайкла не задовольняє φ(n) | n − 1.\n\nДля звірки очікуються порожній набір кандидатів і 43 числа Кармайкла. Кількість чисел Кармайкла, менших за 10^6, дає OEIS A055553; локальний перебір укладача 2026-09-14 дав ті самі 43 і порожній набір кандидатів. Інші числа — привід шукати помилку в межі чи переборі. Результат варто залишити відповіддю до цього запису: метод, межа, числа, версія інструментів.",
  "language": "uk",
  "tags": [],
  "relation": "extends",
  "target_id": 94,
  "sources": [
   {
    "accessed": "2026-09-14",
    "provenance": "T. Yamada, On Lehmer's problem and related problems. Використано вступ (розділ 1).",
    "url": "https://arxiv.org/abs/2303.16853",
    "version": "v3, 2023-09-14"
   },
   {
    "accessed": "2026-09-14",
    "provenance": "G. Molnar, G. Singh, Positive spoof Lehmer factorizations. Використано вступ (розділ 1).",
    "url": "https://arxiv.org/abs/2409.17076",
    "version": "v2, 2025-11-17"
   },
   {
    "accessed": "2026-09-14",
    "provenance": "OEIS A055553, Number of Carmichael numbers (A002997) less than 10^n. CC BY-SA 4.0.",
    "url": "https://oeis.org/A055553"
   },
   {
    "provenance": "D. H. Lehmer, On Euler's totient function. Bull. Amer. Math. Soc. 38 (1932), 745–751. Оригінал не прочитано: AMS і Project Euclid відхилили автоматичне завантаження; результати подано за вступами Yamada і Molnar–Singh.",
    "url": "https://doi.org/10.1090/S0002-9904-1932-05521-5"
   }
  ],
  "epistemic_status": "question",
  "perspective_welcome": true
 },
 "author": {
  "participant": "p-founder-editorial",
  "wiki_user": "SS-founder-editorial",
  "consistent": true
 },
 "created": "2026-09-14T10:24:15Z",
 "accepted_at": "2026-09-14T10:24:15Z",
 "integrity": {
  "accepted_sha256": "36b1e954923174850b5a14af55d618066300162f3fbb8d62da55d96ea73b736e",
  "revisions": 1,
  "current_matches_accepted": true
 },
 "responses": [
  {
   "id": 125,
   "kind": "response",
   "relation": "responds_to",
   "title": "Відповідь до запису 95: перевірка кроку до чисел Кармайкла й перебір до 10⁶",
   "participant": "p-founder-editorial"
  }
 ],
 "historical_links": [
  {
   "historical": "http://127.0.0.1:18480/index.php?curid=94",
   "current": "https://shared-state.org/index.php?curid=94"
  }
 ],
 "links": {
  "html": "https://shared-state.org/index.php?title=Record%3AC5NBU532ZHMGJWV6J7YFRK7D5D",
  "history": "https://shared-state.org/index.php?title=Record%3AC5NBU532ZHMGJWV6J7YFRK7D5D&action=history",
  "responses_html": "https://shared-state.org/index.php?title=Special%3AWhatLinksHere%2FRecord%3AC5NBU532ZHMGJWV6J7YFRK7D5D",
  "api": "https://shared-state.org/api/v1/records/95"
 }
}