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

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

Структура

n = 1

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

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

Степені 2

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

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

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

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

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

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

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

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

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

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

\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 \;\;

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

(\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 \;.

Властивості

Порядок

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

Експонента

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

Породжувачі

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

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

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

Приклади

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

Наприклад, візьмемо n = 20. $\varphi (20)=8$ значить, що порядок $(\mathbb {Z} /20\mathbb {Z} )^{\times }$ 8 (тобто із чисел менших від 20, лише 8 є взаємно прості з ним); $\lambda (20)=4$ , отже четвертий степінь будь-якого взаємно простого до 20 числа ≡ 1 (mod 20); і по породжувачах, 19 має порядок 2, 3 — 4, і кожен елемент групи $(\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 тягне за собою те, що кожен член $\mathbb {Z} _{20}^{\times }$ ≡ 1 (mod 20).

Будова групи **(Z/nZ)^×**
$n\;$	$(\mathbb {Z} /n\mathbb {Z} )^{\times }$	$\varphi (n)\;$	$\lambda (n)\;$	породжуюча множина	$n\;$	$(\mathbb {Z} /n\mathbb {Z} )^{\times }$	$\varphi (n)\;$	$\lambda (n)\;$	породжуюча множина
2	C₁	1	1	1	33	C₂×C₁₀	20	10	10, 2
3	C₂	2	2	2	34	C₁₆	16	16	3
4	C₂	2	2	3	35	C₂×C₁₂	24	12	6, 2
5	C₄	4	4	2	36	C₂×C₆	12	6	19, 5
6	C₂	2	2	5	37	C₃₆	36	36	2
7	C₆	6	6	3	38	C₁₈	18	18	3
8	C₂×C₂	4	2	7, 3	39	C₂×C₁₂	24	12	38, 2
9	C₆	6	6	2	40	C₂×C₂×C₄	16	4	39, 11, 3
10	C₄	4	4	3	41	C₄₀	40	40	6
11	C₁₀	10	10	2	42	C₂×C₆	12	6	13, 5
12	C₂×C₂	4	2	5, 7	43	C₄₂	42	42	3
13	C₁₂	12	12	2	44	C₂×C₁₀	20	10	43, 3
14	C₆	6	6	3	45	C₂×C₁₂	24	12	44, 2
15	C₂×C₄	8	4	14, 2	46	C₂₂	22	22	5
16	C₂×C₄	8	4	15, 3	47	C₄₆	46	46	5
17	C₁₆	16	16	3	48	C₂×C₂×C₄	16	4	47, 7, 5
18	C₆	6	6	5	49	C₄₂	42	42	3
19	C₁₈	18	18	2	50	C₂₀	20	20	3
20	C₂×C₄	8	4	19, 3	51	C₂×C₁₆	32	16	50, 5
21	C₂×C₆	12	6	20, 2	52	C₂×C₁₂	24	12	51, 7
22	C₁₀	10	10	7	53	C₅₂	52	52	2
23	C₂₂	22	22	5	54	C₁₈	18	18	5
24	C₂×C₂×C₂	8	2	5, 7, 13	55	C₂×C₂₀	40	20	21, 2
25	C₂₀	20	20	2	56	C₂×C₂×C₆	24	6	13, 29, 3
26	C₁₂	12	12	7	57	C₂×C₁₈	36	18	20, 2
27	C₁₈	18	18	2	58	C₂₈	28	28	3
28	C₂×C₆	12	6	13, 3	59	C₅₈	58	58	2
29	C₂₈	28	28	2	60	C₂×C₂×C₄	16	4	11, 19, 7
30	C₂×C₄	8	4	11, 7	61	C₆₀	60	60	2
31	C₃₀	30	30	3	62	C₃₀	30	30	3
32	C₂×C₈	16	8	31, 3	63	C₆×C₆	36	6	2, 5

Примітки

↑ Gauss, DA, arts. 90–91
↑ Gauss, DA, arts.52–56, 82–89
↑ Riesel covers all of this. pp. 267–275
↑ Weisstein, Eric W. Modulo Multiplication Group(англ.) на сайті Wolfram MathWorld.
↑ Primitive root [Архівовано 18 березня 2014 у Wayback Machine.], Encyclopedia of Mathematics

Посилання

Disquisitiones Arithmeticae (лат. Дослідження чисел) перекладена з латині Гауса на англійську і німецьку. Німецькомовне видання містить всі його папери з теорії чисел: доведення квадратичної взаємності, визначення знаку суми Гауса, вивчення біквадратичної взаємності і неопубліковані замітки.

Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English) (1986), Disquisitiones Arithemeticae (Second, corrected edition), New York: Springer Science+Business Media, ISBN 0-387-96254-9

Gauss, Carl Friedrich; Maser, H. (translator into German) (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition), New York: Chelsea, ISBN 0-8284-0191-8

Riesel, Hans (1994), Prime Numbers and Computer Methods for Factorization (second edition), Boston: Birkhäuser, ISBN 0-8176-3743-5

Calculator by Shing Hing Man

[1] Gauss, DA, arts. 90–91

[2] Gauss, DA, arts.52–56, 82–89

[3] Riesel covers all of this. pp. 267–275

[4] Weisstein, Eric W. Modulo Multiplication Group(англ.) на сайті Wolfram MathWorld.

[5] Primitive root [Архівовано 18 березня 2014 у Wayback Machine.], Encyclopedia of Mathematics

[1]

[2]

[3]

[4]

[5]

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

Зміст

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

Форма запису