2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Ммалая теорема Ферма и числа Кармайкла
Сообщение27.11.2008, 17:49 


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

 Профиль  
                  
 
 Re: Вопрос по теме "малая теорема Ферма"
Сообщение27.11.2008, 19:43 
Заслуженный участник


27/06/08
4062
Волгоград
Ascar писал(а):
Числа Кармайкла (и соответсвенно, все их сопутсвующие свойства) являются единственными исключениями при нахождении простых чисел с помощью критерия "малая теорема Ферма"???? или есть еще какието исключения????

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

 Профиль  
                  
 
 
Сообщение28.11.2008, 13:26 


23/01/07
3497
Новосибирск
Нет, существуют и другие числа, не являющиеся числами Кармайкла, например:
$ 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 
Заслуженный участник
Аватара пользователя


18/05/06
13438
с Территории
Короче, некоторые числа заваливают тест по некоторым основаниям, а числа Кармайкла - по всем.

 Профиль  
                  
 
 
Сообщение28.11.2008, 13:56 


23/01/07
3497
Новосибирск
ИСН писал(а):
Короче, некоторые числа заваливают тест по некоторым основаниям, а числа Кармайкла - по всем.

Почти по всем. :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 
Заслуженный участник
Аватара пользователя


23/08/07
5495
Нов-ск
Батороев писал(а):
ИСН писал(а):
Короче, некоторые числа заваливают тест по некоторым основаниям, а числа Кармайкла - по всем.

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

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


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

 Профиль  
                  
 
 
Сообщение28.11.2008, 14:11 


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

 Профиль  
                  
 
 
Сообщение28.11.2008, 14:19 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение28.11.2008, 14:27 


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

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

 Профиль  
                  
 
 
Сообщение28.11.2008, 14:31 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва
Батороев в сообщении #162872 писал(а):
Что-то других характеристик чисел Кармайкла не припоминаю.
Я не спрашивал о других характеристиках, я спрашивал, является ли указанное Вами свойство необходимым и достаточным, или только необходимым?

 Профиль  
                  
 
 
Сообщение28.11.2008, 14:37 


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

 Профиль  
                  
 
 
Сообщение28.11.2008, 14:53 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва
Спасибо.

 Профиль  
                  
 
 
Сообщение28.11.2008, 15:23 


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

 Профиль  
                  
 
 
Сообщение28.11.2008, 19:10 
Заслуженный участник


27/06/08
4062
Волгоград
Батороев писал(а):
Нет, существуют и другие числа, не являющиеся числами Кармайкла, например:
$ 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 


23/01/07
3497
Новосибирск
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