числа Кармайкла

[denver5s]

Нашел на форуме в одной из тем решение задачи о нахождении всех чисел Кармайкла вида n=3pq, где p,q - различные простые. Можно как-нибудь поподробнее и попонятнее объяснить ход решения?

[nnosipov]

denver5s, Вам нужно было писать в другой раздел. А указание такое: воспользоваться критерием кармайкловости (найдите его где-нибудь).

[maxal]

вероятно имеется в виду это решение - post44119.html#p44119
что конкретно непонятно?

[denver5s]

Непонятно с момента Откуда 3p-1 = 2(q-1) и далее до конца. Объясните, пожалуйста, попроще и попонятнее

[ИСН]

3p-1 делится нацело на q-1. Сколько оно при этом может давать, учитывая, что само q больше p? Три? Четыре? Стопицот?

[denver5s]

Ну хорошо, теперь понятно, почему 3p-1 = 2(q-1). Но тогда полагая p=2t+1, почему q должно быть равно 3t+2?

[ИСН]

А что, есть какие-то варианты? Подставили, получили.

[denver5s]

этот момент уяснил. дальше, p-1 = 2k делит 3q-1 = 9k-5. почему k должно делить 5?

[ИСН]

потому что запишите это утверждение формально, но в другом виде, без значка "делит". что увидим?

[denver5s]

если к должно делить 5, то 5 = kn. то есть если p-1 = 2k делит 3q-1 = 9k -5, то 9k-5 = 2km

[ИСН]

Ага. Теперь 5 в одну сторону, всё остальное в другую. Та часть делится на k - значит, и эта обязана.

[denver5s]

так ясно теперь, что k по-любому должно делить 5. ну теперь понятно, почему отпадает случай k=1. Спасибо большое, теперь все стало понятно