Мультиплікативна група кільця лишків за модулем n

В модульній арифметиці, множина класів рівності чисел, що є взаємно простими до модуля n утворюють групу над операцією множення відому як мультиплікативна група кільця лишків за модулем n (англ. Multiplicative group of integers modulo n, primitive residue classes modulo n). В теорії кілець, відгалуженні абстрактної алгебри, її описують як групу оборотних елементів кільця лишків за модулем n. (Оборотний елемент, тобто такий, що має обернений за модулем.)

Ця група фундаментальна в теорії чисел. Вона знайшла застосування в криптографії, факторизації цілих чисел і перевірці на простоту. Наприклад, через знаходження порядку (тобто розміру) групи, можна визначити чи просте n: n просте тоді і тільки тоді, якщо порядок становить n − 1.

Аксіоми групи

Просто показати, що для множення класи рівності за модулем n, які взаємно прості до n, задовольняють аксіомам абелевої групи.

З a ≡ b (mod n) випливає, що gcd(a, n) = gcd(b, n).

Тому що gcd(a, n) = 1 і gcd(b, n) = 1 призводить до gcd(ab, n) = 1, множина класів взаємно простих до n замкнена щодо множення.

Природне відображення з множини цілих чисел в класи рівності за модулем n, що переводить ціле число в його клас рівності за модулем n зберігає добуток. Це призводить до того, що клас, який містить 1 є єдиним нейтральним елементом щодо множення, асоціативний і комутативний закони також виконуються. Насправді це гомоморфізм кілець.

Для заданого a, gcd(a, n) = 1, знаходження x, що задовольняє ax ≡ 1 (mod n) це те саме, що розв'язання ax + ny = 1, що можна зробити через рівняння Безу. Знайдений x матиме властивість, що  gcd(x, n) = 1.

Форма запису

Кільце лишків за модулем n позначають ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$  або  ${\displaystyle \mathbb {Z} /(n)}$   (тобто, кільце цілих за модулем ідеала nZ = (n), який складається з чисел кратних n), або як ${\displaystyle \mathbb {Z} _{n}}$ (хоча останню можна сплутати з p-адичними числами у випадку ${\displaystyle n=p}$). Залежно від автора цю групу оборотних елементів записують як ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*},}$   ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times },}$   ${\displaystyle U(\mathbb {Z} /n\mathbb {Z} ),}$   ${\displaystyle E(\mathbb {Z} /n\mathbb {Z} )}$   (німецькою Einheit = оборотний елемент) або щось інше в цьому ключі. Ця стаття використовує ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }.}$

Запис ${\displaystyle C_{n}}$ відповідає циклічній групі порядку n.

Структура

n = 1

Будь-які два цілих числа рівні за модулем 1, тобто існує лише один клас рівності. Кожне ціле взаємно просте до 1. Отже єдиний клас рівності за модулем 1 взаємно простий із модулем, так ${\displaystyle (\mathbb {Z} /1\,\mathbb {Z} )^{\times }\cong C_{1}}$ тривіально. Отримуємо, що φ(1) = 1. Через те, що перший степінь будь-якого цілого числа рівний 1 за модулем 1, λ(1) також 1.

Через свою простоту, випадок рівності за модулем 1 зазвичай опускають. Наприклад, теорема «${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ циклічна тоді і тільки тоді, коли φ(n) = λ(n)» неявно містить випадок n = 1, тоді як твердження теореми Ґауса «${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ тоді і тоді, коли n = 2, 4, будь-який степінь непарного простого числа або двічі будь-який степінь простого числа,» явно виключає 1.

Степені 2

За модулем 2 є лише один клас взаємної рівності, 1, отже ${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{\times }\cong C_{1}}$ — тривіальна група (з одним елементом).

За модулем 4 є два взаємно прості класи рівності, 1 і 3, отже ${\displaystyle (\mathbb {Z} /4\mathbb {Z} )^{\times }\cong C_{2},}$ циклічна група з двома елементами.

За модулем 8 є чотири взаємно прості класи, 1, 3, 5 і 7. Квадрат кожного з них дорівнює 1, отже ${\displaystyle (\mathbb {Z} /8\mathbb {Z} )^{\times }\cong C_{2}\times C_{2},}$ 4-група Клейна.

За модулем 16, присутні вісім взаємно простих класів 1, 3, 5, 7, 9, 11, 13 і 15. ${\displaystyle \{\pm 1,\pm 7\}\cong C_{2}\times C_{2},}$ — підгрупа 2-кручення (тобто квадрат кожного елемента дорівнює 1), отже ${\displaystyle (\mathbb {Z} /16\mathbb {Z} )^{\times }}$ не циклічна. Степені числа 3 утворюють ${\displaystyle \{1,3,9,11\}}$ — підгрупа порядку 4, як і степені 5, ${\displaystyle \{1,5,9,13\}.}$   Таким чином ${\displaystyle (\mathbb {Z} /16\mathbb {Z} )^{\times }\cong C_{2}\times C_{4}.}$

Властивості, що показали приклади з 8 і 16 зберігаються^[1] для вищих степенів 2^k, k > 2: ${\displaystyle \{\pm 1,2^{k-1}\pm 1\}\cong C_{2}\times C_{2},}$ — підгрупа 2-кручення (тому ${\displaystyle (\mathbb {Z} /2^{k}\mathbb {Z} )^{\times }}$ не циклічна) і степені 3 це підгрупи порядку 2^{k − 2}, отже ${\displaystyle (\mathbb {Z} /2^{k}\mathbb {Z} )^{\times }\cong C_{2}\times C_{2^{k-2}}.}$

Степені непарних простих

Для степенів непарних простих чисел p^k група циклічна:^[2]

${\displaystyle \;\;(\mathbb {Z} /p^{k}\mathbb {Z} )^{\times }\cong C_{p^{k-1}(p-1)}\cong C_{\varphi (p^{k})}.}$

Складені числа

Китайська теорема про залишки стверджує, що ^[3] якщо ${\displaystyle \;\;n=p_{1}^{k_{1}}p_{2}^{k_{2}}p_{3}^{k_{3}}\dots ,\;}$ тоді кільце ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ є прямим добутком кілець відповідно до степенів простих множників числа:

${\displaystyle \mathbb {Z} /n\mathbb {Z} \cong \mathbb {Z} /{p_{1}^{k_{1}}}\mathbb {Z} \;\times \;\mathbb {Z} /{p_{2}^{k_{2}}}\mathbb {Z} \;\times \;\mathbb {Z} /{p_{3}^{k_{3}}}\mathbb {Z} \dots \;\;}$

Подібно, група оборотних елементів ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ є прямим добутком відповідно до степеня простого множника:

${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }\cong (\mathbb {Z} /{p_{1}^{k_{1}}}\mathbb {Z} )^{\times }\times (\mathbb {Z} /{p_{2}^{k_{2}}}\mathbb {Z} )^{\times }\times (\mathbb {Z} /{p_{3}^{k_{3}}}\mathbb {Z} )^{\times }\dots \;.}$

Властивості

Порядок

Порядок отримуємо через функцію Ейлера: ${\displaystyle |(\mathbb {Z} /n\mathbb {Z} )^{\times }|=\varphi (n).}$ Це добуток порядків циклічних груп у прямому добутку.

Експонента

Експонента отримується функцією Кармайкла ${\displaystyle \lambda (n),}$ — найменше спільне кратне порядків циклічних груп. Тобто, для заданого n, ${\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}},}$ для будь-якого a взаємно простого до n і ${\displaystyle \lambda (n)}$ — найменше таке число.

Породжувачі

${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ циклічна тоді і тільки тоді, якщо ${\displaystyle \varphi (n)=\lambda (n).}$ Це випадок коли n це 2, 4, p^k або 2p^k, де p непарне просте і k > 0. для всіх інших значень n (окрім 1) група не циклічна.^[4][5] Єдиний породжувач в циклічному випадку називається первісний корінь за модулем n.

З того, що всі ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times },}$ n ≤ 7 циклічні, інакше можна це сказати так: Якщо n < 8 тоді ${\displaystyle \;(\mathbb {Z} /n\mathbb {Z} )^{\times }}$ має первісний корінь. Якщо n ≥ 8 тоді ${\displaystyle \;(\mathbb {Z} /n\mathbb {Z} )^{\times }}$ має первіісний корінь якщо тільки n не ділиться на 4 або на два відмінних простих числа.

В загальному випадку існує лише один породжувач для кожного циклічного прямого множника.

Приклади

Ця таблиця показує циклічну декомпозицію ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ і породжуючу множину для малих значень n. Породжуюча множина не єдина; наприклад для модуля 16 підходять і {−1, 3}, і {−1, 5}. Породжувачі вказані в порядку прямих множників (англ. direct factor).

Наприклад, візьмемо n = 20. ${\displaystyle \varphi (20)=8}$ значить, що порядок ${\displaystyle (\mathbb {Z} /20\mathbb {Z} )^{\times }}$ 8 (тобто із чисел менших від 20, лише 8 є взаємно прості з ним); ${\displaystyle \lambda (20)=4}$, отже четвертий степінь будь-якого взаємно простого до 20 числа ≡ 1 (mod 20); і по породжувачах, 19 має порядок 2, 3 — 4, і кожен елемент групи ${\displaystyle (\mathbb {Z} /20\mathbb {Z} )^{\times }}$ має форму 19^a × 3^b, де a — 0 або 1 і b — 0, 1, 2 або 3.

Степенями 19 є {±1}, а степені 3 — {3, 9, 7, 1}. Степені 3 помножені на ±1 складають всі числа менші 20 і взаємно прості з ним. Факт того, що порядком 19 є 2 і порядок 3 — 4 тягне за собою те, що кожен член ${\displaystyle \mathbb {Z} _{20}^{\times }}$ ≡ 1 (mod 20).

Будова групи (Z/nZ)^×

${\displaystyle n\;}$	${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$	${\displaystyle \varphi (n)\;}$	${\displaystyle \lambda (n)\;}$	породжуюча множина		${\displaystyle n\;}$	${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$	${\displaystyle \varphi (n)\;}$	${\displaystyle \lambda (n)\;}$	породжуюча множина
2	C1	1	1	1		33	C2×C10	20	10	10, 2
3	C2	2	2	2		34	C16	16	16	3
4	C2	2	2	3		35	C2×C12	24	12	6, 2
5	C4	4	4	2		36	C2×C6	12	6	19, 5
6	C2	2	2	5		37	C36	36	36	2
7	C6	6	6	3		38	C18	18	18	3
8	C2×C2	4	2	7, 3		39	C2×C12	24	12	38, 2
9	C6	6	6	2		40	C2×C2×C4	16	4	39, 11, 3
10	C4	4	4	3		41	C40	40	40	6
11	C10	10	10	2		42	C2×C6	12	6	13, 5
12	C2×C2	4	2	5, 7		43	C42	42	42	3
13	C12	12	12	2		44	C2×C10	20	10	43, 3
14	C6	6	6	3		45	C2×C12	24	12	44, 2
15	C2×C4	8	4	14, 2		46	C22	22	22	5
16	C2×C4	8	4	15, 3		47	C46	46	46	5
17	C16	16	16	3		48	C2×C2×C4	16	4	47, 7, 5
18	C6	6	6	5		49	C42	42	42	3
19	C18	18	18	2		50	C20	20	20	3
20	C2×C4	8	4	19, 3		51	C2×C16	32	16	50, 5
21	C2×C6	12	6	20, 2		52	C2×C12	24	12	51, 7
22	C10	10	10	7		53	C52	52	52	2
23	C22	22	22	5		54	C18	18	18	5
24	C2×C2×C2	8	2	5, 7, 13		55	C2×C20	40	20	21, 2
25	C20	20	20	2		56	C2×C2×C6	24	6	13, 29, 3
26	C12	12	12	7		57	C2×C18	36	18	20, 2
27	C18	18	18	2		58	C28	28	28	3
28	C2×C6	12	6	13, 3		59	C58	58	58	2
29	C28	28	28	2		60	C2×C2×C4	16	4	11, 19, 7
30	C2×C4	8	4	11, 7		61	C60	60	60	2
31	C30	30	30	3		62	C30	30	30	3
32	C2×C8	16	8	31, 3		63	C6×C6	36	6	2, 5