2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Гвоздь в попытки обратить малую теорему Ферма вбит уже давно
Сообщение13.01.2006, 09:48 
Заслуженный участник
Аватара пользователя


21/12/05
5903
Новосибирск
Найдите m, разложимое в произведение трёх простых чисел, для которого справедливо утвержение:
$a^m - a \equiv 0 \ (mod \  m)$ для любого a.
ЗЫ. Не сомневаюсь, что это давно известно, поэтому прошу воздержаться от ссылок. Задачка не очень сложная.

 Профиль  
                  
 
 
Сообщение13.01.2006, 11:03 
Модератор
Аватара пользователя


11/01/06
5660
Если отказаться от ограничения на число простых делителей, то получатся в точности числа Кармайкла. Ссылок не даю :)

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


12/10/05
478
Казань
Я слышал, что известных чисел Кармайкла очень мало - немного больше 20 штук...

 Профиль  
                  
 
 
Сообщение13.01.2006, 11:27 
Модератор
Аватара пользователя


11/01/06
5660
Нет, их очень много известно. Более того, недавно доказали, что их существует бесконечно много.

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


12/10/05
478
Казань
Да??? :shock: Я это прочитал в учебнике, по-моему "алгоритмы и структуры данных", в том месте где речь идет об алгоритмах разложения числа на множители... Дома уточню и попробую процитировать... Хотя ничто не стоит на месте, возможно те данные уже устарели..

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


21/12/05
5903
Новосибирск
Sanyok писал(а):
Дома уточню и попробую процитировать...

Но-но, ну дайте порешать-то народу! :D

 Профиль  
                  
 
 
Сообщение13.01.2006, 12:02 
Модератор
Аватара пользователя


11/01/06
5660
Бесконечность их числа доказана аж в 1994 году в статье:
Alford, Granville and Pomerance (1994). There are infinitely many Carmichael numbers, Ann. of Math. 140(3), 703–722.

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


12/10/05
478
Казань
Вот, в инете нашел:
Цитата:
Особо плохими для теста Ферма являются так называемые числа Кармайкла. Они обладают следующим свойством: для любого a такого, что (a, n) = 1 верно
$ a^{n -1} = 1 (mod$ n)
Первые три числа Кармайкла таковы: ..... Среди первых 100000000 чисел их всего 255. Лишь недавно (1994 г.) было доказано, что таких чисел бесконечно много.

Так что похоже, не так уж их и много (я имею в виду, на них случайно сложно напороться)... Сами числа умышленно убрал - пусть народ решает! :lol: Я как-то написал программку для генерации простых чисел в диапазоне 1..N (алгоритм - решето Эратосфена), так их вообще море оказалось! Кстати, какое бы N я не брал, количество простых чисел получалось примерно 1/10 от N.

 Профиль  
                  
 
 
Сообщение13.01.2006, 13:31 
Модератор
Аватара пользователя


11/01/06
5660
Sanyok писал(а):
Так что похоже, не так уж их и много (я имею в виду, на них случайно сложно напороться)...

Для всех достаточно больших n, количество чисел Кармайкла не превосходящих n больше чем $n^{2/7}$.
Sanyok писал(а):
Кстати, какое бы N я не брал, количество простых чисел получалось примерно 1/10 от N.

Простых чисел не превосходящих N примерно равно $\frac{N}{\ln N}$.

 Профиль  
                  
 
 Исходная задача
Сообщение16.01.2006, 03:57 


10/08/05
54
Не совсем ясно что автор имел ввиду. Найди хотя бы одно такое число или описать все.
Последнее сомнительно, т.к. существет пример из 10200 цифр найденный Dubner (ссылки не привожу)

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


21/12/05
5903
Новосибирск
Нет, про описание не заикался - просто рассматривал как тренировочную задачу для студентов. А также при необходимости, можно было бы очередному глобалисту-фундаменталисту дать простую ссылку.
А некоторые из последних может быть даже посмотрят на название и откажутся. В это, правда, слабо верится - не переводятся же триссектристы с квадратурщиками и удвоителями куба.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group