Простой вопрос о сравнениях (корень из единицы по модулю)

[Simba]

Всегда ли можно извлекать нечетный корень в случае: $a^{2k+1}=1 \mod p$ $\quad\rightarrow\quad$ $a=1 \mod p$???

[bnovikov]

Simba в сообщении #486902 писал(а):

Всегда ли можно извлекать нечетный корень в случае: $a^{2k+1}=1(\mod(p))$ $\rightarrow$ $a=1(\mod(p))$???

Нет. $2^{3}\equiv 1\mod(7)$

[Simba]

А в каких случаях можно?

[bnovikov]

Simba в сообщении #486930 писал(а):

А в каких случаях можно?

Не знаю. Почитайте какой нибудь учебник по теории чисел (Виноградов, или Бухштаб, или Боревич - Шафаревич).

[Sonic86]

Simba в сообщении #486930 писал(а):

А в каких случаях можно?

Можно, если степень взаимно проста с $\varphi (p)=p-1$:
$a^r \equiv 1 \pmod p \wedge \text{НОД}(r,p-1)=1 \Rightarrow a \equiv 1 \pmod p$.
Замечу еще, что если порядок $a$ равен $q$ и $\text{НОД}(r,p-1)=1$, то и порядок $a^r$ тоже равен $q$ (в частности, если $a$ - образующая, то и $a^r$ - образующая).
Это все верно не только в $\mathbb{Z}_p^{\times}$, но и в любой циклической конечной коммутативной группе (в частности и для сравнений по нечетным составным модулям).
(обратите внимание на запись сравнений в ТеХе)