Циклические группы в абстрактной алгебре

Циклическая группа (cyclic group) — это группа, которую можно полностью получить (сгенерировать) из одного элемента.

Иными словами, если имеется элемент a и если брать его степени:

..., a^-2, a^-1, e, a, a^2, a^3, ...

то можно получить всю группу.

Формально:

G = <a> = {a^n | n ∈ Z}

Такой элемент a называется generator (генератор). По-простому, один элемент “накручивает” всю группу.

Важная ремарка про notation

Если группа записывается в multiplicative notation, то пишут:

a^n

Это значит:

a · a · a · ... · a

n раз. Иначе говоря, элемент a, скомбинированный сам с собой n раз через групповую операцию.

Но если группа записывается в additive notation, то вместо степеней пишут:

na

Например в группе (Z, +) запись:

3 · 1

означает:

1 + 1 + 1 = 3

То есть в additive notation степени превращаются в repeated addition.

Пример 1: группа (Z, +)

Группа целых чисел под сложением:

(Z, +)

является cyclic group.

Её генераторы 1 и -1. Почему?

Потому что из 1 можно получить все integers:

..., -3, -2, -1, 0, 1, 2, 3, ...

В additive notation:

n · 1 = n

Из -1 тоже можно получить все integers:

n · (-1) = -n

Поэтому пишут:

Z = <1> = <-1>

Пример 2: группа (Z_n, +)

Группа:

Z_n = {0, 1, 2, ..., n-1}

под сложением modulo n тоже является cyclic group.

Всегда:

<1> = Z_n

Также:

<-1> = <n-1> = Z_n

Например в Z4:

Z4 = {0, 1, 2, 3}

и:

<1> = {0, 1, 2, 3}

потому что:

1
1 + 1 = 2
1 + 1 + 1 = 3
1 + 1 + 1 + 1 = 0

Также:

<3> = {0, 3, 2, 1} = Z4

Значит 1 и 3 являются generators of Z4.

Пример 3: Z8

Другой пример:

Z8 = <1> = <3> = <5> = <7>

То есть generators of Z8:

1, 3, 5, 7

А вот 2 не generator:

<2> = {0, 2, 4, 6}

Из 2 получается только подгруппа, а не вся группа Z8.

Тут уже видна закономерность: в Z_n генераторами являются элементы, взаимно простые с n.

То есть:

gcd(n, k) = 1

Для Z8:

gcd(8,1) = 1
gcd(8,3) = 1
gcd(8,5) = 1
gcd(8,7) = 1

А:

gcd(8,2) = 2

поэтому 2 не generator.

Напоминалка: GCD и взаимно простые числа

gcd(a, b) — это greatest common divisor, то есть наибольший общий делитель (НОД) чисел a и b.

Например:

gcd(8, 12) = 4

Потому что 4 — самое большое число, которое делит и 8, и 12.

Взаимно простые числа

Числа a и b называются взаимно простыми (coprime / relatively prime), если:

gcd(a, b) = 1

То есть у них нет общих делителей, кроме 1.

Примеры:

gcd(8, 3) = 1

Значит 8 и 3 взаимно простые.

gcd(8, 5) = 1

Значит 8 и 5 взаимно простые.

А вот:

gcd(8, 6) = 2

Значит 8 и 6 не взаимно простые.

Nonexample: U(8)

Не всякая finite group является cyclic.

Например:

U(8) = {1, 3, 5, 7}

не является cyclic group.

В первую очередь, разберёмся, что вообще такое U(8).

Что такое U(8)

U(8) — это группа обратимых элементов по модулю 8.

То есть берём числа из:

Z8 = {0, 1, 2, 3, 4, 5, 6, 7}

и оставляем только те, у которых есть multiplicative inverse modulo 8.

Получаем:

U(8) = {1, 3, 5, 7}

Короче, это такие числа, которые взаимно просты с 8:

gcd(1, 8) = 1
gcd(3, 8) = 1
gcd(5, 8) = 1
gcd(7, 8) = 1

А числа:

0, 2, 4, 6

не входят в U(8), потому что у них нет обратного элемента по умножению modulo 8.

Операция в U(8)

Операция в U(8) — умножение modulo 8:

multiplication modulo 8

Например:

3 * 5 = 15 ≡ 7 (mod 8)

Значит внутри U(8):

3 * 5 = 7

Ещё примеры:

3 * 3 = 9 ≡ 1 (mod 8)
5 * 5 = 25 ≡ 1 (mod 8)
7 * 7 = 49 ≡ 1 (mod 8)

Почему это группа

U(8) является группой под умножением modulo 8.

Identity element: 1.

Каждый элемент имеет inverse:

1^-1 = 1
3^-1 = 3
5^-1 = 5
7^-1 = 7

Потому что:

1 * 1 ≡ 1 (mod 8)
3 * 3 ≡ 1 (mod 8)
5 * 5 ≡ 1 (mod 8)
7 * 7 ≡ 1 (mod 8)

И результат умножения любых двух элементов из U(8) снова лежит в U(8).

Почему это не циклическая группа

Проверим generated subgroups:

<1> = {1}
<3> = {3, 1}
<5> = {5, 1}
<7> = {7, 1}

Ни один элемент не порождает всю группу:

{1, 3, 5, 7}

Значит:

U(8) ≠ <a>

для любого:

a ∈ U(8)

Теорема: когда степени совпадают

Пусть a — элемент группы. Если a имеет infinite order, то:

a^i = a^j iff i = j

То есть степени не повторяются.

iff означает “if and only if”.

Если a имеет finite order n, то:

a^i = a^j iff n divides (i - j)

То есть степени повторяются по модулю n.

Короче, если |a| = n, то степени a ведут себя циклично, как integers modulo n.

Например, если:

|a| = 6

то:

a^0 = a^6 = a^12 = ...
a^1 = a^7 = a^13 = ...
a^2 = a^8 = a^14 = ...

и так далее.

Следствие: Cyclic group порядка n работает как Z_n

Если:

|a| = n

то внутри подгруппы <a> операция со степенями работает как сложение modulo n.

Потому что:

a^i a^j = a^(i+j)

А если i + j больше n, оно заворачивается modulo n. То есть finite cyclic group порядка n ведёт себя как Z_n.

Если же a имеет infinite order, то <a> ведёт себя как Z.

Для тех, кто ничего не понял

Говоря проще, если элемент a имеет порядок n, то при повторении a получается цикл длины n. Не забывайте, что порядок группы — это количество элементов в группе. Порядок элемента g в группе — это минимальное положительное число n, такое что: g^n = e.

Например, пусть |a| = 4. Значит:

a^0 = e
a^1 = a
a^2
a^3
a^4 = e
a^5 = a
a^6 = a^2
a^7 = a^3
a^8 = e

То есть степени начинают повторяться каждые 4 шага. Это очень похоже на Z4:

0, 1, 2, 3, 0, 1, 2, 3, ...

Что касается степеней, которые опять же означают комбинацию элемента с самим собой. При умножении степеней показатели складываются:

a^i a^j = a^(i+j)

Но поскольку цикл имеет длину n, показатель можно брать modulo n. То есть:

a^i a^j = a^((i+j) mod n)

Поэтому finite cyclic group порядка n по своей логике работает как Z_n. Если же a имеет infinite order, цикл никогда не замыкается, и <a> работает как обычные integers (Z).

Следствие: Порядок элемента и порядок generated subgroup

Любой элемент a группы G порождает некоторую подгруппу: <a>. Но важно: элемент не обязан порождать всю группу G. Он порождает только те элементы, до которых можно добраться повторным применением group operation к самому a.

В multiplicative notation:

<a> = {..., a^-2, a^-1, e, a, a^2, a^3, ...}

В additive notation:

<a> = {..., -2a, -a, 0, a, 2a, 3a, ...}

Так, вот следствие из теоремы выше такое: порядок элемента равен количеству элементов в подгруппе, которую он порождает.

Записывается так:

|a| = |<a>|

То есть если элемент a возвращается в identity через n повторений, то в подгруппе <a> будет ровно n разных элементов.

Пример в Z8

В группе:

(Z8, +)

элемент 3 порождает всю группу:

<3> = Z8

Потому что repeated addition modulo 8 даёт:

3
3 + 3 = 6
3 + 3 + 3 = 9 ≡ 1 (mod 8)
3 + 3 + 3 + 3 = 12 ≡ 4 (mod 8)
3 + 3 + 3 + 3 + 3 = 15 ≡ 7 (mod 8)
3 + 3 + 3 + 3 + 3 + 3 = 18 ≡ 2 (mod 8)
3 + 3 + 3 + 3 + 3 + 3 + 3 = 21 ≡ 5 (mod 8)
3 + 3 + 3 + 3 + 3 + 3 + 3 + 3 = 24 ≡ 0 (mod 8)

Получили все элементы:

{0, 1, 2, 3, 4, 5, 6, 7}

Поэтому:

<3> = Z8

и:

|3| = |<3>| = 8

Пример элемента, который не порождает всю группу

В той же группе Z8 элемент 2 порождает только подгруппу:

<2> = {0, 2, 4, 6}

Потому что:

2
2 + 2 = 4
2 + 2 + 2 = 6
2 + 2 + 2 + 2 = 8 ≡ 0 (mod 8)

После этого цикл повторяется.

Значит:

|2| = |<2>| = 4

Но:

<2> ≠ Z8

То есть 2 порождает подгруппу, но не всю группу.

Пример identity element

Identity element всегда порождает только trivial subgroup:

<e> = {e}

В Z8 identity element — это 0. Поэтому:

<0> = {0}

и:

|0| = 1

То есть identity никуда не “двигает” группу и ничего нового не порождает.

Следствие: если a^k = e, то |a| делит k

Пусть элемент a имеет порядок n:

|a| = n

Это значит, что n — минимальное положительное число, для которого:

a^n = e

Следствие говорит: если a^k = e, то n делит k.

То есть identity element появляется только на степенях, кратных порядку элемента. Иначе говоря, если элемент возвращается в identity через n шагов, то дальше он будет возвращаться в identity через:

n, 2n, 3n, 4n, ...

Пример с порядком 6

Если:

|a| = 6

то цикл степеней выглядит так:

a^0 = e
a^1 = a
a^2
a^3
a^4
a^5
a^6 = e
a^7 = a
a^8 = a^2
...

Identity появляется на степенях:

0, 6, 12, 18, ...

То есть на multiples of 6.

Поэтому:

a^6 = e
a^12 = e
a^18 = e

Но:

a^5 != e
a^7 != e

если порядок элемента действительно равен 6.

Пример в D4

В группе D4 возьмём элемент R90. Его порядок:

|R90| = 4

Потому что:

R90^4 = R0

где R0 — identity element.

Значит R90^k = R0 только тогда, когда k делится на 4.

Например:

R90^4 = R0
R90^8 = R0
R90^12 = R0

Но:

R90^1 = R90
R90^2 = R180
R90^3 = R270
R90^5 = R90

То есть identity появляется только на кратных 4.

Пример в Z4

В группе:

(Z4, +)

операция — сложение modulo 4, поэтому вместо a^k пишут:

k · a

Возьмём элемент 3. Его порядок:

|3| = 4

Потому что:

3 + 3 + 3 + 3 = 12 ≡ 0 (mod 4)

Значит:

k · 3 = 0

только когда k делится на 4.

Например:

4 · 3 = 12 ≡ 0 (mod 4)
8 · 3 = 24 ≡ 0 (mod 4)
12 · 3 = 36 ≡ 0 (mod 4)

Но:

1 · 3 = 3
2 · 3 = 6 ≡ 2 (mod 4)
3 · 3 = 9 ≡ 1 (mod 4)
5 · 3 = 15 ≡ 3 (mod 4)

Следствие: связь между |ab| и |a||b|

Если a и b принадлежат finite group и коммутируют:

ab = ba

то |ab| делит |a||b|. То есть порядок произведения ab делит произведение порядков a и b.

Условие ab = ba здесь критично. Без него утверждение может не работать.

Это свойство не говорит, что:

|ab| = |a||b|

Оно говорит только, что |ab| divides |a||b|. То есть порядок ab может быть меньше.

Пример

Пусть:

|a| = 4
|b| = 6
ab = ba

Тогда:

|ab| divides 4 * 6

То есть:

|ab| divides 24

Значит возможный порядок ab может быть, например:

1, 2, 3, 4, 6, 8, 12, 24

Но не может быть:

5, 7, 10, 11

Пример в Z8

В группе:

(Z8, +)

все элементы коммутируют.

Возьмём:

a = 2
b = 3

Порядки:

|2| = 4
|3| = 8

Сумма:

2 + 3 = 5

Порядок 5 в Z8:

|5| = 8

И правда:

8 divides 4 * 8

Теорема: порядок a^k

Пусть элемент a имеет порядок n:

|a| = n

Тогда порядок элемента a^k вычисляется по формуле:

|a^k| = n / gcd(n, k)

Это говорит, через сколько повторений элемент a^k вернётся в identity.

Иными словами

Если a имеет порядок n, то степени элемента a образуют цикл длины n:

e, a, a^2, ..., a^(n-1), e, a, a^2, ...

Когда мы берём a^k, мы как будто двигаемся по этому циклу не на 1 шаг, а сразу на k шагов.

• Если gcd(n, k) = 1, то шаг k проходит по всему циклу длины n, поэтому a^k тоже является generator.
• Если gcd(n, k) > 1, то шаг k попадает только в часть цикла, поэтому a^k порождает меньшую подгруппу.

Именно это измеряет:

gcd(n, k)

Пример: элемент порядка 8

Пусть:

|a| = 8

Тогда:

a^8 = e

Элемент a^2

|a^2| = 8 / gcd(8, 2) = 8 / 2 = 4

То есть a^2 имеет порядок 4.

Цикл:

(a^2)^1 = a^2
(a^2)^2 = a^4
(a^2)^3 = a^6
(a^2)^4 = a^8 = e

Элемент a^3

|a^3| = 8 / gcd(8, 3) = 8 / 1 = 8

То есть a^3 имеет порядок 8. Значит a^3 тоже generator всей cyclic subgroup <a>.

Цикл:

a^3, a^6, a^9, a^12, a^15, a^18, a^21, a^24

Но показатели считаются modulo 8:

a^3, a^6, a^1, a^4, a^7, a^2, a^5, a^0

То есть мы получили все элементы:

e, a, a^2, a^3, a^4, a^5, a^6, a^7

Пример в Z8

В группе:

(Z8, +)

элемент 1 имеет порядок 8:

|1| = 8

Потому что:

8 · 1 = 0 mod 8

Теперь посмотрим на элемент 2. Формула говорит:

|2| = 8 / gcd(8, 2) = 8 / 2 = 4

И правда:

2
2 + 2 = 4
2 + 2 + 2 = 6
2 + 2 + 2 + 2 = 8 ≡ 0 (mod 8)

Значит:

|2| = 4

Ещё пример в Z8: элемент 3

|3| = 8 / gcd(8, 3) = 8 / 1 = 8

Значит 3 имеет порядок 8 и порождает всю группу Z8.

Проверка:

3
3 + 3 = 6
3 + 3 + 3 = 9 ≡ 1
3 + 3 + 3 + 3 = 12 ≡ 4
3 + 3 + 3 + 3 + 3 = 15 ≡ 7
3 + 3 + 3 + 3 + 3 + 3 = 18 ≡ 2
3 + 3 + 3 + 3 + 3 + 3 + 3 = 21 ≡ 5
3 + 3 + 3 + 3 + 3 + 3 + 3 + 3 = 24 ≡ 0

Получили все элементы:

0, 1, 2, 3, 4, 5, 6, 7

Но и это ещё не всё!

Из этого следствия про порядок a^k можно вытащить ещё кое-что интересное. Пусть элемент a имеет порядок n:

|a| = n

и пусть:

d = gcd(n, k)

Тогда:

<a^k> = <a^d>

То есть элемент a^k порождает ту же самую подгруппу, что и a^gcd(n,k).

Грубо говоря, a^k ходит по циклу <a> с шагом k, но набор достижимых позиций зависит только от gcd(n, k).

Пример

Пусть:

|a| = 24

То есть:

a^24 = e

Возьмём:

k = 10

Тогда:

gcd(24, 10) = 2

Значит:

<a^10> = <a^2>

То есть <a^10> и <a^2> порождают одно и то же.

Что порождает a^10? Считаем степени a^10:

(a^10)^1 = a^10
(a^10)^2 = a^20
(a^10)^3 = a^30 = a^6
(a^10)^4 = a^40 = a^16
(a^10)^5 = a^50 = a^2
(a^10)^6 = a^60 = a^12
(a^10)^7 = a^70 = a^22
(a^10)^8 = a^80 = a^8
(a^10)^9 = a^90 = a^18
(a^10)^10 = a^100 = a^4
(a^10)^11 = a^110 = a^14
(a^10)^12 = a^120 = e

Показатели считаются modulo 24, потому что:

a^24 = e

Получаем:

<a^10> = {e, a^2, a^4, a^6, a^8, a^10, a^12, a^14, a^16, a^18, a^20, a^22}

Что порождает a^2?

<a^2> = {e, a^2, a^4, a^6, a^8, a^10, a^12, a^14, a^16, a^18, a^20, a^22}

Это тот же самый набор!

Посчитаем порядок a^10. Так как:

gcd(24, 10) = 2

то:

|a^10| = 24 / 2 = 12

И действительно, в <a^10> ровно 12 элементов.

Казалось бы ну и что с того, что они порождают одно и то же? Дело в том, что с a^2 попроще работать. Это как бы самый простой “шаг”, который описывает ту же самую подгруппу.

Следствие: порядок элемента делит порядок группы

В finite cyclic group порядок любого элемента делит порядок всей группы.

То есть если:

|G| = n

и:

g ∈ G

то |g| divides n.

В общем, в finite cyclic group не может быть элемента, порядок которого не делит порядок группы.

Например, в cyclic group порядка 8 не может быть элемента порядка:

3
5
6
7

Потому что эти числа не делят 8.

Пример: Z8

В группе:

(Z8, +)

порядок группы:

|Z8| = 8

Порядки элементов:

|0| = 1
|1| = 8
|2| = 4
|3| = 8
|4| = 2
|5| = 8
|6| = 4
|7| = 8

Все эти числа делят 8:

1, 2, 4, 8

Следствие: когда <a^i> = <a^j> и |a^i| = |a^j|

Пусть элемент a имеет порядок n:

|a| = n

Тогда:

<a^i> = <a^j>

если и только если:

gcd(n, i) = gcd(n, j)

И также:

|a^i| = |a^j|

если и только если:

gcd(n, i) = gcd(n, j)

То есть подгруппа, которую порождает a^i, определяется не самим i, а числом gcd(n, i).

Иными словами

Если a имеет порядок n, то степени a ходят по циклу длины n.

Элемент a^i ходит по этому циклу с шагом i. Но итоговая подгруппа зависит не от самого шага i, а от того, какой общий делитель у i и n.

Короче говоря, если верно:

gcd(n, i) = gcd(n, j)

то a^i и a^j порождают одну и ту же подгруппу и имеют одинаковый порядок. Если gcd разные, то подгруппы разные и порядки тоже разные.

Пример: |a| = 12

Пусть:

|a| = 12

Сравним:

a^4

и:

a^8

Считаем gcd:

gcd(12, 4) = 4
gcd(12, 8) = 4

Значит:

<a^4> = <a^8>

и:

|a^4| = |a^8|

Проверим:

<a^4> = {e, a^4, a^8}

А:

<a^8> = {e, a^8, a^16}

Но так как показатели считаются modulo 12:

a^16 = a^4

получаем:

<a^8> = {e, a^8, a^4}

То есть это та же самая подгруппа.

Ещё пример

Сравним:

a^3

и:

a^9

gcd(12, 3) = 3
gcd(12, 9) = 3

Значит:

<a^3> = <a^9>

И действительно:

<a^3> = {e, a^3, a^6, a^9}

<a^9> = {e, a^9, a^18, a^27}

Считаем показатели modulo 12:

a^18 = a^6
a^27 = a^3

Получаем ту же подгруппу:

{e, a^3, a^6, a^9}

Следствие: Критерий генератора в finite cyclic group

Пусть:

G = <a>

и:

|a| = n

Тогда элемент:

a^j

является generator всей группы тогда и только тогда, когда:

gcd(n, j) = 1

То есть показатель j должен быть взаимно прост с порядком группы.

Генераторы Z_n

Для Z_n это звучит так:

элемент k является generator of Z_n iff gcd(n, k) = 1.

То есть k порождает всю группу Z_n, если k взаимно просто с n.

Примеры:

Z4 generators: 1, 3
Z6 generators: 1, 5
Z8 generators: 1, 3, 5, 7

Пример: Z8

В группе:

(Z8, +)

элемент 3 является generator, потому что:

gcd(8, 3) = 1

Проверим:

3
3 + 3 = 6
3 + 3 + 3 = 9 ≡ 1 (mod 8)
3 + 3 + 3 + 3 = 12 ≡ 4 (mod 8)
3 + 3 + 3 + 3 + 3 = 15 ≡ 7 (mod 8)
3 + 3 + 3 + 3 + 3 + 3 = 18 ≡ 2 (mod 8)
3 + 3 + 3 + 3 + 3 + 3 + 3 = 21 ≡ 5 (mod 8)
3 + 3 + 3 + 3 + 3 + 3 + 3 + 3 = 24 ≡ 0 (mod 8)

Получили все элементы Z8:

0, 1, 2, 3, 4, 5, 6, 7

Значит:

<3> = Z8

А вот 2 не generator

gcd(8, 2) = 2

Поэтому 2 не порождает всю группу.

Проверим:

2
2 + 2 = 4
2 + 2 + 2 = 6
2 + 2 + 2 + 2 = 8 ≡ 0 (mod 8)

Получили только:

0, 2, 4, 6

То есть:

<2> = {0, 2, 4, 6}

Это подгруппа, но не вся Z8.

Пример, связанный с ECC: группа простого порядка

Пусть есть cyclic group простого порядка:

G = <P>
|G| = 7

Элементы группы в additive notation:

O, P, 2P, 3P, 4P, 5P, 6P

где:

7P = O

O — identity element.

Любой ненулевой kP тоже generator

Берём:

Q = kP

Порядок такого элемента считается так:

|kP| = 7 / gcd(7, k)

Так как 7 — prime number, то для любого:

k = 1, 2, 3, 4, 5, 6

выполняется:

gcd(7, k) = 1

Значит:

|kP| = 7

В общем, в группе простого порядка любой ненулевой элемент является generator. Это одна из причин, почему в ECC любят prime-order groups/subgroups.

Классификация подгрупп циклических групп

У циклических групп (cyclic groups) подгруппы устроены очень аккуратно. Если группа порождена одним элементом:

G = <a>

и имеет порядок:

|G| = n

то все её подгруппы можно полностью описать через делители числа n. Это одна из причин, почему cyclic groups такие удобные.

Fundamental Theorem of Cyclic Groups

Пусть:

G = <a>

и:

|G| = n

Тогда:

1. Любая подгруппа cyclic group тоже является cyclic.
2. Порядок любой подгруппы делит n.
3. Для каждого положительного делителя k числа n существует ровно одна подгруппа порядка k.

Эта подгруппа имеет вид:

<a^(n/k)>

То есть если нужна подгруппа порядка k, надо взять элемент:

a^(n/k)

и посмотреть, что он порождает.

Иными словами

Если cyclic group имеет порядок n, то её элементы идут по циклу:

e, a, a^2, ..., a^(n-1)

Подгруппа — это не случайный набор элементов, а регулярный “подцикл” внутри этого большого цикла. Поэтому возможные размеры подгрупп — только делители n.

Например, если:

|G| = 30

то подгруппа не может иметь порядок 7, потому что 7 не делит 30.

Возможные порядки подгрупп:

1, 2, 3, 5, 6, 10, 15, 30

Пример: Z30

Рассмотрим:

Z30 = {0, 1, 2, ..., 29}

с операцией addition modulo 30. Группа Z30 cyclic:

Z30 = <1>

Порядок группы:

|Z30| = 30

Делители числа 30:

1, 2, 3, 5, 6, 10, 15, 30

Значит у Z30 есть ровно по одной подгруппе каждого из этих порядков.

Все подгруппы Z30

<1>  = {0, 1, 2, ..., 29}        order 30
<2>  = {0, 2, 4, ..., 28}        order 15
<3>  = {0, 3, 6, ..., 27}        order 10
<5>  = {0, 5, 10, 15, 20, 25}    order 6
<6>  = {0, 6, 12, 18, 24}        order 5
<10> = {0, 10, 20}               order 3
<15> = {0, 15}                   order 2
<30> = {0}                       order 1

В Z30 элемент 30 — это то же самое, что 0, потому что:

30 ≡ 0 (mod 30)

Поэтому:

<30> = <0> = {0}

Как найти подгруппу нужного порядка

Для Z_n правило особенно простое. Если нужна подгруппа порядка k, где k делит n, надо взять:

<n/k>

Например, в Z30 нужна подгруппа порядка 6.

Считаем:

30 / 6 = 5

Значит нужная подгруппа:

<5>

И правда:

<5> = {0, 5, 10, 15, 20, 25}

В ней ровно 6 элементов.

Ещё пример: подгруппа порядка 9 в Z36

Рассмотрим:

Z36

Нужна подгруппа порядка 9. Считаем:

36 / 9 = 4

Значит один генератор такой подгруппы: 4. Эта подгруппа:

<4> = {0, 4, 8, 12, 16, 20, 24, 28, 32}

В ней 9 элементов.

Все генераторы этой подгруппы

Чтобы найти остальные генераторы подгруппы порядка 9, надо взять элементы вида 4j, где:

gcd(9, j) = 1

То есть j должен быть взаимно прост с 9.

Такие j:

1, 2, 4, 5, 7, 8

Поэтому генераторы подгруппы <4> в Z36:

4 * 1 = 4
4 * 2 = 8
4 * 4 = 16
4 * 5 = 20
4 * 7 = 28
4 * 8 = 32

И все они порождают одну и ту же подгруппу:

<4> = <8> = <16> = <20> = <28> = <32>

Euler Phi Function

Функция Эйлера (Euler phi function) обозначается:

φ(n)

Она показывает, сколько положительных integers от 1 до n взаимно просты с n.

То есть:

φ(n) = количество k таких, что 1 ≤ k ≤ n и gcd(n, k) = 1

Примеры:

φ(1) = 1
φ(2) = 1
φ(3) = 2
φ(4) = 2
φ(5) = 4
φ(6) = 2
φ(8) = 4
φ(10) = 4

Например:

φ(8) = 4

потому что с 8 взаимно просты:

1, 3, 5, 7

Теорема: количество элементов каждого порядка

Если d — положительный делитель n, то количество элементов порядка d в cyclic group порядка n равно:

φ(d)

То есть если:

|G| = n

и d divides n, то в G ровно:

φ(d)

элементов порядка d.

Пример: элементы разных порядков в Z8

В группе:

Z8

порядок группы:

|Z8| = 8

Делители 8:

1, 2, 4, 8

Элементы порядка 1:

0

Их количество:

φ(1) = 1

Элементы порядка 2:

4

Их количество:

φ(2) = 1

Элементы порядка 4:

2, 6

Их количество:

φ(4) = 2

Элементы порядка 8:

1, 3, 5, 7

Их количество:

φ(8) = 4

Всё сходится.

Следствие: количество элементов порядка d в конечной группе

В любой finite group количество элементов порядка d является кратным φ(d). То есть число элементов порядка d имеет вид:

m · φ(d)

для какого-то целого m ≥ 0.

Смысл этого следствия

В cyclic group порядка n всё точнее если d divides n, то элементов порядка d ровно φ(d).

А вот в произвольной finite group утверждение слабее: элементов порядка d может быть 0, φ(d), 2φ(d), 3φ(d), .... То есть не обязательно ровно φ(d), но обязательно кратно φ(d).

Почему так происходит

Каждый элемент порядка d порождает cyclic subgroup порядка d. А в cyclic group порядка d ровно:

φ(d)

генераторов.

Поэтому элементы порядка d группируются пачками по φ(d) — по генераторам соответствующих cyclic subgroups.

Пример: D4

В группе симметрий квадрата D4 элементы порядка 4:

R90, R270

Их количество: 2.

Считаем:

φ(4) = 2

Значит всё сходится: 2 is a multiple of φ(4).

Ещё пример: элементы порядка 2 в D4

Элементы порядка 2:

R180, H, V, D, D'

Их количество: 5.

Считаем:

φ(2) = 1

Выходит 5 is a multiple of 1. Тоже сходится.

Subgroup Lattice

Подгруппы можно рисовать в виде диаграммы. Такая диаграмма называется subgroup lattice (решётка подгрупп). Верхний элемент диаграммы — вся группа.

Нижний элемент — trivial subgroup:

{e}

Для Z30 верх:

<1> = Z30

низ:

<0> = {0}

А между ними лежат:

<2>, <3>, <5>, <6>, <10>, <15>

Линия между двумя подгруппами означает, что нижняя подгруппа содержится в верхней.

Например:

<10> ≤ <2>

и:

<10> ≤ <5>

Почему cyclic groups такие удобные

В finite cyclic group всё классифицируется через делители порядка группы.

Если:

|G| = n

то:

• подгруппы соответствуют делителям n;
• для каждого делителя есть ровно одна подгруппа;
• каждая подгруппа тоже cyclic;
• количество элементов порядка d равно φ(d).

Для обычных finite groups всё может быть намного сложнее.

Например, группа может иметь несколько разных подгрупп одного и того же порядка или не иметь подгруппы для некоторых делителей.