2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Вопрос по теме "малая теорема Ферма"
Сообщение27.11.2008, 19:43 
Ascar писал(а):
Числа Кармайкла (и соответсвенно, все их сопутсвующие свойства) являются единственными исключениями при нахождении простых чисел с помощью критерия "малая теорема Ферма"???? или есть еще какието исключения????

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

 
 
 
 
Сообщение28.11.2008, 13:26 
Нет, существуют и другие числа, не являющиеся числами Кармайкла, например:
$ 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} $

 
 
 
 
Сообщение28.11.2008, 13:40 
Аватара пользователя
Короче, некоторые числа заваливают тест по некоторым основаниям, а числа Кармайкла - по всем.

 
 
 
 
Сообщение28.11.2008, 13:56 
ИСН писал(а):
Короче, некоторые числа заваливают тест по некоторым основаниям, а числа Кармайкла - по всем.

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

Число Кармайкла $ 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} $

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

 
 
 
 
Сообщение28.11.2008, 14:03 
Аватара пользователя
Батороев писал(а):
ИСН писал(а):
Короче, некоторые числа заваливают тест по некоторым основаниям, а числа Кармайкла - по всем.

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

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


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

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

 
 
 
 
Сообщение28.11.2008, 14:19 
Аватара пользователя
Батороев в сообщении #162867 писал(а):
По памяти:
Числа Кармайкла - это числа, вида:
$ N = p_1\pdot p_2\pdot p_3.. $, в которых
$ N-1 $ делится без остатка на любое $ p_i -1 $ ( $p$ - простые множители).
А разве любое из таких чисел будет числом Кармайкла?

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

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

 
 
 
 
Сообщение28.11.2008, 14:31 
Аватара пользователя
Батороев в сообщении #162872 писал(а):
Что-то других характеристик чисел Кармайкла не припоминаю.
Я не спрашивал о других характеристиках, я спрашивал, является ли указанное Вами свойство необходимым и достаточным, или только необходимым?

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

 
 
 
 
Сообщение28.11.2008, 14:53 
Аватара пользователя
Спасибо.

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

 
 
 
 
Сообщение28.11.2008, 19:10 
Батороев писал(а):
Нет, существуют и другие числа, не являющиеся числами Кармайкла, например:
$ 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 внесет ясность в этот вопрос.

 
 
 
 
Сообщение28.11.2008, 19:56 
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 $. :oops:

Я потому это требование в памяти не держу, потому что оно оч. прозрачно, т.е. $ 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} $.

 
 
 [ Сообщений: 15 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group