Ммалая теорема Ферма и числа Кармайкла

[Ascar]

Числа Кармайкла (и соответсвенно, все их сопутсвующие свойства) являются единственными исключениями при нахождении простых чисел с помощью критерия "малая теорема Ферма"???? или есть еще какието исключения???? Или этот вопрос остается открытым???

[VAL]

Ascar писал(а):

Числа Кармайкла (и соответсвенно, все их сопутсвующие свойства) являются единственными исключениями при нахождении простых чисел с помощью критерия "малая теорема Ферма"???? или есть еще какието исключения????

Других исключений нет. Числа Кармайкла ведь так и определяются.
Числом Кармайкла называется нечетное (а четные, бОльшие 2, вряд имеет смысл проверять на простоту) составное натуральное число m такое, что для каждого a, взаимно простого с m, выполняется сравнение $ a^{m-1} \equiv 1 (\mod m) $, т.е ведет неотличимо от простого по критерию Ферма.

[Батороев]

Нет, существуют и другие числа, не являющиеся числами Кармайкла, например:
$ 2^{340}\equiv 1\pmod {341} $

$ 2^{2700}\equiv 1 \pmod {2701} $
$ 3^{2700}\equiv 1 \pmod {2701} $
$ 4^{2700}\equiv 1 \pmod {2701} $
$ 6^{2700}\equiv 1 \pmod {2701} $
$ 8^{2700}\equiv 1 \pmod {2701} $

[ИСН]

Короче, некоторые числа заваливают тест по некоторым основаниям, а числа Кармайкла - по всем.

[Батороев]

ИСН писал(а):

Короче, некоторые числа заваливают тест по некоторым основаниям, а числа Кармайкла - по всем.

Почти по всем.

Число Кармайкла $ 561 = 3\cdot 7 \cdot 11 $

$ 3^{560}\equiv 375\pmod {561} $
$ 11^{560}\equiv 154\pmod {561} $
$ 21^{560}\equiv 375\pmod {561} $
$ 33^{560}\equiv 528\pmod {561} $

Короче, по всем - взаимнопростым.

[TOTAL]

Батороев писал(а):

ИСН писал(а):

Короче, некоторые числа заваливают тест по некоторым основаниям, а числа Кармайкла - по всем.

Почти по всем.

Число Кармайкла $ 561 = 3\cdot 7 \cdot 11 $

Что называете числами Кармайкла?

[Батороев]

По памяти:
Числа Кармайкла - это числа, вида:
$ N = p_1\pdot p_2\pdot p_3.. $, в которых
$ N-1 $ делится без остатка на любое $ p_i -1 $ ( $p$ - простые множители).

[Brukvalub]

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

По памяти:
Числа Кармайкла - это числа, вида:
$ N = p_1\pdot p_2\pdot p_3.. $, в которых
$ N-1 $ делится без остатка на любое $ p_i -1 $ ( $p$ - простые множители).

А разве любое из таких чисел будет числом Кармайкла?

[Батороев]

Да, вроде бы.
Что-то других характеристик чисел Кармайкла не припоминаю.

Вот нашел одну ссылку.

[Brukvalub]

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

Что-то других характеристик чисел Кармайкла не припоминаю.

Я не спрашивал о других характеристиках, я спрашивал, является ли указанное Вами свойство необходимым и достаточным, или только необходимым?

[Батороев]

Указанное свойство является необходимым и достаточным.
См. ссылку в предыдущем сообщении.
Тьфу! Забыл, что $ i>2 $.

[Brukvalub]

Спасибо.

[Батороев]

Вдруг, кого-то заинтересуют такие числа, то первые 11 чисел Кармайкла:
561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041.

[VAL]

Батороев писал(а):

Нет, существуют и другие числа, не являющиеся числами Кармайкла, например:
$ 2^{340}\equiv 1\pmod {341} $

Однако $ 5^{340}\equiv 67\pmod {341} $

Цитата:

$ 2^{2700}\equiv 1 \pmod {2701} $
$ 3^{2700}\equiv 1 \pmod {2701} $
$ 4^{2700}\equiv 1 \pmod {2701} $
$ 6^{2700}\equiv 1 \pmod {2701} $
$ 8^{2700}\equiv 1 \pmod {2701} $

Однако $ 5^{2700}\equiv 2554\pmod {2701} $

Поэтому приведенные Вами примеры никакие не исключения.
Ведь речь идет о НЕВОЗМОЖНОСТИ ОТЛИЧИТЬ число от простого с помощью критерия $ a^{m-1}\equiv 1 \pmod {m} $ при ЛЮБОМ a, взаимно простом с m, а не о ВОЗМОЖНОСТИ НЕ ОТЛИЧИТЬ при ПОДХОДЯЩЕМ a.
Если же рассуждать по Вашему, то все нечетные составные числа будут похожи на числа Кармайкла. А если допустить в качестве онования степени 1, то и вообще все

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

[Батороев]

VAL писал(а):

Однако $ 5^{2700}\equiv 2554\pmod {2701} $

Поэтому приведенные Вами примеры никакие не исключения.
Ведь речь идет о НЕВОЗМОЖНОСТИ ОТЛИЧИТЬ число от простого с помощью критерия $ a^{m-1}\equiv 1 \pmod {m} $ при ЛЮБОМ a, взаимно простом с m, а не о ВОЗМОЖНОСТИ НЕ ОТЛИЧИТЬ при ПОДХОДЯЩЕМ a.

Смотря, что называть ПОДХОДЯЩИМ a?
Чем мое ЛЮБОЕ число отличается от Вашего ЛЮБОГО? Они оба ПОДХОДЯЩИЕ, но только для разных оппонентов.

А если серьезно, то задача теста - ГАРАНТИРОВАННО отличить простое число от составного. При этом никому заранее не известно, какие числа $ a $ являются подходящими или не подходящими (т.е. не известно, взаимнопростое оно или нет с числом $N$).
Их принимают ЛЮБЫЕ, меньшие самого числа (за исключением $1$ и $ N-1 $).

По-моему, автора темы именно и интересовало, на каких числах, кроме чисел Кармайкла может еще ошибиться тест по МТФ?

Батороев писал(а):

Тьфу! Забыл, что $ i>2 $.

Я потому это требование в памяти не держу, потому что оно оч. прозрачно, т.е. $ i\ne 2 $.
Допустим, имеется составное число $ N = pq $, при этом простые $ p<q $.
Число $ N $ не может быть числом Кармайкла, т.к. нецелочисленно отношение:
$ \frac{N-1}{q-1} = \frac{pq-1}{q-1} = \frac{pq-p+p-1}{q-1} = \frac{p(q-1)}{q-1}+\frac{p-1}{q-1} = p + \frac{p-1}{q-1} $.