2014 dxdy logo

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

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




 
 Сравнимость чисел по модулю
Сообщение05.02.2014, 10:17 
Аватара пользователя
Тут на днях, делая уроки, сын выдвинул следующее предположение:
$a^{2n-1}\equiv a \mod (2n-1)$
(число в нечетной степени сравнимо с самим числом по модулю этой степени)
Доказать или придумать контрпример мы с ним так и не смогли. Я было начал по индукции пробовать, да уж всё позабыл как это делается... :-)
Есть желающие доказать или контрпример найти?
(для четных степеней контрпример находится легко)

 
 
 
 Re: Сравнимость чисел по модулю
Сообщение05.02.2014, 10:21 
Аватара пользователя
$2^9\equiv 2 \mod 9$?

-- менее минуты назад --

С учётом малой теоремы Ферма, предположение эквивалентно такому: "Все нечётные числа просты".
Заметить его в такой форме было не так-то легко: для этого нужно любить числа и много с ними возиться. Это хорошее предположение, no kidding.
Но - неверное.

 
 
 
 Re: Сравнимость чисел по модулю
Сообщение05.02.2014, 10:38 
nnosipov в сообщении #821832 писал(а):
каковы те натуральные $n>1$, для которых имеет место сравнение $a^n \equiv a \pmod{n}$ для любого $a \in \mathbb{Z}$?. Ответ известен: это простые числа и числа Кармайкла (абсолютно псевдопростые числа).

 
 
 
 Re: Сравнимость чисел по модулю
Сообщение05.02.2014, 10:42 
Аватара пользователя
Спасибо. Да, действительно... :oops:

 
 
 
 Re: Сравнимость чисел по модулю
Сообщение05.02.2014, 13:50 
Аватара пользователя
Sonic86 в сообщении #822995 писал(а):
каковы те натуральные $n>1$, для которых имеет место сравнение $a^n \equiv a \pmod{n}$ для любого $a \in \mathbb{Z}$?. Ответ известен: это простые числа и числа Кармайкла (абсолютно псевдопростые числа).

А приводится ли где-то доказательство для простых чисел (ну в смысле, ссылка есть?)? Я так понимаю, что если доказательство и есть, то оно доказывает только достаточность, правильно? А все остальные, волшебным образом подходящие числа, просто назвали числами Кармайкла, да? :wink:
(а мы перебирали степени от 2 до 7 для разных чисел и подумали, что для нечетных выполняется, а оказывается просто на простые числа попадали... )

 
 
 
 Re: Сравнимость чисел по модулю
Сообщение05.02.2014, 13:57 
Аватара пользователя
https://ru.wikipedia.org/wiki/%D0%9C%D0 ... 0%BC%D0%B0

 
 
 
 Re: Сравнимость чисел по модулю
Сообщение05.02.2014, 14:10 
Аватара пользователя
Да, да, да... Я уже нашел, спасибо! Я чего-то не обратил внимания, что вы уже упомянули эту теорему в своем ответе. Вернее, обратил, но не связал ее почему-то с этим вопросом (а точнее, просто подумал про ВТФ почему-то...)

 
 
 
 Re: Сравнимость чисел по модулю
Сообщение05.02.2014, 21:05 
OlegCh в сообщении #823059 писал(а):
а мы перебирали степени от 2 до 7 для разных чисел и подумали, что для нечетных выполняется

"3 — простое, 5 — простое, 7 — простое, 9 — ошибка эксперимента, 11 — простое, 13 — простое. Следовательно, все нечетные числа — простые".

 
 
 
 Re: Сравнимость чисел по модулю
Сообщение06.02.2014, 10:40 
Аватара пользователя
Joker_vD в сообщении #823173 писал(а):
OlegCh в сообщении #823059 писал(а):
а мы перебирали степени от 2 до 7 для разных чисел и подумали, что для нечетных выполняется

"3 — простое, 5 — простое, 7 — простое, 9 — ошибка эксперимента, 11 — простое, 13 — простое. Следовательно, все нечетные числа — простые".

(Оффтоп)

Шутку оценил. Но, наверное, это простительно для семиклассника, который ничего не слышал о теореме Ферма и фактически получилось очень похоже...

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


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