Мультиплікативна група кільця лишків за модулем 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(an) = gcd(bn).

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

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

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

Форма запису[ред. | ред. код]

Кільце лишків за модулем n позначають   або    (тобто, кільце цілих за модулем ідеала nZ = (n), який складається з чисел кратних n), або як (хоча останню можна сплутати з p-адичними числами у випадку ). Залежно від автора цю групу оборотних елементів записують як         (німецькою Einheit = оборотний елемент) або щось інше в цьому ключі. Ця стаття використовує

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

Структура[ред. | ред. код]

n = 1[ред. | ред. код]

Будь-які два цілих числа рівні за модулем 1, тобто існує лише один клас рівності. Кожне ціле взаємно просте до 1. Отже єдиний клас рівності за модулем 1 взаємно простий із модулем, так тривіально. Отримуємо, що φ(1) = 1. Через те, що перший степінь будь-якого цілого числа рівний 1 за модулем 1, λ(1) також 1.

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

Степені 2[ред. | ред. код]

За модулем 2 є лише один клас взаємної рівності, 1, отже тривіальна група (з одним елементом).

За модулем 4 є два взаємно прості класи рівності, 1 і 3, отже циклічна група з двома елементами.

За модулем 8 є чотири взаємно прості класи, 1, 3, 5 і 7. Квадрат кожного з них дорівнює 1, отже 4-група Клейна.

За модулем 16, присутні вісім взаємно простих класів 1, 3, 5, 7, 9, 11, 13 і 15. — підгрупа 2-кручення (тобто квадрат кожного елемента дорівнює 1), отже не циклічна. Степені числа 3 утворюють — підгрупа порядку 4, як і степені 5,   Таким чином

Властивості, що показали приклади з 8 і 16 зберігаються[1] для вищих степенів 2k, k > 2: — підгрупа 2-кручення (тому не циклічна) і степені 3 це підгрупи порядку 2k − 2, отже

Степені непарних простих[ред. | ред. код]

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

Складені числа[ред. | ред. код]

Китайська теорема про залишки стверджує, що [3] якщо тоді кільце є прямим добутком кілець відповідно до степенів простих множників числа:

Подібно, група оборотних елементів є прямим добутком відповідно до степеня простого множника:

Властивості[ред. | ред. код]

Порядок[ред. | ред. код]

Порядок отримуємо через функцію Ейлера: Це добуток порядків циклічних груп у прямому добутку.

Експонента[ред. | ред. код]

Експонента отримується функцією Кармайкла найменше спільне кратне порядків циклічних груп. Тобто, для заданого n, для будь-якого a взаємно простого до n і — найменше таке число.

Породжувачі[ред. | ред. код]

циклічна тоді і тільки тоді, якщо Це випадок коли n це 2, 4, pk або 2pk, де p непарне просте і k > 0. для всіх інших значень n (окрім 1) група не циклічна.[4][5] Єдиний породжувач в циклічному випадку називається первісний корінь за модулем n.

З того, що всі n ≤ 7 циклічні, інакше можна це сказати так: Якщо n < 8 тоді має первісний корінь. Якщо n ≥ 8 тоді має первіісний корінь якщо тільки n не ділиться на 4 або на два відмінних простих числа.

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

Приклади[ред. | ред. код]

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

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

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

Будова групи (Z/nZ)×
породжуюча множина   породжуюча множина
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 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