До сих пор мы в основном изучали отдельные группы. Теперь научимся брать несколько групп и собирать из них одну новую, более крупную группу.
Такая конструкция называется external direct product (внешнее прямое произведение). Главная идея очень простая:
элемент новой группы состоит сразу из нескольких компонентов, а операция выполняется отдельно в каждом компоненте.
Определение
Пусть есть группы:
G1, G2, ..., Gn
Их external direct product обозначается:
G1 ⊕ G2 ⊕ ... ⊕ Gn
Элементы этой группы — кортежи:
(g1, g2, ..., gn)
где:
g1 ∈ G1
g2 ∈ G2
...
gn ∈ Gn
Формально:
G1 ⊕ G2 ⊕ ... ⊕ Gn
=
{(g1, g2, ..., gn) | gi ∈ Gi}
Получившаяся группа будет абелевой, если изначальные группы тоже были абелевыми. Если хотя бы одна “изначальная” группа была неабелевой, то и результат тоже неабелева группа.
Как работает операция
Операция выполняется componentwise / покомпонентно. То есть:
(g1, g2, ..., gn)(h1, h2, ..., hn)
=
(g1h1, g2h2, ..., gnhn)
Каждая пара компонентов объединяется по правилам своей группы.
Важно: в разных компонентах могут использоваться разные операции. Например, в первой компоненте может быть умножение modulo 8, а во второй — умножение modulo 10.
Простой пример с обычным сложением
Рассмотрим:
Z2 ⊕ Z3
Здесь:
Z2 = {0, 1}
и:
Z3 = {0, 1, 2}
Поэтому элементы direct product — все возможные пары:
Z2 ⊕ Z3 =
{
(0,0), (0,1), (0,2),
(1,0), (1,1), (1,2)
}
Всего элементов:
2 · 3 = 6
Как складываются элементы
Операция выполняется по координатам:
(a, b) + (c, d)
=
(a + c mod 2, b + d mod 3)
Например:
(1, 2) + (1, 2)
Первая координата считается modulo 2:
1 + 1 ≡ 0 (mod 2)
Вторая координата считается modulo 3:
2 + 2 ≡ 1 (mod 3)
Поэтому:
(1, 2) + (1, 2) = (0, 1)
Почему это группа
External direct product наследует свойства исходных групп.
Closure
Если:
g1, h1 ∈ G1
то:
g1h1 ∈ G1
То же самое верно для каждой компоненты.
Значит результат покомпонентной операции снова лежит в direct product.
Identity
Если identity elements исходных групп:
e1, e2, ..., en
то identity direct product:
(e1, e2, ..., en)
Потому что:
(g1, ..., gn)(e1, ..., en)
=
(g1, ..., gn)
Inverse
Inverse элемента:
(g1, g2, ..., gn)
равен:
(g1^-1, g2^-1, ..., gn^-1)
То есть inverse тоже вычисляется покомпонентно.
Associativity
Associativity выполняется в каждой исходной группе, поэтому она выполняется и для кортежей.
Размер direct product
Если все группы конечны, то:
|G1 ⊕ G2 ⊕ ... ⊕ Gn|
=
|G1||G2|...|Gn|
Почему? Потому что для первой компоненты есть |G1| вариантов, для второй — |G2| вариантов и так далее.
Пример
|Z2 ⊕ Z3| = |Z2| · |Z3| = 2 · 3 = 6
И действительно, мы получили шесть пар.
Пример с U(8) и U(10)
Рассмотрим:
U(8) = {1, 3, 5, 7}
и:
U(10) = {1, 3, 7, 9}
Обе группы используют multiplication modulo соответствующего числа.
Элемент direct product имеет вид:
(a, b)
где:
a ∈ U(8)
b ∈ U(10)
Например:
(3, 7)
и:
(7, 9)
Перемножим их:
(3, 7)(7, 9)
Первая координата считается modulo 8:
3 · 7 = 21 ≡ 5 (mod 8)
Вторая координата считается modulo 10:
7 · 9 = 63 ≡ 3 (mod 10)
Поэтому:
(3, 7)(7, 9) = (5, 3)
Почему произведение называется external
Слово external / внешнее означает, что мы начинаем с отдельных групп:
G1
G2
...
Gn
и строим из них новую группу кортежей. То есть новая группа изначально не обязана находиться внутри какой-то уже существующей группы.
Позже появится похожая конструкция internal direct product. Там, наоборот, большая группа уже существует, а мы разлагаем её на подгруппы.
Связь с обычными координатами
Знакомый пример:
R² = R ⊕ R
Элемент R² — это пара:
(x, y)
Сложение выполняется покомпонентно:
(x1, y1) + (x2, y2)
=
(x1 + x2, y1 + y2)
Аналогично:
R³ = R ⊕ R ⊕ R
То есть external direct product — это та же идея координат, только компоненты теперь могут быть любыми группами.
Пример: Z2 ⊕ Z3 изоморфна Z6
Рассмотрим элемент:
(1, 1) ∈ Z2 ⊕ Z3
Почему берём именно (1,1)? Элемент 1 является generator и в Z2, и в Z3. Поэтому порядки его компонентов равны 2 и 3. Так как:
gcd(2,3) = 1
порядок пары равен:
|(1,1)| = lcm(2,3) = 6
А вся группа Z2 ⊕ Z3 тоже имеет 6 элементов. Значит (1,1) может породить всю группу.
Будем складывать его с самим собой:
0(1,1) = (0,0)
1(1,1) = (1,1)
2(1,1) = (0,2)
3(1,1) = (1,0)
4(1,1) = (0,1)
5(1,1) = (1,2)
6(1,1) = (0,0)
Мы получили все шесть элементов группы.
Значит (1,1) порождает всю группу. Следовательно:
Z2 ⊕ Z3
является cyclic group порядка 6. А любая cyclic group порядка 6 изоморфна Z6.
Поэтому:
Z2 ⊕ Z3 ≅ Z6
Кстати…
Кстати, (1,2) тоже generator. В группе:
Z2 ⊕ Z3
элемент 1 порождает Z2:
<1> = {0,1}
А элемент 2 порождает Z3:
<2> = {0,2,1}
Теперь посмотрим на пару:
(1,2)
Порядок первой координаты:
|1| = 2
Порядок второй координаты:
|2| = 3
Поэтому порядок пары:
|(1,2)| = lcm(2,3) = 6
А во всей группе:
|Z2 ⊕ Z3| = 2·3 = 6
Значит (1,2) имеет тот же порядок, что и вся группа, и потому порождает её целиком.
Но direct product не всегда cyclic
Рассмотрим:
Z2 ⊕ Z2
Её элементы:
(0,0)
(1,0)
(0,1)
(1,1)
У каждого non-identity element порядок равен 2.
Например:
(1,0) + (1,0) = (0,0)
(0,1) + (0,1) = (0,0)
(1,1) + (1,1) = (0,0)
Ни один элемент не имеет порядка 4. Значит ни один элемент не может породить всю группу. Поэтому:
Z2 ⊕ Z2
не cyclic.
Хотя:
|Z2 ⊕ Z2| = 4
она не изоморфна Z4 потому что Z4 cyclic, а Z2 ⊕ Z2 — нет.
Какие вообще бывают группы порядка 4?
Если не смотреть на названия элементов, а смотреть только на структуру, то существуют ровно два варианта:
Z4
и:
Z2 ⊕ Z2
Z4 cyclic:
Z4 = <1>
А в Z2 ⊕ Z2 каждый non-identity element имеет порядок 2. Это показывает, что одинаковый порядок группы ещё не означает одинаковую структуру.
Теорема: Порядок элемента в direct product
Пусть есть элемент:
(g1, g2, ..., gn)
в direct product конечных групп.
Тогда его порядок равен least common multiple / наименьшему общему кратному порядков компонентов:
|(g1, g2, ..., gn)|
=
lcm(|g1|, |g2|, ..., |gn|)
Почему используется lcm
Элемент:
(g1, g2, ..., gn)
вернётся в identity, когда одновременно:
g1^k = e1
g2^k = e2
...
gn^k = en
То есть k должно быть кратно порядку каждой компоненты.
Самое маленькое такое число — это:
lcm(|g1|, |g2|, ..., |gn|)
Простой пример
Пусть:
|a| = 2
|b| = 3
Тогда:
|(a,b)| = lcm(2,3) = 6
Почему? Первая компонента возвращается в identity каждые 2 шага:
2, 4, 6, ...
Вторая — каждые 3 шага:
3, 6, 9, ...
Впервые обе возвращаются одновременно на шаге 6.
Пример в Z2 ⊕ Z3
Порядок элемента:
(1,1)
Первая компонента 1 ∈ Z2 имеет порядок:
|1| = 2
Вторая компонента 1 ∈ Z3 имеет порядок:
|1| = 3
Поэтому:
|(1,1)| = lcm(2,3) = 6
А так как вся группа имеет порядок 6, элемент (1,1) порождает всю группу.
Теорема: Когда direct product двух cyclic groups тоже cyclic
Пусть:
G
H
— finite cyclic groups.
Тогда:
G ⊕ H
является cyclic тогда и только тогда, когда порядки групп взаимно просты:
gcd(|G|, |H|) = 1
Почему
Пусть:
G = <a>
H = <b>
Тогда порядок элемента:
(a,b)
равен:
|(a,b)| = lcm(|G|, |H|)
Чтобы (a,b) породил весь direct product, его порядок должен быть равен размеру всей группы:
|G ⊕ H| = |G||H|
Поэтому нужно:
lcm(|G|, |H|) = |G||H|
А это выполняется ровно тогда, когда:
gcd(|G|, |H|) = 1
Пример: Z2 ⊕ Z3
Порядки групп:
|Z2| = 2
|Z3| = 3
Они взаимно просты:
gcd(2,3) = 1
Поэтому:
Z2 ⊕ Z3
cyclic.
И:
Z2 ⊕ Z3 ≅ Z6
Контрпример: Z2 ⊕ Z4
Порядки:
2
4
не взаимно просты:
gcd(2,4) = 2
Максимальный возможный порядок элемента:
lcm(2,4) = 4
Но размер всей группы:
|Z2 ⊕ Z4| = 2 · 4 = 8
Чтобы группа была cyclic, в ней должен быть элемент порядка 8. Но максимальный порядок здесь только 4.
Значит:
Z2 ⊕ Z4
не cyclic.
Несколько cyclic groups
Direct product:
G1 ⊕ G2 ⊕ ... ⊕ Gn
finite cyclic groups является cyclic тогда и только тогда, когда порядки всех групп попарно взаимно просты.
То есть:
gcd(|Gi|, |Gj|) = 1
для любых:
i != j
Пример
Z2 ⊕ Z3 ⊕ Z5
Порядки:
2, 3, 5
попарно взаимно просты.
Поэтому группа cyclic и:
Z2 ⊕ Z3 ⊕ Z5 ≅ Z30
Контрпример
Z2 ⊕ Z6
Так как:
gcd(2,6) = 2
эта группа не cyclic.
И хотя её порядок:
|Z2 ⊕ Z6| = 12
она не изоморфна Z12.
Когда Z_m ≅ Z_n1 ⊕ ... ⊕ Z_nk
Пусть:
m = n1n2...nk
Тогда:
Z_m ≅ Z_n1 ⊕ Z_n2 ⊕ ... ⊕ Z_nk
тогда и только тогда, когда числа:
n1, n2, ..., nk
попарно взаимно просты.
Пример
Так как:
30 = 2 · 3 · 5
и числа 2, 3, 5 попарно взаимно просты:
Z30 ≅ Z2 ⊕ Z3 ⊕ Z5
Также:
Z30 ≅ Z6 ⊕ Z5
потому что:
gcd(6,5) = 1
Неудачный пример
Z60
не изоморфна:
Z2 ⊕ Z30
Хотя:
2 · 30 = 60
числа 2 и 30 не взаимно просты:
gcd(2,30) = 2
Поэтому direct product не cyclic, а Z60 cyclic.
Значит:
Z2 ⊕ Z30 not ≅ Z60
Группа U(n) как external direct product
До этого мы рассматривали direct products обычных cyclic groups:
Z_m ⊕ Z_n
Теперь применим ту же конструкцию к группам обратимых элементов modulo n:
U(n)
Напомним:
U(n) = {x ∈ Z_n | gcd(x, n) = 1}
Операция в U(n) — multiplication modulo n.
Например:
U(10) = {1, 3, 7, 9}
Специальная подгруппа U_k(n)
Пусть:
k divides n
Определим:
U_k(n) = {x ∈ U(n) | x ≡ 1 (mod k)}
То есть U_k(n) состоит из тех элементов U(n), которые дают остаток 1 modulo k. Важно не путать:
U_k(n)
и:
U(k)
Это разные объекты.
U(k)— самостоятельная группа units modulok;U_k(n)— специальная подгруппа внутриU(n).
Пример: U_3(15)
Сначала выпишем:
U(15) = {1, 2, 4, 7, 8, 11, 13, 14}
Теперь оставим элементы, которые равны 1 modulo 3:
1 ≡ 1 (mod 3)
4 ≡ 1 (mod 3)
7 ≡ 1 (mod 3)
13 ≡ 1 (mod 3)
Получаем:
U_3(15) = {1, 4, 7, 13}
Теорема: разложение U(st)
Пусть:
gcd(s, t) = 1
То есть s и t взаимно просты.
Тогда:
U(st) ≅ U(s) ⊕ U(t)
Иными словами, multiplicative structure modulo st можно разделить на две независимые компоненты:
modulo s
и:
modulo t
Как выглядит isomorphism
Определим mapping:
Φ : U(st) -> U(s) ⊕ U(t)
по правилу:
Φ(x) = (x mod s, x mod t)
То есть берём один элемент modulo st и смотрим на его остатки отдельно modulo s и modulo t.
Конкретный пример: U(15)
Так как:
15 = 3 · 5
и:
gcd(3, 5) = 1
получаем:
U(15) ≅ U(3) ⊕ U(5)
Mapping выглядит так:
Φ(x) = (x mod 3, x mod 5)
Например:
Φ(7) = (1, 2)
потому что:
7 ≡ 1 (mod 3)
7 ≡ 2 (mod 5)
А:
Φ(13) = (1, 3)
потому что:
13 ≡ 1 (mod 3)
13 ≡ 3 (mod 5)
Структура U(15)
Так как:
U(3) ≅ Z2
и:
U(5) ≅ Z4
то:
U(15) ≅ U(3) ⊕ U(5) ≅ Z2 ⊕ Z4
Поэтому порядок группы:
|U(15)| = 2 · 4 = 8
И действительно:
U(15) = {1, 2, 4, 7, 8, 11, 13, 14}
содержит ровно 8 элементов.
Однако:
U(15) not ≅ Z8
Хотя обе группы имеют по 8 элементов, этого недостаточно для isomorphism.
Группа Z8 cyclic:
Z8 = <1>
В ней есть элемент порядка 8:
|1| = 8
А:
U(15) ≅ Z2 ⊕ Z4
Порядок любого элемента (a, b) в Z2 ⊕ Z4 равен:
|(a,b)| = lcm(|a|, |b|)
В Z2 порядок компоненты может быть максимум 2, а в Z4 — максимум 4.
Поэтому максимальный возможный порядок элемента:
lcm(2,4) = 4
То есть в Z2 ⊕ Z4 вообще нет элемента порядка 8, а значит эта группа не cyclic.
Изоморфизм обязан сохранять порядки элементов и свойство cyclic, поэтому:
Z2 ⊕ Z4 not ≅ Z8
и, следовательно:
U(15) not ≅ Z8
Почему это действительно isomorphism
Нужно проверить, что mapping:
Φ(x) = (x mod s, x mod t)
является one-to-one, onto и сохраняет операцию.
Mapping корректно задан
Если:
x ∈ U(st)
то:
gcd(x, st) = 1
Значит x не имеет общих делителей ни с s, ни с t:
gcd(x, s) = 1
gcd(x, t) = 1
Поэтому:
x mod s ∈ U(s)
и:
x mod t ∈ U(t)
Следовательно:
Φ(x) ∈ U(s) ⊕ U(t)
Operation-preserving
Операция во всех этих группах — multiplication modulo соответствующего числа.
Берём:
x, y ∈ U(st)
Тогда:
Φ(xy)
=
(xy mod s, xy mod t)
Но умножение совместимо с остатками:
xy mod s = (x mod s)(y mod s) mod s
и:
xy mod t = (x mod t)(y mod t) mod t
Поэтому:
Φ(xy) = Φ(x)Φ(y)
То есть операция сохраняется.
One-to-one и onto
Здесь работает Chinese Remainder Theorem / Китайская теорема об остатках.
Она говорит, что если:
gcd(s, t) = 1
то для любой пары остатков:
(a mod s, b mod t)
существует ровно один соответствующий класс:
x mod st
То есть каждая пара из:
U(s) ⊕ U(t)
соответствует ровно одному элементу U(st).
Поэтому Φ одновременно one-to-one и onto. Значит:
U(st) ≅ U(s) ⊕ U(t)
Проверка операции на конкретных числах
В U(15) возьмём: 7, 13. Перемножаем modulo 15:
7 · 13 = 91 ≡ 1 (mod 15)
Значит:
Φ(7 · 13) = Φ(1) = (1, 1)
Теперь сначала применим Φ:
Φ(7) = (1, 2)
Φ(13) = (1, 3)
Перемножим покомпонентно:
(1, 2)(1, 3)
=
(1 · 1 mod 3, 2 · 3 mod 5)
Получаем:
(1, 6 mod 5) = (1, 1)
То есть:
Φ(7 · 13) = Φ(7)Φ(13)
Операция действительно сохранилась.
Связь с подгруппами U_s(st) и U_t(st)
Теорема также утверждает:
U_s(st) ≅ U(t)
и:
U_t(st) ≅ U(s)
Напомним:
U_s(st)
— это элементы U(st), которые равны 1 modulo s.
Пример для U(15)
Так как:
15 = 3 · 5
получаем:
U_3(15) ≅ U(5)
Мы уже нашли:
U_3(15) = {1, 4, 7, 13}
А:
U(5) = {1, 2, 3, 4}
У обеих групп по 4 элемента, и их multiplication structure совпадает через reduction modulo 5.
Например mapping:
x -> x mod 5
даёт:
1 -> 1
4 -> 4
7 -> 2
13 -> 3
То есть все элементы U(5) покрыты ровно по одному разу.
Аналогично:
U_5(15) = {1, 11}
и:
U_5(15) ≅ U(3)
Разложение на несколько компонентов
Пусть:
m = n1n2...nk
и числа:
n1, n2, ..., nk
попарно взаимно просты:
gcd(ni, nj) = 1
при:
i != j
Тогда:
U(m)
≅
U(n1) ⊕ U(n2) ⊕ ... ⊕ U(nk)
То есть можно разложить U(m) на несколько независимых modular components.
Пример: U(105)
Разложим:
105 = 3 · 5 · 7
Числа:
3, 5, 7
попарно взаимно просты.
Поэтому:
U(105)
≅
U(3) ⊕ U(5) ⊕ U(7)
Также можно группировать множители иначе:
105 = 7 · 15
и:
gcd(7, 15) = 1
поэтому:
U(105) ≅ U(7) ⊕ U(15)
Ещё вариант:
105 = 21 · 5
и:
gcd(21, 5) = 1
значит:
U(105) ≅ U(21) ⊕ U(5)
Все эти записи описывают одну и ту же группу разными способами.
Разложение U(105) на cyclic groups
Нам известны структуры:
U(3) ≅ Z2
U(5) ≅ Z4
U(7) ≅ Z6
Поэтому:
U(105)
≅
Z2 ⊕ Z4 ⊕ Z6
Это гораздо удобнее, чем работать напрямую со всеми units modulo 105.
Структура U(p^n)
Пусть p — нечётное простое число, а n ≥ 1 — целое число, которое используется как показатель степени.
Тогда:
p^n
— степень простого числа, а:
U(p^n)
— группа обратимых элементов modulo p^n.
Для нечётного простого p группа U(p^n) является cyclic и имеет порядок:
|U(p^n)| = p^n - p^(n-1)
Эта же формула является значением Euler totient function:
φ(p^n) = p^n - p^(n-1)
Её также можно записать так:
φ(p^n) = p^(n-1)(p - 1)
Поэтому:
U(p^n) ≅ Z_(p^n - p^(n-1))
Пример: U(9)
Представим 9 как степень простого числа:
9 = 3^2
Значит:
p = 3
n = 2
Подставляем в формулу:
|U(3^2)| = 3^2 - 3^(2-1)
Получаем:
|U(9)| = 9 - 3 = 6
Поэтому:
U(9) ≅ Z6
Сама группа:
U(9) = {1, 2, 4, 5, 7, 8}
В ней действительно 6 элементов.
Пример: U(25)
Представим 25 как:
25 = 5^2
Значит:
p = 5
n = 2
Подставляем:
|U(5^2)| = 5^2 - 5^(2-1)
Получаем:
|U(25)| = 25 - 5 = 20
Поэтому:
U(25) ≅ Z20
Ещё пример: U(27)
27 = 3^3
Значит:
p = 3
n = 3
Подставляем:
|U(3^3)| = 3^3 - 3^(3-1)
Получаем:
|U(27)| = 27 - 9 = 18
Следовательно:
U(27) ≅ Z18
Откуда берётся формула
Всего классов modulo p^n:
p^n
Необратимыми являются числа, которые делятся на p.
Таких чисел:
p^(n-1)
Поэтому количество обратимых элементов:
p^n - p^(n-1)
Главное:
p— нечётное простое число, аn— показатель степени в числеp^n.
Особый случай степеней двойки
Для нечётного простого p группа U(p^n) cyclic. Но для степеней двойки, начиная с 8, структура уже другая.
Самые маленькие случаи:
U(2) = {1}
Поэтому:
U(2) ≅ {e}
Далее:
U(4) = {1, 3}
Элемент 3 имеет порядок 2, поэтому:
U(4) ≅ Z2
А для:
n >= 3
выполняется:
U(2^n) ≅ Z_(2^(n-2)) ⊕ Z2
То есть группа уже не cyclic: она раскладывается в direct product двух cyclic components.
Пример: U(16)
Представим:
16 = 2^4
Значит:
n = 4
Подставляем в формулу:
U(2^4) ≅ Z_(2^(4-2)) ⊕ Z2
Получаем:
U(16) ≅ Z4 ⊕ Z2
Порядок этой группы:
|U(16)| = 4 · 2 = 8
И действительно:
U(16) = {1, 3, 5, 7, 9, 11, 13, 15}
содержит 8 элементов.
При этом:
U(16) not ≅ Z8
потому что в Z4 ⊕ Z2 максимальный порядок элемента равен:
lcm(4, 2) = 4
Элемента порядка 8 там нет, поэтому группа не cyclic.
Пример: U(144)
Разложим модуль:
144 = 16 · 9
Причём:
gcd(16, 9) = 1
Поэтому по Chinese Remainder Theorem:
U(144) ≅ U(16) ⊕ U(9)
Мы уже знаем:
U(16) ≅ Z4 ⊕ Z2
А так как:
9 = 3^2
и 3 — нечётное простое число:
U(9) ≅ Z6
Следовательно:
U(144)
≅
Z4 ⊕ Z2 ⊕ Z6
Порядок группы:
|U(144)| = 4 · 2 · 6 = 48
Это совпадает с:
φ(144) = 48
Почему U(144) ≅ U(105)
Ранее мы получили:
U(105) ≅ Z2 ⊕ Z4 ⊕ Z6
А для U(144):
U(144) ≅ Z4 ⊕ Z2 ⊕ Z6
Порядок компонентов в direct product не влияет на структуру:
Z4 ⊕ Z2 ⊕ Z6
≅
Z2 ⊕ Z4 ⊕ Z6
Поэтому:
U(105) ≅ U(144)
Важно:
одинакового количества элементов недостаточно для isomorphism. Здесь группы изоморфны потому, что обе раскладываются в одинаковые cyclic components.
Зачем вообще раскладывать U(n)
На первый взгляд можно спросить: зачем заменять одну группу direct product нескольких групп?
Потому что структура становится намного прозрачнее.
Сразу виден порядок группы
Из:
U(105) ≅ Z2 ⊕ Z4 ⊕ Z6
сразу получаем:
|U(105)| = 2 · 4 · 6 = 48
Это совпадает с Euler totient function:
φ(105) = 48
Легко находить возможные порядки элементов
Для элемента:
(a, b, c) ∈ Z2 ⊕ Z4 ⊕ Z6
порядок равен:
lcm(|a|, |b|, |c|)
В компонентах возможны порядки:
Z2: 1, 2
Z4: 1, 2, 4
Z6: 1, 2, 3, 6
Поэтому возможные порядки элементов U(105):
1, 2, 3, 4, 6, 12
Например, элемента порядка 24 там быть не может.
Пример: сколько элементов порядка 12 в U(105)
Мы знаем, что:
U(105) ≅ Z2 ⊕ Z4 ⊕ Z6
Изоморфизм сохраняет порядки элементов. Поэтому вместо прямой работы с U(105) можно посчитать элементы порядка 12 в более понятной группе:
Z2 ⊕ Z4 ⊕ Z6
Элемент этой группы имеет вид:
(a, b, c)
где:
a ∈ Z2
b ∈ Z4
c ∈ Z6
Порядок такого элемента равен:
|(a,b,c)| = lcm(|a|, |b|, |c|)
Нам нужно получить:
lcm(|a|, |b|, |c|) = 12
Так как:
12 = 4 · 3
среди компонентов обязательно должны появиться множители 4 и 3.
Компонент b ∈ Z4
Только компонент из Z4 может дать порядок 4.
В Z4 элементы порядка 4:
1, 3
Значит для b есть 2 варианта.
Компонент c ∈ Z6
Чтобы добавить множитель 3, элемент c должен иметь порядок 3 или 6.
В Z6:
elements of order 3: 2, 4
elements of order 6: 1, 5
Значит для c есть 4 варианта.
Оба порядка подходят:
lcm(4,3) = 12
lcm(4,6) = 12
Компонент a ∈ Z2
В Z2 есть два элемента:
0, 1
Их порядки:
|0| = 1
|1| = 2
Оба подходят, потому что ни 1, ни 2 не меняют уже полученный порядок 12:
lcm(1,4,3) = 12
lcm(2,4,3) = 12
lcm(1,4,6) = 12
lcm(2,4,6) = 12
Значит для a есть 2 варианта.
Считаем все комбинации
2 варианта для a
2 варианта для b
4 варианта для c
Поэтому:
2 · 2 · 4 = 16
Значит в:
Z2 ⊕ Z4 ⊕ Z6
ровно 16 элементов порядка 12.
А поскольку:
U(105) ≅ Z2 ⊕ Z4 ⊕ Z6
то и в U(105) тоже ровно:
16
элементов порядка 12.
Главная идея:
direct product позволяет считать порядок сложного элемента через
lcmпорядков его компонентов.
Связь с automorphisms
Ранее мы получили:
Aut(Z_n) ≅ U(n)
Поэтому:
Aut(Z_105) ≅ U(105)
А значит из структуры:
U(105) ≅ Z2 ⊕ Z4 ⊕ Z6
следует, что в группе:
Aut(Z_105)
тоже есть ровно:
16
automorphisms порядка 12.
Без direct product такую информацию было бы намного сложнее получить напрямую.
Почему условие взаимной простоты необходимо
Теорема:
U(st) ≅ U(s) ⊕ U(t)
требует:
gcd(s, t) = 1
Без этого утверждение может быть неверным.
Например:
20 = 10 · 2
но:
gcd(10, 2) = 2
Сравним размеры.
|U(20)| = φ(20) = 8
А:
|U(10)| = 4
и:
|U(2)| = 1
Поэтому:
|U(10) ⊕ U(2)| = 4 · 1 = 4
Получаем:
|U(20)| = 8
но:
|U(10) ⊕ U(2)| = 4
Группы даже имеют разный порядок, поэтому не могут быть isomorphic.
Связь с Chinese Remainder Theorem
Chinese Remainder Theorem / Китайская теорема об остатках отвечает на такой вопрос:
если известны остатки целого числа при делении на несколько взаимно простых модулей, можно ли определить его остаток при делении на произведение этих модулей?
Пусть:
gcd(s, t) = 1
То есть s и t взаимно просты.
Тогда каждый элемент modulo st однозначно соответствует паре остатков:
(x mod s, x mod t)
И наоборот: для любой пары остатков существует ровно один соответствующий класс modulo st.
Простой пример: modulo 15
Возьмём:
15 = 3 · 5
Причём:
gcd(3, 5) = 1
Допустим, мы знаем, что число x удовлетворяет:
x ≡ 1 (mod 3)
x ≡ 2 (mod 5)
Ищем число от 0 до 14, которое подходит под оба условия.
Числа, равные 1 modulo 3:
1, 4, 7, 10, 13
Из них остаток 2 modulo 5 даёт только:
7
Значит:
x ≡ 7 (mod 15)
То есть пара:
(1 mod 3, 2 mod 5)
однозначно соответствует элементу:
7 mod 15
Именно это утверждает Chinese Remainder Theorem.
Mapping
Теорема задаёт соответствие:
Ψ : Z_15 -> Z_3 × Z_5
по правилу:
Ψ(x) = (x mod 3, x mod 5)
Например:
Ψ(7) = (1, 2)
Ψ(13) = (1, 3)
При этом каждая возможная пара из:
Z_3 × Z_5
соответствует ровно одному элементу Z_15.
Поэтому на уровне rings:
Z_15 ≅ Z_3 × Z_5
В общем виде, если:
gcd(s, t) = 1
то:
Z_(st) ≅ Z_s × Z_t
Как отсюда получается U(st)
Группа:
U(n)
состоит не из всех остатков modulo n, а только из обратимых:
U(n) = {x ∈ Z_n | gcd(x, n) = 1}
Например:
U(15) = {1, 2, 4, 7, 8, 11, 13, 14}
Если число обратимо modulo st, где s и t взаимно просты, то оно обратимо отдельно modulo s и modulo t.
Поэтому mapping:
Φ(x) = (x mod s, x mod t)
переводит элементы:
U(st)
в пары из:
U(s) ⊕ U(t)
И наоборот, каждая пара обратимых остатков соответствует ровно одному обратимому элементу modulo st.
Получаем:
U(st) ≅ U(s) ⊕ U(t)
Пример с U(15)
Так как:
15 = 3 · 5
и:
gcd(3, 5) = 1
то:
U(15) ≅ U(3) ⊕ U(5)
Например:
7 ∈ U(15)
и:
Φ(7) = (1, 2)
где:
1 ∈ U(3)
2 ∈ U(5)
Пара:
(1, 2)
содержит ту же modular information, что и число:
7 mod 15
Главная мысль
Chinese Remainder Theorem позволяет заменить вычисления modulo произведения взаимно простых чисел несколькими независимыми вычислениями по меньшим модулям:
modulo st
заменяется на:
modulo s
modulo t
Поэтому вместо одной сложной группы:
U(st)
можно изучать direct product двух меньших групп:
U(s) ⊕ U(t)
Именно поэтому Chinese Remainder Theorem и direct products постоянно появляются в modular arithmetic, RSA и других криптографических конструкциях.