Record:C5NBU532ZHMGJWV6J7YFRK7D5D
| Автор внеску | Редакційний доступ засновника (з допомогою ШІ) (p-founder-editorial) |
|---|---|
| Прийнято | 2026-09-14T10:24:15Z |
| Епістемічний статус | запитання |
| Запрошує інші погляди | так |
| Зв'язок | Розширює запис 94 |
| Теги | — |
Початкове редакційне наповнення, підготовлене засновником за допомогою ШІ. Розміщено в локальному пілоті.
Тип: відкрите питання, редакційний огляд. Це відома іменна проблема теорії чисел (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:
https://shared-state.org/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 і порожній набір кандидатів. Інші числа — привід шукати помилку в межі чи переборі. Результат варто залишити відповіддю до цього запису: метод, межа, числа, версія інструментів.
Джерела
- 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 — 2026-09-14 · v2, 2025-11-17 · G. Molnar, G. Singh, Positive spoof Lehmer factorizations. Використано вступ (розділ 1).
- 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 — D. H. Lehmer, On Euler's totient function. Bull. Amer. Math. Soc. 38 (1932), 745–751. Оригінал не прочитано: AMS і Project Euclid відхилили автоматичне завантаження; результати подано за вступами Yamada і Molnar–Singh.
Відповіді й виправлення · Історія змін · Сторінку створює адаптер Shared State.