Показатель элемента ord

[Stasya7]

Как быстро считать $ord_m (a)$? Понятно, что $ord_m (a)$ - это делитель $\varphi (m)$. Но не перебором же делать?
Даже скажу, что меня смущает: надо найти $ord_{241}(3)$. По идее, $\varphi (241) = 240$, и надо перебирать все делители $240$, пока не найдётся минимальное число такое, что $3^q = 1(mod 241) $. Но на лекции сказали, что достаточно проверить только $q=48, 80, 120$? Почему? Как я поняла, $\varphi(241)=240=2^4 * 3*5$, а $48=240:5$ $120=240:2$ $80=240:3$

[Brukvalub]

Речь идет о порядке элемента в мультипликативной группе кольца вычетов?

[Stasya7]

Brukvalub в сообщении #1159824 писал(а):

Речь идет о порядке элемента в мультипликативной группе кольца вычетов?

Да

[Brukvalub]

Есть множество частных случаев, в которых появляются дополнительные соображения, упрощающие поиск порядка элемента, но общего, универсального не переборного алгоритма, видимо, нет.

[Stasya7]

Brukvalub в сообщении #1159840 писал(а):

Есть множество частных случаев, в которых появляются дополнительные соображения, упрощающие поиск порядка элемента, но общего, универсального не переборного алгоритма, видимо, нет.

А почему в этом примере достаточно перебрать только из делителей $48, 80, 120 $?

[Brukvalub]

По теореме Лагранжа, но не только по этой теореме, нужны еще простые доп. соображения.

[Stasya7]

Brukvalub в сообщении #1159875 писал(а):

По теореме Лагранжа, но не только по этой теореме, нужны еще простые доп. соображения.

Кажется, сама уже поняла