Сравнимость чисел по модулю

[OlegCh]

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

[ИСН]

$2^9\equiv 2 \mod 9$?

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

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

[Sonic86]

nnosipov в сообщении #821832 писал(а):

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

[OlegCh]

Спасибо. Да, действительно...

[OlegCh]

Sonic86 в сообщении #822995 писал(а):

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

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

[ИСН]

https://ru.wikipedia.org/wiki/%D0%9C%D0 ... 0%BC%D0%B0

[OlegCh]

Да, да, да... Я уже нашел, спасибо! Я чего-то не обратил внимания, что вы уже упомянули эту теорему в своем ответе. Вернее, обратил, но не связал ее почему-то с этим вопросом (а точнее, просто подумал про ВТФ почему-то...)

[Joker_vD]

OlegCh в сообщении #823059 писал(а):

а мы перебирали степени от 2 до 7 для разных чисел и подумали, что для нечетных выполняется

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

[OlegCh]

Joker_vD в сообщении #823173 писал(а):

OlegCh в сообщении #823059 писал(а):

а мы перебирали степени от 2 до 7 для разных чисел и подумали, что для нечетных выполняется

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

(Оффтоп)

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