Sistem residu tereduksi 📖 Wikipedia

Diambil sembarang bilangan asli ${\displaystyle n}$ dan sembarang bilangan pada sistem residu tereduksi modulo ${\displaystyle n}$, misalnya ${\displaystyle a}$. Berdasarkan definisi dari sistem residu tereduksi, maka ${\displaystyle \operatorname {FPB} (a,\,n)=1}$. Berdasarkan identitas Bézout, maka terdapat suatu bilangan bulat ${\displaystyle p}$ dan ${\displaystyle q}$ sedemikian sehingga $${\displaystyle ap+nq=\operatorname {FPB} (a,\,n)=1}$$ yang ekuivalen dengan $${\displaystyle ap\equiv 1{\pmod {n}}}$$

Perhatikan bahwa setiap elemen ${\displaystyle k\in \left(\mathbb {Z} _{n},\,+\right)}$ akan kongruen dengan ${\displaystyle 1\cdot k}$. Akibatnya, $${\displaystyle {\begin{aligned}ap&\equiv 1&{\pmod {n}}\\ap\cdot k&\equiv 1\cdot k&{\pmod {n}}\\a(pk)&\equiv k&{\pmod {n}}\end{aligned}}}$$ Dengan kata lain, elemen ${\displaystyle k}$ dapat dinyatakan sebagai penjumlahan berulang dari bilangan ${\displaystyle a}$ sebanyak ${\displaystyle p\times k}$ kali $${\displaystyle \underbrace {a+a+a+a+\ldots +a} _{p\times k\;{\text{kali}}}\equiv k{\pmod {n}}}$$ sehingga dapat disimpulkan bahwa ${\displaystyle a}$ merupakan generator dari ${\displaystyle \left(\mathbb {Z} _{n},\,+\right)}$.

Lihat halaman Grup perkalian bilangan bulat modulo ${\displaystyle n}$.

Diambil sembarang bilangan asli ${\displaystyle n}$ dan sembarang bilangan bulat ${\displaystyle a}$ yang relatif prima dengan ${\displaystyle n}$. Didefinisikan fungsi ${\displaystyle f:X\to aX}$ dengan definisi ${\displaystyle f(x)=ax}$

1. Oleh karena ${\displaystyle \operatorname {FPB} (a,\,n)=1}$ dan ${\displaystyle \operatorname {FPB} (x_{i},\,n)=1}$ untuk setiap ${\displaystyle i\in \left\{1,\,2,\,3,\,\ldots ,\,\varphi (n)\right\}}$, maka ${\displaystyle \operatorname {FPB} (ax_{i},\,n)=1}$.
2. Telah dibuktikan sebelumnya bahwa fungsi ${\displaystyle f}$ bersifat injektif. Dengan kata lain, setiap pasangan bilangan bulat ${\displaystyle p}$ dan ${\displaystyle q}$ yang memenuhi ${\displaystyle ap\equiv aq{\pmod {n}}}$ akan berlaku ${\displaystyle p\equiv q{\pmod {n}}}$. Dengan menggunakan kontraposisi, maka setiap pasang elemen yang tidak kongruen dalam modulo ${\displaystyle n}$ tetap tidak akan kongruen meskipun keduanya dikalikan dengan ${\displaystyle a}$. Oleh karena ${\displaystyle X}$ merupakan sistem residu tereduksi, maka setiap pasang elemen pada ${\displaystyle X}$ tidak akan kongruen satu sama lain. Akibatnya, setiap pasang elemen pada ${\displaystyle aX}$ juga demikian.
3. Untuk setiap elemen ${\displaystyle ax_{i}\in aX}$, terdapat ${\displaystyle x_{i}\in X}$ sedemikian sehingga ${\displaystyle f(x_{i})=ax_{i}}$. Akibatnya, fungsi ${\displaystyle f}$ bersifat surjektif. Oleh karena ${\displaystyle f}$ merupakan bijeksi antara ${\displaystyle X}$ dengan ${\displaystyle aX}$, maka ${\displaystyle aX}$ memiliki jumlah elemen yang sama dengan ${\displaystyle X}$, yaitu ${\displaystyle \varphi (n)}$ elemen.

Diambil sembarang bilangan asli ${\displaystyle n>2}$. Perhatikan bahwa ${\displaystyle \operatorname {FPB} (n-1,\,n)=1}$ untuk setiap ${\displaystyle n\in \mathbb {N} }$, sehingga ${\displaystyle n-1\in X}$. Dengan kata lain, ${\displaystyle X}$ bukanlah himpunan kosong.

Berdasarkan sifat 3, maka himpunan $${\displaystyle (n-1)X=\left\{(n-1)x_{1},\,(n-1)x_{2},\,(n-1)x_{3},\,\ldots ,\,(n-1)x_{\varphi (n)}\right\}}$$ juga merupakan sistem residu tereduksi modulo ${\displaystyle n}$. Oleh karena setiap elemen pada ${\displaystyle X}$ kongruen dengan tepat satu elemen pada ${\displaystyle (n-1)X}$, maka $${\displaystyle {\begin{aligned}\sum _{x\,\in \,X}x&\equiv \sum _{x\,\in \,(n-1)X}x&{\pmod {n}}\\\sum _{i\,=\,1}^{\varphi (n)}x_{i}&\equiv \sum _{i\,=\,1}^{\varphi (n)}(n-1)x_{i}&{\pmod {n}}\\2\sum _{i\,=\,1}^{\varphi (n)}x_{i}&\equiv n\sum _{i\,=\,1}^{\varphi (n)}x_{i}&{\pmod {n}}\\2\sum _{i\,=\,1}^{\varphi (n)}x_{i}&\equiv 0&{\pmod {n}}\\\sum _{i\,=\,1}^{\varphi (n)}x_{i}&\equiv 0&{\pmod {n}}\end{aligned}}}$$

Perhatikan bahwa kekongruenan terakhir diperoleh sebab ${\displaystyle n>2}$, yang mengakibatkan bahwa ${\displaystyle n}$ tidak habis membagi ${\displaystyle 2}$. Jika ${\displaystyle n}$ habis membagi ${\displaystyle 2}$, maka kekongruenan $${\displaystyle 2\sum _{i\,=\,1}^{\varphi (n)}x_{i}\equiv 0{\pmod {n}}}$$ tetap berlaku, namun tidak dengan $${\displaystyle \sum _{i\,=\,1}^{\varphi (n)}x_{i}\equiv 0{\pmod {n}}}$$