Beberapa Teorema Dasar tentang Kongruensi
- Definisi
- Contoh Soal
Definisi
Definisi 1. Himpunan bilangan bulat $S$ dikatakan sebagai sistem residu lengkap modulo $m$, jika setiap bilangan bulat kongruen dengan tepat satu bilangan bulat dalam $S$ modulo $m$.
Misalnya, untuk setiap bilangan asli $m$, himpunan $\{0,1,2,…,m-1\}$ merupakan sistem residu lengkap, dan dikatakan sebagai sistem residu nonnegatif terkecil modulo $m$.
Jika bilangan asli $n$ relatif prima terhadap bilangan asli $m$, maka semua bilangan dalam kelas kongruensi yang sama modulo $m$ dengan $n$ juga relatif prima terhadap $m$. Kelas tersebut disebut kelas tereduksi modulo $m$, dan jumlah kelas tereduksi dilambangkan dengan $\varphi (m)$, yang disebut fungsi phi Euler.
Untuk bilangan asli $m>1$ tertentu, setiap kelas tereduksi berisi satu bilangan unik kurang dari $m$, sehingga nilai $\varphi(m)$ sebenarnya sama dengan jumlah bilangan asli $n$ yang relatif prima terhadap $m$ dan tidak lebih besar dari $m$. Misalnya, $\varphi(1)=1, \varphi(p)=p-1$ untuk setiap bilangan prima $p$, dan $\varphi(m)<m-1$ untuk setiap komposit $m.$
Rumus berikut berguna untuk menghitung nilai $\varphi(m)$.
Teorema I. Ketika $m$ memiliki faktorisasi prima $m=p_{1}^{\alpha_1}\cdots p_{k}^{\alpha_k}$, maka $$\varphi(m)=m(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_k}).$$ Secara khusus, ketika $(m,n)=1$, maka $\varphi(mn)=\varphi(m)\varphi(n).$
Bukti. Kami menggunakan prinsip inklusi dan eksklusi untuk menunjukkan persamaan.
Misalkan $S=\{1,2,3,…,m\},S_i=\{x\in S:p_i|x\}$ untuk $i=1,2,…,k$. Maka $\varphi (m)=|\overline{S_1\cup S_2\cup \cdots \cup S_k}|$. Sudah jelas bahwa $$|S|=m,|S_i|=\frac{m}{p_i},|S_i\cap S_j|=\frac{m}{p_ip_j},…$$ Maka, dengan prinsip inklusi dan eksklusi, $$\varphi(m)=m-\left[ \sum_{i=1}^{k}\frac{m}{p_i}-\sum_{1\le i\le j\le k}^{ }\frac{m}{p_ip_j}+…+(-1)^{k-1} \frac{m}{p_1p_2\cdots p_k}\right]$$ $$=m\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots \left(1-\frac{1}{p_k}\right).$$ Secara khusus, jika $(m,n)=1$, maka $m$ dan $n$ tidak memiliki faktor prima yang sama, sehingga dengan mengelompokkan faktor-faktor produk terakhir sebagai dua kelompok, rumus $\varphi(mn)=\varphi(m)\cdot \varphi(n)$ diperoleh.
Definisi 2. Himpunan $S$ dengan $\varphi(m)$ bilangan berbeda disebut sistem residu tereduksi modulo $m$, jika semua bilangan bulat ini relatif prima terhadap $m$ dan dua bilangan apa pun tidak kongruen modulo $m$. Misalnya, himpunan $\varphi(m)$ bilangan asli yang tidak lebih besar dari $m$ dan relatif prima terhadap $m$ merupakan sistem residu tereduksi, dan disebut sistem residu tereduksi terkecil modulo $m$.
Teorema II. Untuk setiap bilangan asli $m>1$ dan bilangan bulat $a$, persamaan kongruensi $ax\equiv b$ selalu memiliki solusi untuk setiap bilangan bulat $b$ jika dan hanya jika $(a,m)=1$.
Bukti. Jika $(a,m)=1$, maka sistem $S =\{ac_1-b,ac_2-b,…,ac_m-b\}$ adalah sistem residu lengkap modulo $m$ asalkan $\{c_1,c_2,…,c_m\}$ adalah sistem residu lengkap modulo $m$, karena dua bilangan apa pun di $S$ memiliki sisa yang berbeda modulo $m$. Oleh karena itu, pasti ada satu elemen di $S$ yang habis dibagi $m$, katakanlah $m|(ac_1-b)$, sehingga $ac_1-b\equiv 0$ (mod $m$), dan yang ekuivalen dengan itu, $c_1$ adalah solusi dari persamaan $ac_1\equiv b$ (mod $m$).
Sebaliknya, Jika $ax\equiv b$ (mod $m$) selalu memiliki solusi untuk setiap bilangan bulat $b$, itu ekuivalen dengan pernyataan bahwa $ax\equiv 1$ (mod $m$) memiliki solusi. Misalkan $x_0$ menjadi solusi untuk persamaan $ax\equiv 1$ (mod $M$), maka $ax_0-1=km$ untuk beberapa bilangan bulat $k$. Misalkan $(a,m)=d>1$, maka $d|1$ kontradiksi. Jadi, $a,m)=1.$
Catatan: Setiap solusi persamaan $ax\equiv 1$ (mod $m$) dikatakan menjadi kebalikan dari modulo $m$, menyatakan dengan $a^{-1}$ (mod $m$) atau $\frac{1}{a}$ (mod $m$). Secara khusus, ada $a^{-1}$ unik yang memenuhi $1\le a^{-1}<m$.
Teorema III. (Teorema Euler) Misalkan $a,m\in\mathbb{Z}$ dengan $m\ge 1$. Jika $(a,m)=1$, maka $$a^{\varphi(m)}\equiv 1\text{ }\text{ }\text{ }(\text{mod }m).$$
Bukti. Misalkan $\{r_1,r_2,…,r_{\varphi(m)}\}$ adalah sistem residu tereduksi terkecil modulo $m$. Maka $\{ar_1,ar_2,…,ar_{\varphi(m)}$ juga merupakan sistem tereduksi modulo $m$ karena elemen $\varphi(m)$ dari sistem terakhir memiliki sisa yang berbeda modulo $m$. Dengan demikian, $$(ar_1)(ar_2)\cdots (ar_{\varphi(m)})\equiv r_1r_2\cdots r_{\varphi(m)}\text{ }\text{ }\text{ }(\text{mod }m)$$ Karena $(r_i,m)=1$ untuk semua $i=1,2,…,\varphi(m)$, kita memiliki $(r_1r_2\cdots r_{\varphi(m)},m)=1$, maka, dengan membatalkan $r_1r_2\cdots r_{\varphi(m)}$ dari kedua sisi persamaan kongruensi terakhir, kesimpulannya diperoleh sekaligus.
Teorema IV. (Teorema Kecil Fermat) Untuk setiap bilangan prima $p$, jika $a\in\mathbb{Z}$ dan $p\nmid a$, maka $$a^{p-1}\equiv 1\text{ }\text{ }\text{ }(\text{mod }p).$$
Bukti. Penerapan teorema Euler menghasilkan kesimpulan sekaligus ketika kita misalkan $m=p$.
Catatan: Teorema Kecil Fermat ini terkadang dinyatakan kembali dalam bentuk berikut: Untuk bilangan prima apa pun $p$ dan bilangan bulat apa pun $a,a^p\equiv a$ (mod $p$). Pernyataan ini juga dikenal sebagai Teorema Besar Fermat.
Teorema IV. (Wilson Theorem) Untuk setiap bilangan prima $p$, $$(p-1)!\equiv -1\text{ }\text{ }\text{ }(\text{mod }p).$$
Bukti. Kesimpulan nya adalah jelas untuk $p=2$. Jika $p\ge 3$ dan $1\le p-1$, maka ada $a^{-1}$ unik dengan $1\le a^{-1}\le p-1$, sehingga $aa^{-1}\equiv 1$ (mod $p$). Karena $$a\equiv a^{-1}\text{ }\text{ }\text{ }(\text{mod }p)\Longleftrightarrow a\equiv \pm 1\text{ }\text{ }\text{ }(\text{mod }p),$$ jadi $a=1$ atau $a=p-1$ saja. Sisa bilangan $p-3$ $2,3,…,p-2$ dapat dikelompokkan menjadi pasangan $(p-3)/2$ sehingga setiap pasangan berbentuk $(a,a^{-1})$ modulo $p$. Jadi, $$(p-1)!\equiv 1\cdot (p-1)\equiv -1\text{ }\text{ }\text{ }(\text{mod }p).$$
Contoh Soal
- Barisan $\{a_n\}$ didefinisikan dengan $a_0=a(a\in\mathbb{N})$, $a_n=a_{n-1}+40^{n!}(n>0)$. Buktikan bahwa barisan $\{a_n\}$ berisi tak terhingga banyaknya suku yang habis dibagi $2009$.
Solusi: $2009=41\cdot 49$ menyiratkan $(40,\text{ 2009})=1$. Oleh karena itu, dengan teorema Euler, $$40^{k\cdot \varphi(2009)}\equiv 1\text{ }\text{ }\text{ }(\text{mod }2009)\text{ }\text{ untuk semua }k\in \mathbb{N}_0.$$ Ketika $n>\varphi (2009)$, maka $\varphi(2009)|n!$, maka $a_{n+1}\equiv a_n +1$ (mod $2009$), maka $\{a_n\}$ adalah deret periodik yang dimulai dari suatu suku dengan $2009$ sebagai periode dalam modulo $2009$, dan periode ini membentuk suatu sistem residu lengkap modulo $2009$. Kesimpulannya, $\{a_n\}$ memuat suku-suku tak terhingga banyaknya yang habis dibagi $2009$. - Temukan semua bilangan bulat positif $n$ sehingga $\varphi (2n)=\varphi (3n)$.
Solusi: Tulis $n=2^{\alpha}4^{\beta}M$, dimana $\alpha,\beta$ adalah bilangan bulat non-negatif dan $M$ adalah bilangan bulat positif dengan $(6,M)=1$.
Misalkan $\beta >0$, maka $\varphi(2^{\alpha+1})=2^{\alpha},\varphi(3^{\beta})=3^{\beta-1}\cdot 2$, jadi $$\varphi(2n)=\varphi(2^{\alpha+1})\cdot \varphi(3^{\beta})\cdot \varphi(M)=2^{\alpha}\cdot 2(3^{\beta -1})\cdot \varphi(M),$$ $$\varphi(3n)=\varphi(2^{\alpha})\cdot \varphi(3^{\beta +1})\cdot\varphi(M)=\varphi(2^{\alpha})\cdot 2(3^{\beta})\cdot\varphi(M),$$ yang menyiratkan $\varphi (2n)\neq \varphi(3n)$. Maka, $\beta=0$, yaitu $n=2^{\alpha}M$. Untuk setiap $n$, $$\varphi(2n)=\varphi(2^{\alpha+1})\cdot \varphi(M)\text{ dan }\varphi(3n)=\varphi(2^{\alpha})\cdot 2\cdot \varphi(M)$$ $$\Rightarrow \varphi (2^{\alpha})=2^{\alpha-1}\Rightarrow \alpha \ge 1.$$ Maka, $n=2^{\alpha}M$, dimana $\alpha$ adalah bilangan bulat positif dan $M$ adalah bilangan bulat positif dengan $(6,M)=1$. - Temukan sisa dari jumlah $9^{10}+9^{10^2}+…+9^{10^{100}}$ jika dibagi dengan $7$.
Solusi: Karena $(9,7)=1$, dengan teorema Euler, $9^6\equiv 1$ (mod $7$), maka $$9^{10}\equiv 9^4\equiv 3^8\equiv 3^2\equiv 2\text{ }\text{ }\text{ }(\text{mod }7).$$ Demikian pula, $$9^{10^2}\equiv (9^{10})^{10}\equiv 2^{10}\equiv 2\text{ }\text{ }\text{ }(\text{mod }7).$$ Asumsikan bahwa $9^{10^n}\equiv 2$ (mod $7$) untuk $n=k$, maka untuk $n=k+1$. $$9^{10^{k+1}}\equiv (9^{10^k})^{10}\equiv 2^{10}\equiv 2\text{ }\text{ }\text{ }(\text{mod }7).$$ Dengan induksi, $9^{10^n}\equiv 2$ (mod $7$) untuk semua $n\in \mathbb{N}$. Maka, $$9^{10}+9^{10^2}+…+9^{10^{100}}\equiv 2\cdot 100\equiv 200\equiv 4\text{ }\text{ }\text{ }(\text{mod }7).$$ - Untuk setiap bilangan bulat positif $a,b$ dan $n$, buktikan bahwa $$n!|b^{n-1}a(a+b)(a+2b)\cdots [a+(n-1)b].$$ Solusi: Cukup menunjukkan bahwa untuk setiap bilangan prima $p\le n$, jika $p^{\alpha}|n!$, dimana $\alpha$ adalah indeks $p$ dalam faktorisasi prima $n!$, maka $p^{\alpha}|b^{n-1}a(a+b)(a+2b)\cdots (a+(n-1)b)$.
(i) Ketika $p|b$, maka $\alpha=\sum_{k=1}^{\infty}\left[\frac{n}{p^k}\right]<\sum_{k=1}^{\infty}\frac{n}{p^k}=\frac{n}{p-1}\le n$ menyiratkan $\alpha \le n-1$, dan maka kesimpulannya selesai.
(ii) Ketika $p\nmid b$, maka $(b,p)=1\Rightarrow (b,p^{\alpha})=1$, maka ada $b_1$ sehingga $bb_1\equiv 1$ (mod $p^{\alpha}$). Maka $$b_1^na(a+b)(a+2b)\cdots (a+(n-1)b)$$ $$\equiv ab_1(ab_1+1)(ab_1+2)\cdots (ab_1+(n-1))\text{ }\text{ }\text{ }(\text{mod }p^{\alpha}).$$ Ruas kanan merupakan hasil perkalian $n$ bilangan bulat berurutan, sehingga habis dibagi $n!$, dan habis dibagi $p^{\alpha}$. Karena $(b,p)=1\Rightarrow (b_1,p)=1\Rightarrow (b_1^n,p^{\alpha})=1$, kita memiliki $$p^{\alpha}|a(a+b)(a+2b)\cdots (a+(n-1)b),$$ maka, $p^{\alpha}|b^{n-1}(a+b)(a+2b)\cdots (a+(n-1)b).$ - Tentukan semua fungsi $f:\mathbb{N}_0\mapsto \mathbb{N}_0$ sehingga
(i) $f(mn)=f(m)+f(n);$
(ii) $f(2008)=0;$
(iii) $f(n)=0$ untuk semua $n$ dengan $n\equiv 39$ (mod $2008$).$
Solusi: Perhatikan bahwa $2008=2^3\times 251$. Jika $f$ adalah solusi, (i) dan (ii) menghasilkan $3f(2)+f(251)=0$. Rentang $f$ adalah himpunan bilangan bulat non-negatif, jadi $f(2)=f(251)=0$. Oleh karena itu, untuk setiap $n=2^a\cdot 251^b\cdot m$ dengan $(m,2008)=1$ $$f(n)=af(2)+bf(251)+f(m)=f(m).\text{ }\text{ }\text{ }(20.1)$$ Karena $(m,2008)=1$, persamaan $mx\equiv 1$ (mod $2008$) harus memiliki solusi $k$ sehingga $$km\equiv 1\text{ }\text{ }\text{ }(\text{mod }2008).$$ (iii) maka menghasilkan $$f(39km)=f(39)+f(k)+f(m)=0\Rightarrow f(39)=f(k)=f(m)=0.$$ Jadi, $f(m)=0$ untuk setiap bilangan bulat positif $m$ dengan $(m,2008)=1$, dan maka dengan $(20.1)$ $$f(n)=0,\text{ }\text{ }\text{ }\text{ untuk semua }n\in\mathbb{N}.$$ - Temukan semua pasangan terurut $(p,q)$ dari dua bilangan prima sedemikian rupa sehingga $pq|5^p+5^q$.
Solusi: Ketika $2|pq$ kita asumsikan bahwa $p=2$, maka $2q|5^2+5^q\Rightarrow q|25+5^q$. Dari teorema Kecil Fermat, $q|(5^q-5)$, maka $q|30$, yaitu $q$ kemungkinan $2,3,5$. Dengan memeriksa, (2, 3), (2, 5) adalah dua solusi untuk $(p,q)$ tetapi $\{2,2\}$ tidak dapat diterima.
Ketika $p,q$ kedua nya ganjil dan $5|pq$, kita asumsikan bahwa $p=5$, maka $5q|(5^5+5^q)$ dan $q|5^{q-1}+625$. Ketika $q=5$, pasangan (5, 5) memenuhi persyaratan. Ketika $q\neq 5$, dengan teorema Kecil Fermat, $q|(5^{q-1}-1)$, maka $q|626$. Karena $q$ adalah prima ganjil dan $626=2\cdot 313$, kita harus memiliki $q=313$. Pasangan (5, 313) memenuhi syarat dengan memeriksa.
Ketika $p,q$ kedua nya bukan $2$ dan $5$, maka $pq|5^{p-1}+5^{q-1}$, dan juga $$5^{p-1}+5^{q-1}\equiv 0\text{ }\text{ }\text{ }(\text{mod }p).\text{ }\text{ }\text{ }\text{ }\text{ }(20.2)$$ Dengan torema kecil Fermat, $$5^{p-1}\equiv 1\text{ }\text{ }\text{ }(\text{mod }p).\text{ }\text{ }\text{ }\text{ }\text{ }(20.3)$$ Kombinasi (20.2) dan (20.3) menghasilkan $$5^{q-1}\equiv -1\text{ }\text{ }\text{ }\text{mod }p).\text{ }\text{ }\text{ }\text{ }\text{ }(20.4)$$ Tulis $p-1=2^k(2r-1),q-1=2^l(2s-1)$, dimana $k,l,r,s$ semua nya positif bilangan bulat.
Jika $k\le 1$, dari (20.3) dan (20.4), $$1=1^{2^{l-k}(2s-1)}\equiv (5^{p-1})^{2^{l-k}(2s-1)}\equiv 5^{2^{l}(2r-1)(2s-1)}$$ $$=(5^{q-1})^{2r-1}\equiv (-1)^{2r-1}\equiv -1\text{ }\text{ }\text{ }(\text{mod }p),$$ yang bertentangan dengan asumsi bahwa $p\neq 2!$ Maka, $k>1$.
Namun, setelah bertukar $p$ dan $q$ dan berpikir dengan cara yang sama, maka diperoleh $k>l$. Jadi, tidak ada solusi untuk $(p,q)$ pada kasus ini.
Akhirnya, mempertimbangkan simetris $p$ dan $q$ pada pertanyaan, pasangan yang diinginkan untuk $(p,q)$ adalah $$(2,3),(3,2),(2,5),(5,2),(5,5),(5,313),(313,5).$$ - Buktikan bahwa ada barisan tak terbatas yang bertambah $\{a_n\}, n=1,2,…$ dari bilangan bulat positif, sedemikian rupa sehingga ada bilangan bulat positif $M$ dengan sifat berikut: untuk semua bilangan bulat positif $n\ge M$, semua faktor prima dari $n!+1$ harus lebih besar dari $n+a_n$ asalkan $n+1$ bukan bilangan prima.
Solusi: Misalkan $p$ menjadi faktor prima $n!+1$ dan $n+1$ bukan prima, maka $p>n+1$. Misalkan $t=p-n-1$, maka $t$ bilangan bulat positif. Dengan teorema Wilson, $$(p-1)!\equiv -1\text{ }\text{ }\text{ }(\text{mod }p).$$ Karena $(p-t-1)!t!\equiv (-1)^t(p-1)!\equiv (-1)^{t+1}(\text{mod }p)$, maka $n!t!\equiv (-1)^{t+1}(\text{mod }p)$, oleh karena itu $p|t!+(-1)^{t+1}$. Maka, $t!\ge p-1$. Karena $p-1=n+t$, jadi $t!-t\ge n$ menyiratkan bahwa $t!>n$.
Sekarang definisikan $a_n$ minimum bilangan bulat positif $m$ yang memenuhi $m!>n$, maka $\{a_n\}$ adalah deret menigkat, dan $a_n\to +\infty$ sebagai $n\to +\infty$. Sebaliknya, ada konstanta $C$ sehingga $C!>n$ untuk semua $n\in\mathbb{N}$.) Maka, $t\ge a_n$ menyiratkan $$p=n+t+1>n+a_n.$$
“The only place where success comes before work is in the dictionary.”
