Теорема Кармайкла

[xagiwo]

Пытаюсь доказать, что мультипликативная группа $U(\mathbb Z/p^n\mathbb Z),\, p \text{ – нечётное простое}$ циклична. Пока получается только в случае $n = 1$. Что делать с большими $n$?
Случай n=1:
Будем работать в поле $\mathbb Z/p\mathbb Z$. Назовём цепочкой длины $n$, порождённой $x$ множество $\{x^1 \neq 1,x^2 \neq 1,…, x^{n-1} \neq 1,\, x^n = 1\}$. Докажем 6 утверждений:

1. Если цепочка длины $n$ есть, то она одна. Выводится из того, что у уравнения $x^n = 1$ не более $n$ решений и все они — в цепочке.
2. Пусть есть цепочка длины $n$, порождённая $x$ и число $m \mid n$, тогда цепочка длины $m$ есть и содержится в цепочке длины $n$. Док-во: достаточно взять $\{x^{n/m}, x^{2n/m}, …, x^n\}$
3. Если $A$ — подцепочка $B$, то длина $A$ делит длину $B$. Док-во: пусть $B$ длины $n$ и порождено $x$, а $A$ порождено $x^a$. Легко проверить, что $\{x^a, x^{2a}, …, x^{\frac{na}{\gcd(n,a)}}\}$ — цепочка, а потому $A$ — цепочка длины $\frac{n}{\gcd(n,a)} \mid n$
4. Если длины $A$ и $B$ взаимно просты, то единственный их общий элемент есть единица. Иначе длина общей подцепочки $A$ и $B$ была бы общим делителем их длин.
5. Пусть есть цепочки длин $n$ и $m$, порождённые $x$ и $y$, $\gcd(n,m) = 1$. Тогда есть цепочка длины $nm$. Действительно, рассмотрим $\{(xy), (xy)^2, …, (xy)^{nm}\}$. Если $(xy)^k = 1$, то $x^{k \bmod n}$ и $y^{m-k \bmod m}$ есть общий элемент этих цепочек, то есть единица, тогда $k \vdots n, k \vdots m \Rightarrow k \vdots nm$.
6. Пусть есть цепочки длин $n$ и $m$, тогда есть цепочка длины $\gcd(n,m)$ и она содержит обе эти цепочки. Док-во: выделим из этих цепочек подцепочки взаимно простых длин $a \mid n,\, b \mid m,\, ab = \gcd(n,m)$. По лемме 5 есть цепочка длины $ab = \gcd(n,m)$ и по лемме 2 она содержит цепочки длин $n$ и $m$

Обобщая утверждение 6 на произвольное число цепочек и применяя к цепочкам, порождённым всеми возможными ненулевыми элементами поля получим цепочку, которая содержит все элементы поля, что и означает цикличность мультипликативной группы.

Попытка применить это для больших $n$ ломается уже на утверждении 1, у $x^s = 1$ может быть сколько угодно решений. Придирки по оформлению приветствуются.

[xagiwo]

ps в пункте 6 $\operatorname{lcm}$, а не $\gcd$

[Padawan]

Почитайте, например, док-во в учебнике И. М. Виноградова.

[Sonic86]

Есть также доказательство в учебнике Бухштаба Теория чисел.
ЕМНИП, если $a$ - первообразная в $\mathbb{Z}/p\mathbb{Z}$, то для $n=2$ либо $a$, либо $a+p$ - первообразная в $\mathbb{Z}/p^2\mathbb{Z}$. А для $n>2$ вроде бы вообще просто подъем работал...

[Padawan]

Там так: если $a$ -- первообразный корень по модулю $p$ такой, что $a^{p-1}\not\equiv 1\pmod {p^2}$, то $a$ является первообразных корнем сразу по всем модулям $p^\alpha$. И из двух чисел $a$, $a+p$ этому условию по крайней мере одно число удовлетворяет.

[xagiwo]

Padawan, Sonic86, спасибо!