Числа Кармайкла.

[Imperator]

Найти все числа Кармайкла вида $3pq,$ где $p$ и $q$ - простые.

[maxal]

Число $3pq$ является числом Кармайкла тогда и только тогда, когда $p-1\mid 3q-1$ и $q-1\mid 3p-1$. Пусть $3<p<q.$
Тогда $p<q<3p.$ Откуда $3p-1=2(q-1)$ и, следовательно, $p=2k+1$ и $q=3k+2$ для некоторого целого $k.$
Так как $p-1=2k$ делит $3q-1=9k+5,$ то $k$ делит 5. Случай $k=1$ отпадает, остается $k=5,$ что дает $p=11$ и $q=17.$
Поэтому $3\cdot 11\cdot 17=561$ единственное число Кармайкла вида $3pq.$

[Sonic86]

Можно показать, что если $pqr$ - число Кармайкла и $p= const$, то таких чисел Кармайкла конечное число.

[Батороев]

Коль скоро, задача решена, а числа интересные, хочу задать один вопрос:
Можно ли составить выражение по ограничению величины наименьшего делителя числа Кармайкла в зависимости от величины самого числа, т.е. $ p_{min} \leq f(K) $, где $K $ - число Кармайкла?
На мой взгляд, проверяя числа на простоту по тестам, подобным тесту Миллера, мы тем самым достоверно можем определить простоту любого числа, кроме чисел Кармайкла.
Если это так, то для ОБЪЕКТИВНОЙ проверки необходимо проверить числа до $P_{min}$, что значительно меньше, чем $ \sqrt N $.

[ha]

Можно, но оно будет как минимум порядка $O(\sqrt[3]{N})$.

[Батороев]

Несколько лет назад я получил следующие выкладки:

Допустим, имеется число Кармайкла $ K = p_1p_2p_3 $, где $ p_1<p_2<p_3 $ - простые делители.
(Рассмотрим числа Кармайкла, имеющие только три простых делителя, т.к. при большем количестве делителей $ p_{min} $ будет меньше).
При этом $p_3-1\mid p_1p_2-1$.
Наибольший делитель $p_3$ возможен, если: $ \dfrac{p_1p_2-1}{p_3-1} = 2 $ (1)
При выполнении этого условия число $K$ должно быть треугольным:
$ K = \dfrac {(2p_3-1)2p_3}{2} $.
Тогда наименьший делитель не должен превосходить:
$ p_1\leqslant\sqrt{p_1p_2} = \sqrt{\dfrac {K}{p_3}} $

Или $ p_1\leqslant\sqrt{\dfrac{4K}{1+\sqrt{1+8K}} $ (что значительно меньше, чем $ \sqrt[3]{K} $).

Все было бы ничего и оценка по известным мне числам Кармайкла действует, но в выкладках есть один абсурдный момент, который я подчеркнул. Ведь при наибольшем возможном $ p_3 $ мы должны, вроде бы, получить наименьшее $ p_1p_2 $.
Может, специалисты по неравенствам помогут внести ясность?

[Sonic86]

Вряд ли момент был абсурден - он был необоснован, но он верный.
$\frac{p_1 p_2 - 1}{p_3-1} = \frac{K - p_3}{p_3 (p_3-1)}$ - убывающая функция аргумента, так что $p_3$ - максимально $\Leftrightarrow \frac{p_1 p_2 - 1}{p_3-1}$ - минимально для $K = const$

Или я не про то пишу?

[Батороев]

По-моему, Вы не поняли суть абсурда.

Попробую пояснить несколько по-другому.
Допустим, имеется число $ N = ab $, где нам известно, что $a>b$.
Мы можем записать неравенство: $ a>\sqrt {N}$.

Если нам дополнительно известно, что число $ a = cd $ - составное, где $ c>d $, то можно записать, что $ c>\sqrt a $ или $ c>\sqrt[4]{N} $.
Но про другое число записать $ d<\sqrt[4]{N} $ мы не можем.

Но я то шел примерно таким же путем ( $ p_1$ - аналог $d$, но с учетом свойств чисел Кармайкла) и получил неравенство для $p_1$, которое абсурдно по использованному пути, но не опровергнуто (быть может, пока?) каким-либо контр-примером.

[ha]

Число $K=(6n+1)(12n+1)(18n+1)$ является числом Кармайкла, если все сомножители - простые. Отсюда видно, что кубическую оценку не улучшить. Ваши рассуждения верны только при выполнении (1). Но вообще-то чем больше отношение, тем больше может быть наименьший простой делитель.

[Батороев]

Мою оценку можно немного загрубить и получим:
$ p_1 < \sqrt{\dfrac{4K}{1+\sqrt{1+8K}}} \approx\sqrt[4]{2K} $.
Первым из указанных Вами чисел Кармайкла является $ K = 7\cdot 13\cdot 19 = 1729 $.
Наименьший множитель $ 7 < \sqrt[4]{2\cdot 1729} $.

Я не хочу сказать, что моя оценка верная, но видно есть еще какой-то неувиденный нами квантор, который позволяет все же снизить Вашу оценку.

[ha]

Ау. Если таких чисел бесконечно много, то улучшить кубическую оценку нельзя. А я генерировал подобные числа с сотнями цифр.

[Батороев]

Ау-ау! Я и не терялся.
А Вы могли бы, ради интереса, проверить мою оценку на больших числах Кармайкла?

Кстати, как получена Ваша оценка?

[maxal]

Числом Деварая называется свободное от квадратов число $n=p_1 p_2\dots p_k$ (где $p_i$ - различные простые числа) такое, что $\varphi(n)=(p_1-1)(p_2-1)\dots(p_k-1)$ делит $\gcd(p_1-1,p_2-1,\dots,p_k-1)^2 (n-1)^{k-2}$.
Докажите, что каждое число Кармайкла является также числом Деварая.
Найдите наименьшее число Деварая, не являющееся числом Кармайкла.

Добавлено спустя 8 минут 55 секунд:

Батороев в сообщении #171466 писал(а):

На мой взгляд, проверяя числа на простоту по тестам, подобным тесту Миллера, мы тем самым достоверно можем определить простоту любого числа, кроме чисел Кармайкла.

Во-первых, тесты "подобные тесту Миллера" (правильнее говорить о тесте Миллера-Рабина) являются вероятностными, поэтом достоверно определить с помощью них простоту какого бы то ни было числа не получится. Во-вторых, числа Кармайкла для теста Миллера-Рабина не представляют никаких проблем. Вероятно, вы имели в виду тест Ферма, который всегда определяет числа Кармайкла как вероятно простые.

[Руст]

maxal писал(а):

Числом Деварая называется свободное от квадратов число $n=p_1 p_2\dots p_k$ (где $p_i$ - различные простые числа) такое, что $\varphi(n)=(p_1-1)(p_2-1)\dots(p_k-1)$ делит $\gcd(p_1-1,p_2-1,\dots,p_k-1)^2 (n-1)^{k-2}$.
Докажите, что каждое число Кармайкла является также числом Деварая.
Найдите наименьшее число Деварая, не являющееся числом Кармайкла.

Пусть n - число Кармайкла, q простой делитель $ord_q(\phi (n))=l$. Известно (и легко доказать), что число n свободно от квадратов. Пусть простые делители $p_i$ упорядочены, так, что
$ord_q(p_1-1)\le ord_q(p_2-1)\le...\le ord_q(p_k-1)$.
Если $ord_q(p_1-1)=ord_q(p_2-1)=0$, то очевидно
$ord_q(A)\ge (k-2)ord_q(p_k-1)\ge \sum_i ord_q(p_i-1)= l=ord_q(\phi (n))$,
где А число в определении числа Деваря.
Пусть $m=ord_q(p_3-1)$. Так как $q^m|n-1=(1+q^ma)p_1p_2-1=(1+q^ma)(1+q^rb)(1+q^sc)-1$ и $r\le s \ge 1$ получается, что если q>2, то $r=ord_q(p_1-1)=s=ord_q(p_2-1)=m$, следовательно
$ord_q(gcd(p_i-1))=m$ и $ord_q(A)\ge l$.
Если $q=2$ то и в этом случае получается $r=s,2^m|2^r(b+c)+2^{2r}bc$. Соответственно $ord_2(p_i-1)^2=2r$ и $ord_2(A)\ge l$.

[Батороев]

maxal писал(а):

Во-первых, тесты "подобные тесту Миллера" (правильнее говорить о тесте Миллера-Рабина) являются вероятностными, поэтом достоверно определить с помощью них простоту какого бы то ни было числа не получится. Во-вторых, числа Кармайкла для теста Миллера-Рабина не представляют никаких проблем. Вероятно, вы имели в виду тест Ферма, который всегда определяет числа Кармайкла как вероятно простые.

Вообще то я имел в виду, именно, детерминированный тест Миллера.
Т.е. зная оценку наименьшего делителя числа Кармайкла, проверить последовательно при помощи все числа $a$ до этой величины.
Тогда тест Миллера может приобрести статус ДОСТОВЕРНЫЙ.

Для обоих тестов - и Миллера, и Миллера-Рабина, как раз то числа Кармайкла и представляют главное препятствие, которое не позволяет им быть достоверными, а не вероятностными.

Никто не спорит, что на практике любое число Кармайкла достаточно быстро распознается указанными тестами, но никто не может и дать 100%-ной гарантии, что число, "выдержавшее" проверку тестом, является простым.

Особенно "неудобны" для проверки указанными тестами числа вида $ N = 4n+3 $, т.к. алгоритм проверки по указанным тестам ничем не отличается от теста Лемана: $ a^{\frac{N-1}{2}}\equiv\pm 1\pmod N $.