Grup perkalian bilangan bulat modulo $n$

Dalam aritmetika modular, himpunan semua bilangan asli yang kurang dari $n$ dan relatif prima dengan $n$ membentuk grup terhadap operasi perkalian modulo $n$ , yang dikenal sebagai grup perkalian bilangan bulat modulo $n$ . Hal ini ekuivalen dengan memandang setiap elemen dari grup ini sebagai residu (atau kelas ekuivalensi) modulo $n$ yang relatif prima dengan $n$ . Akibatnya, nama lain dari grup ini ialah kelas residu primitif modulo $n$ .

Dalam teori gelanggang, salah satu cabang ilmu dari aljabar abstrak, grup ini dideskripsikan sebagai grup unit-unit dari gelanggang bilangan bulat modulo $n$ . Kata unit disini merujuk kepada elemen yang memiliki invers perkalian, yang pada gelanggang ini, ialah elemen-elemen yang relatif prima dengan $n$ .

Grup ini, yang biasa ditulis sebagai $\left(\mathbb {Z} /n\mathbb {Z} ,\,\times \right)$ atau $\left(\mathbb {Z} /n\mathbb {Z} \right)^{\times }$ , merupakan grup yang fundamental dalam teori bilangan. Grup ini digunakan dalam kriptografi, faktorisasi prima, dan pengujian keprimaan. Grup ini merupakan grup abelian berhingga yang ordenya diperoleh melalui fungsi phi Euler: $\left|{\dfrac {\mathbb {Z} }{n\mathbb {Z} }}\right|=\varphi (n)$ dengan $\left|H\right|$ menyatakan kardinalitas dari himpunan $H$ . Jika $n$ merupakan bilangan prima, maka grup ini merupakan grup siklik, dan secara umum, struktur dari grup ini mudah untuk dideskripsikan, tetapi belum diketahui apakan terdapat rumus sederhana untuk menentukan generator dari grup ini.

Notasi

Himpunan dari (kelas-kelas kekongruenan) bilangan bulat modulo $n$ terhadap operasi penjumlahan dan perkalian merupakan gelanggang. Himpunan ini dinotasikan dengan $\mathbb {Z} /n\mathbb {Z}$ atau $\mathbb {Z} /(n)$ .^{[note 1]} Di luar teori bilangan, seringkali digunakan notasi $\mathbb {Z} _{n}$ yang lebih sederhana, walau mungkin dikelirukan dengan bilangan bulat $p$ -adik ketika $n$ merupakan bilangan prima.

Grup perkalian bilangan bulat modulo $n$ —yaitu grup dari semua unit pada gelanggng ini—dapat ditulis sebagai $\left(\mathbb {Z} /n\mathbb {Z} \right)^{\times }$ , $\left(\mathbb {Z} /n\mathbb {Z} \right)^{\ast }$ , $\operatorname {U} (\mathbb {Z} /n\mathbb {Z} )$ , atau notasi serupa. Artikel ini akan menggunakan notasi $\left(\mathbb {Z} /n\mathbb {Z} \right)^{\times }$ .

Struktur grup

Misalkan $N$ menyatakan himpunan kelas-kelas kekongruenan modulo $n$ yang relatif prima dengan $n$ . Himpunan $N$ memenuhi semua aksioma dari grup abelian terhadap operasi perkalian modulo $n$ .

Himpunan tak kosong —

Perhatikan bahwa $\left[1\right]_{n}\in N$ , sebab $\operatorname {FPB} (1,\,n)=1$ untuk setiap $n\in \mathbb {N}$ . Akibatnya, $N$ bukanlah himpunan kosong.

Operasi biner (terdefinisi dengan jelas) —

Diambil sembarang $n\in \mathbb {N}$ serta sembarang $\left[a\right]_{n}$ , $\left[b\right]_{n}\in N$ . Bilangan bulat $a$ akan relatif prima dengan $n$ jika dan hanya jika $\operatorname {FPB} (a,\,n)=1$ . Jika bilangan bulat $a$ dan $b$ berada pada kelas kekongruenan yang sama (yaitu $a\equiv b{\pmod {n}}$ ), maka $\operatorname {FPB} (a,\,n)=\operatorname {FPB} (b,\,n)$ . Akibatnya, jika salah satu bersifat relatif prima dengan $n$ , maka begitu juga dengan bilangan satunya, sehingga konsep "kelas-kelas kekongruenan modulo $n$ yang relatif prima dengan $n$ " merupakan objek yang terdefinisi dengan jelas.

Operasi biner (tertutup) —

Diambil sembarang $n\in \mathbb {N}$ dan sembarang $\left[a\right]_{n}$ , $\left[b\right]_{n}\in N$ . Akan dibuktikan bahwa $\left[ab\right]_{n}\in N$ menggunakan pembuktian melalui kontradiksi. Dengan kata lain, akan ditunjukkan bahwa $\operatorname {FPB} (ab,\,n)=1$ .

Misalkan $d=\operatorname {FPB} (ab,\,n)$ . Berdasarkan definisi dari FPB, maka

$d\mid n$ , dan
$d\mid ab$

Andaikan $d\neq 1$ , maka $d\geq 2$ . Tanpa mengurangi keumuman, diasumsikan bahwa $d$ merupakan bilangan prima.^{[note 2]} Berdasarkan lema Euclides, maka terdapat 2 kasus yang dapat terjadi:

Jika $d\mid a$ , maka $d$ merupakan faktor persekutuan dari $a$ dan $n$ . Akan tetapi, faktor persekutuan terbesar dari $a$ dan $n$ ialah 1, sehingga setiap bilangan yang lebih dari 1 bukan merupakan faktor persekutuan dari $a$ dan $n$ .
Jika $d\mid b$ , maka $d$ merupakan faktor persekutuan dari $b$ dan $n$ . Akan tetapi, faktor persekutuan terbesar dari $b$ dan $n$ ialah 1, sehingga setiap bilangan yang lebih dari 1 bukan merupakan faktor persekutuan dari $b$ dan $n$ .

Oleh karena terjadi kontradiksi pada kedua kasus di atas, maka asumsi di awal—bahwa nilai $d\neq 1$ — bernilai salah, sehingga dapat disimpulkan bahwa $\operatorname {FPB} (ab,\,n)=d=1$ . Berdasarkan definisi dari himpunan $N$ , maka terbukti bahwa $\left[ab\right]_{n}\in N$ .

Sifat komutatif —

Diambil sembarang $n\in \mathbb {N}$ dan sembarang $\left[a\right]_{n}$ , $\left[b\right]_{n}\in N$ . Berdasarkan definisi perkalian pada modulo $n$ , maka $\left[a\right]_{n}\left[b\right]_{n}=\left[ab\right]_{n}=\left[ba\right]_{n}=\left[b\right]_{n}\left[a\right]_{n}$ Pada persamaan kedua, digunakan informasi bahwa operasi perkalian pada himpunan bilangan bulat bersifat komutatif.

Sifat asosiatif —

Diambil sembarang $n\in \mathbb {N}$ dan sembarang $\left[a\right]_{n}$ , $\left[b\right]_{n}$ , $\left[c\right]_{n}\in N$ . Berdasarkan definisi perkalian pada modulo $n$ , maka ${\begin{aligned}\left(\left[a\right]_{n}\left[b\right]_{n}\right)\left[c\right]_{n}&=\left[ab\right]_{n}\left[c\right]_{n}\\&=\left[(ab)c\right]_{n}\\&=\left[a(bc)\right]_{n}\\&=\left[a\right]_{n}\left[bc\right]_{n}\\&=\left[a\right]_{n}\left(\left[b\right]_{n}\left[c\right]_{n}\right)\end{aligned}}$ Pada baris ketiga, digunakan informasi bahwa operasi perkalian pada himpunan bilangan bulat bersifat asosiatif.

Kewujudan elemen identitas —

Perhatikan bahwa $\left[1\right]_{n}\in N$ , sebab $\operatorname {FPB} (1,\,n)=1$ untuk setiap $n\in \mathbb {N}$ . Akibatnya, berlaku ${\begin{aligned}\left[1\right]_{n}\left[k\right]_{n}&=\left[1\cdot k\right]_{n}\\&=\left[k\right]_{n}\\\\\left[k\right]_{n}\left[1\right]_{n}&=\left[k\cdot 1\right]_{n}\\&=\left[k\right]_{n}\end{aligned}}$ untuk setiap $\left[k\right]_{n}\in N$ .

Kewujudan elemen invers —

Diambil sembarang $n\in \mathbb {N}$ dan sembarang $a\in \mathbb {Z}$ . Invers perkalian dari $a$ pada modulo $n$ ialah bilangan bulat $p$ yang memenuhi $ap\equiv 1{\pmod {n}}$

Bilangan $p$ terjamin kewujudannya jika $a$ relatif prima dengan $n$ , sebab berdasarkan identitas Bézout, maka terdapat suatu $p$ , $q\in \mathbb {Z}$ sedemikian sehingga $ap+nq=\operatorname {FPB} (a,\,n)=1$ Dengan kata lain, jika $\left[a\right]_{n}\in N$ , maka invers perkalian dari $a$ terjamin ada. Lebih lanjut, persamaan $ap+nq=1$ mengakibatkan bahwa $p$ relatif prima dengan $n$ , sehingga $\left[p\right]_{n}\in N$ .

Lihat juga

Pemfaktoran kurva eliptik Lenstra

Catatan

↑ Kedua notasi ini merujuk kepada proses pengambilan hasil bagi dari bilangan bulat modulo ideal yang berisi kelipatan dari $n$ , ditulis sebagai $n\mathbb {Z}$ atau $(n)$ .
↑ Jika $d$ merupakan bilangan komposit, maka terdapat suatu bilangan prima $p$ yang habis membagi $d$ . Oleh karena operasi keterbagian merupakan relasi transitif, maka $p\mid ab$ dan $p\mid n$ .

Referensi

Disquisitiones Arithmeticae telah diterjemahkan dari bahasa Latin Ciceronian Gauss ke dalam bahasa Inggris dan Jerman. Edisi Jerman mencakup semua paper teori bilangan miliknya: semua bukti dari timbal balik kuadratik, penentuan tanda dari jumlah Gauss, penyelidikan timbal balik bikuadratik, serta catatan yang tidak diterbitkan.

Gauss, Carl Friedrich (1986), Disquisitiones Arithemeticae (terjemahan bahasa Inggris, edisi kedua, telah diperbaiki), diterjemahkan oleh Clarke, Arthur A., New York: Springer, ISBN 0-387-96254-9
Gauss, Carl Friedrich (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & paper lainnya dalam teori bilangan) (terjemahan Jerman, edisi kedua), diterjemahkan oleh Maser, H., New York: Chelsea, ISBN 0-8284-0191-8
Riesel, Hans (1994), Prime Numbers and Computer Methods for Factorization [Bilangan Prima dan Metode Komputer untuk Pemfaktoran] (dalam bahasa Inggris) (Edisi kedua), Boston: Birkhäuser, ISBN 978-0-8176-3743-9
Vinogradov, I. M. (2003), "§ VI Primitive roots and indices", Elements of Number Theory [Elemen dari Teori Bilangan] (dalam bahasa Inggris), Mineola, NY: Dover Publications, hlm. 105–121, ISBN 978-0-486-49530-9

Pranala luar

(Inggris) Weisstein, Eric W. "Grup Multiplikatif Modulo n". MathWorld.
(Inggris) Weisstein, Eric W. "Akar Primitif". MathWorld.
Alat berbasis situs web untuk menghitung tabel grup secara interaktif oleh John Jones

[1] Kedua notasi ini merujuk kepada proses pengambilan hasil bagi dari bilangan bulat modulo ideal yang berisi kelipatan dari $n$ , ditulis sebagai $n\mathbb {Z}$ atau $(n)$ .

[2] Jika $d$ merupakan bilangan komposit, maka terdapat suatu bilangan prima $p$ yang habis membagi $d$ . Oleh karena operasi keterbagian merupakan relasi transitif, maka $p\mid ab$ dan $p\mid n$ .

[note 1]

[note 2]