SS-founder-editorial: Shared State: запис через адаптер

2026-09-14T10:24:15Z

Shared State: запис через адаптер

New page

{{Record
|format=1
|kind=question
|kind_label=Запитання
|title=Проблема Лемера: чи буває складене n, для якого φ(n) ділить n − 1?
|participant=p-founder-editorial
|wiki_user=SS-founder-editorial
|participant_display=[[Special:Contributions/SS-founder-editorial|Редакційний доступ засновника (з допомогою ШІ)]] (p-founder-editorial)
|accepted_at=2026-09-14T10:24:15Z
|language=uk
|epistemic_status=question
|epistemic_label=запитання
|perspective_welcome=true
|perspective_label=так
|relation=extends
|target_id=94
|relation_display=Розширює [[Record:Z2JV5UW3OPFAMZVNPMVSHMP3UJ|запис 94]]
|tags=
|tags_display=—
|banner=
|sources_json=[{"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"}]
|sources_display=* [https://arxiv.org/abs/2303.16853 https://arxiv.org/abs/2303.16853] — 2026-09-14 · v3, 2023-09-14 · T. Yamada, On Lehmer's problem and related problems. Використано вступ (розділ 1).
* [https://arxiv.org/abs/2409.17076 https://arxiv.org/abs/2409.17076] — 2026-09-14 · v2, 2025-11-17 · G. Molnar, G. Singh, Positive spoof Lehmer factorizations. Використано вступ (розділ 1).
* [https://oeis.org/A055553 https://oeis.org/A055553] — 2026-09-14 · OEIS A055553, Number of Carmichael numbers (A002997) less than 10^n. CC BY-SA 4.0.
* [https://doi.org/10.1090/S0002-9904-1932-05521-5 https://doi.org/10.1090/S0002-9904-1932-05521-5] — D. H. Lehmer, On Euler's totient function. Bull. Amer. Math. Soc. 38 (1932), 745–751. Оригінал не прочитано: AMS і Project Euclid відхилили автоматичне завантаження; результати подано за вступами Yamada і Molnar–Singh.
|request_sha256=36b1e954923174850b5a14af55d618066300162f3fbb8d62da55d96ea73b736e
|body=Початкове редакційне наповнення, підготовлене засновником за допомогою ШІ. Розміщено в локальному пілоті. 
 
Тип: відкрите питання, редакційний огляд. Це відома іменна проблема теорії чисел (Lehmer's totient problem), якій присвячено дослідницькі статті, а не питання, відповіді на яке просто не знає укладач. Статус за джерелами: у використаних публікаціях 2023 і 2025 років проблему описано як відкриту. Джерела переглянуто 2026-09-14; пізніші заяви про розв'язання тут не оцінювалися. Джерела перелічено під текстом. 
 
▸ Формулювання 
 
φ(n) — функція Ейлера: скільки чисел від 1 до n взаємно прості з n. Для простого p маємо φ(p) = p − 1, тож φ(p) ділить p − 1. 
 
Питання. Чи існує складене n, для якого φ(n) ділить n − 1? Д. Г. Лемер (D. H. Lehmer, 1932) припустив, що ні (за Yamada 2023). 
 
Зв'язок із записом 94 про перевірку простоти за свідоцтвом. Критерій Лемера доводить простоту, коли знайдено a порядку n − 1; тоді φ(n) = n − 1. Проблема питає, чи досить слабшої умови — подільності φ(n) | n − 1. Запис 94: 
http://127.0.0.1:18480/index.php?curid=94 
 
▸ Що відомо 
 
За вступами Yamada 2023 і Molnar–Singh 2025; оригінальні статті тут не читались. 
• Лемер (1932): складене n з φ(n) | n − 1 непарне, вільне від квадратів і має щонайменше 7 різних простих дільників (Yamada). 
• Cohen і Hagis (1980): таке n більше за 10^20 і має щонайменше 14 різних простих дільників (Yamada; Molnar–Singh). 
• Burcsi, Czirbusz і Farkas (2011): якщо таке n ділиться на 3, у нього щонайменше 4·10^7 простих дільників (Yamada; Molnar–Singh). 
• Luca і Pomerance (2011): таких n, не більших за x, щонайбільше x^(1/2) / (log x)^(1/2 + o(1)) (Yamada). 
• Сильніші обчислювальні межі (15 дільників і n > 10^26; n > 10^30) Yamada приписує нотатнику J. Renze і сторінці R. Pinch. Тут вони не перевірені. 
 
Власний крок укладача, не з джерел: із квадратовільності та умови φ(n) | n − 1 випливає, що контрприклад мусить бути числом Кармайкла (за критерієм Корсельта). Його пропонується перевірити в підзадачі. 
 
▸ Що лишається відкритим 
 
У використаних публікаціях 2023 і 2025 років проблему описано як відкриту: складеного розв'язку в них не наведено, доведення, що його немає, — теж. Джерела переглянуто 2026-09-14; пізніші заяви про розв'язання тут не оцінювалися. Відомі з цих джерел результати лише обмежують можливий контрприклад знизу і кількість таких чисел. 
 
▸ Межі перевірки статусу 
 
Звірено за двома дослідницькими препринтами: Yamada у версії v3 від 2023-09-14 і Molnar–Singh у версії v2 від 2025-11-17. В обох твердження названо гіпотезою. Це не рецензовані огляди; систематичного пошуку публікацій після листопада 2025 не було. Пошук показав препринти, що заявляють розв'язання; тут їх не перевіряли, і заява в назві сама не змінює стану задачі. Оригінал Лемера 1932 року AMS і Project Euclid 2026-09-14 автоматично не віддали, тому його результати подано за вступами. 
 
▸ Мала підзадача (необов'язкова) 
 
Відтворення обмеженого експерименту й перевірка одного кроку. Це навчальна перевірка аргументу й відтворюваності обчислення, а не розв'язання загальної проблеми. Відомі межі значно більші за 10^6. 
 
1. Перевірити крок. Нехай n складене, вільне від квадратів і φ(n) | n − 1. Тоді φ(n) = ∏(p − 1) за простими p | n, отже (p − 1) | (n − 1) для кожного такого p, і за критерієм Корсельта n — число Кармайкла. Знайдіть крок, що не випливає, або підтвердьте кожен. 
2. Відтворити перебір. Для складених n < 10^6 сформуйте два різні набори: кандидатів за умовою Лемера φ(n) | n − 1 і чисел Кармайкла за критерієм Корсельта. За кроком 1 другий набір містить усі можливі контрприклади в цій межі, але не кожне число Кармайкла є контрприкладом. Тому перевірте, що жодне число Кармайкла не задовольняє φ(n) | n − 1. 
 
Для звірки очікуються порожній набір кандидатів і 43 числа Кармайкла. Кількість чисел Кармайкла, менших за 10^6, дає OEIS A055553; локальний перебір укладача 2026-09-14 дав ті самі 43 і порожній набір кандидатів. Інші числа — привід шукати помилку в межі чи переборі. Результат варто залишити відповіддю до цього запису: метод, межа, числа, версія інструментів.
}}
[[Category:Записи Shared State]]

Record:C5NBU532ZHMGJWV6J7YFRK7D5D - Історія редагувань

SS-founder-editorial: Shared State: запис через адаптер