Решить сравнение

[Mary84]

Добрый день.

Помогите , пожалуйста, разобраться с небольшой задачей.
Нужно найти все натуральные x, удовлетворяющие сравнению $ 4^{x}\equiv 1(\mod 77)$

По теореме Эйлера $ 4^{ \varphi (77) }\equiv 1 ( \mod 77) $

$ \varphi (77)= \varphi (7) \varphi (11)=(7-1)(11-1)=60 $

Не знаю, что дальше надо делать.

[Sonic86]

Ну хорошо.
Там точнее было бы через $L$-функцию Кармайкла, ну да ладно.
Я Вам советую разложить модуль на множители и перейти от одного сравнения к системе. Множители будут достаточно маленькими, чтобы вычисления было удобно делать даже в голове. После решения каждого сравнения просто найдете общее решение и все.
Далее, вот пусть у нас есть сравнение $a^x\equiv 1\pmod m$. По т. Эйлера мы знаем, что $a^{\varphi (m)}\equiv 1\pmod {m}$. Поскольку все решения образуют арифметическую прогрессию с нулевым начальным членом, т.е. все $x$ описываются сравнением $x\equiv 0\pmod{d}$, то $d$ делит $\varphi(m)$. Если $d$ делит $\varphi(m)$, то у нас есть лишь конечное число вариантов - их можно перебрать. Вот теперь перебирайте делители, как найдете самый малый делитель, удовлетворяющий сравнению, так он и будет его решением.

[Mary84]

$\begin{cases} & { 4^{x}\equiv 1 ( \mod 7)} \\ & { 4^{x}\equiv 1 ( \mod 11) } \end{cases}$

$\varphi (7)=6=2\cdot 3 $

$4^{2}\equiv 2 (\mod 7)$
$4^{3}\equiv 1 (\mod 7)$

$\varphi (11)=10=2\cdot 5 $

$4^{2}\equiv 5 (\mod 11)$
$4^{5}\equiv 1 (\mod 11)$

Первый член арифметической прогрессии равен $3\cdot5=15 , d=15$.

[Sonic86]

Прекрасно
Только советую все же написать не $3\cdot 5$, а $\text{НОК}(3,5)$. Ну как хотите, главное, чтобы Вы это понимали.
Ну и слов можно добавить - тут сами смотрите. Если для себя решаете, то слов не нужно, для препода - смотря какой препод...

[Mary84]

Точно, нужно НОК написать. Спасибо Вам большое!