Мультиплікативна група кільця лишків за модулем 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 зберігаються для вищих степенів 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 група циклічна:

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

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

Китайська теорема про залишки стверджує, що якщо $\;\;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) група не циклічна. Єдиний породжувач в циклічному випадку називається первісний корінь за модулем 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	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

Посилання

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