Sistem residu tereduksi

Dalam matematika, sistem residu tereduksi modulo $n$ adalah suatu himpunan $R\subseteq \mathbb{Z}$ sedemikian sehingga:

1. $\mathrm{FPB}(r,n)=1$, untuk setiap $r\in R$.
2. tidak ada dua elemen pada $R$ yang saling kongruen modulo $n$.
3. $R$ memiliki $\phi (n)$ elemen.

dengan $\phi$ adalah fungsi totien Euler.

Sistem residu tereduksi modulo $n$ dapat dibentuk dari sistem residu lengkap modulo $n$ dengan menghilangkan semua bilangan bulat yang tidak relatif prima dengan $n$. Sebagai contoh, sistem residu lengkap modulo 10 ialah $$\{0,1,2,3,4,5,6,7,8,9\}$$ Perhatikan bahwa bilangan-bilangan yang relatif prima dengan $10$ pada himpunan tersebut hanyalah $1$, $3$, $7$, dan $9$, sehingga padanan sistem residu tereduksi modulo 10 nya ialah $\{1,3,7,9\}$. Kardinalitas dari himpunan ini dapat dicari menggunakan fungsi totien Euler, yaitu $\phi (10)=4$. Beberapa sistem residu tereduksi modulo 10 lainnya ialah

• $\{21,23,37,59\}$
• $\{-9,-7,-3,-1\}$
• $\{-27,19,41,-33\}$
• $\{11,29,53,67\}$

Sifat

\equiv k \pmod{n}</math>

sehingga dapat disimpulkan bahwa $a$ merupakan generator dari $({\mathbb{Z}}_n,+)$.}}

Lihat juga

• Grup perkalian bilangan bulat modulo
• Relasi kekongruenan
• Fungsi phi Euler
• Faktor persekutuan terbesar
• Sistem residu lengkap modulo
• Sistem residu terkecil modulo
• Aritmetika modular
• Teori bilangan
• Sistem bilangan residu

Sumber dan atribusi

Konten artikel ini diadaptasi dari Wikipedia bahasa Indonesia, revisi 27950218 (2025-10-11T00:49:21Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.