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