Уравнение в кольце Z_d

[Профессор Снэйп]

Вопрос возник по ходу следующей темы.

Пусть $d > 0$ --- натуральное число и $n \in \mathbb{Z}_d$. При каких условиях на $d$ и $n$ уравнение $nx^2 - x = 0$ имеет в $\mathbb{Z}_d$ ненулевой корень?

[Профессор Снэйп]

Эквивалентная формулировка задачи такая: при каких натуральных положительных $n$ и $d$ кольцо $n\mathbb{Z}/nd\mathbb{Z}$ будет содержать единичный элемент?

[RIP]

Если $d=p_1^{\alpha_1}\ldots p_s^{\alpha_s}$ --- разложение на простые, то необходимо и достаточно, чтобы $n\not\equiv0\pmod{p_1\cdot\ldots\cdot p_s}$.

[Профессор Снэйп]

Ага. Проверил, сходится. Спасибо!