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

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

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

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

Примітки

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

Посилання

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

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

• 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 

• Riesel, Hans (1994), Prime Numbers and Computer Methods for Factorization (second edition), Boston: Birkhäuser, ISBN 

• by Shing Hing Man