Число решений $x^k=1$

[lena7]

Доказать, что число решений уравнения $x^k=1$ в циклической группе $C_n$ порядка $n$ равно $(n,k)$ -- наибольшему общему делителю $n$ и $k$.

Если $C_n=\langle a\rangle$, то порядок элемента $a^m$ равен $n/(m,n)$. Нужно найти число таких $m$, что $n/(m,n)$ делит $k$. Как это можно сделать? Или может задачу с другого конца проще решать?

[AV_77]

Все решения уравнения $x^k = 1$ лежат в некоторой подгруппе. Найдете ее образующую - найдете и все решения уравнения.

[provincialka]

А что считать уже известным (доказанным)? Например, если $a^m=1$, чему может быть равно $m$?

Можно просто записать искомое решение как $a^x$, подставить, и найти все возможные $x$. И, соответственно, разные $a^x$.

[lena7]

AV_77 в сообщении #716361 писал(а):

Все решения уравнения $x^k = 1$ лежат в некоторой подгруппе.

Точно! Раз это подгруппа, то её порядок $d$ делит $n$. Но $d$ также делит $k$. Наибольшую подгруппу получим, когда $d=(n,k)$.

[provincialka]

lena7 в сообщении #716369 писал(а):

AV_77 в сообщении #716361 писал(а):

Все решения уравнения $x^k = 1$ лежат в некоторой подгруппе.

Точно! Раз это подгруппа, то её порядок $d$ делит $n$. Но $d$ также делит $k$. Наибольшую подгруппу получим, когда $d=(n,k)$.

А она точно наибольшая? Прямое перечисление как-то надежнее

[lena7]

provincialka
Если существует бо́льшая подгруппа, то её порядок делит $n$, $k$, а значит и $(n,k)$ -- противоречие.

[provincialka]

Вот теперь вроде все!