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

В модульній арифметиці, множина класів рівності чисел, що є взаємно простими до модуля n утворюють групу над операцією множення відому як мультиплікативна група кільця лишків за модулем n (Шаблон:Lang-en). В теорії кілець, відгалуженні абстрактної алгебри, її описують як групу оборотних елементів кільця лишків за модулем 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-адичне число|Шаблон:Math-адичними числами]] у випадку $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_{\phi (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 }|=\phi (n).$ Це добуток порядків циклічних груп у прямому добутку.

Експонента

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

Породжувачі

$(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$ циклічна тоді і тільки тоді, якщо $\phi (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}. Породжувачі вказані в порядку прямих множників (Шаблон:Lang-en).

Наприклад, візьмемо n = 20. $\phi (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 }$	$\phi (n)$	$\lambda (n)$	породжуюча множина		$n$	$(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$	$\phi (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 (Шаблон:Lang-la) перекладена з латині Гауса на англійську і німецьку. Німецькомовне видання містить всі його папери з теорії чисел: доведення квадратичної взаємності, визначення знаку суми Гауса, вивчення біквадратичної взаємності і неопубліковані замітки.

• Шаблон:Citation

• Шаблон:Citation

• Шаблон:Citation

• Calculator by Shing Hing Man