Teorema Sisa Cina dan Urutan Bilangan Bulat

Pengantar Pemecahan Masalah

Pemecahan masalah atau problem solving adalah proses untuk menemukan solusi dari suatu masalah dengan menggunakan pengetahuan dan keterampilan yang sudah ada. Pemecahan masalah merupakan soft skill yang penting untuk menghadapi tantangan dalam kehidupan sehari – hari, terutama ketika harus menemukan solusi inovatif untuk masalah yang rumit

Kelas

Materi ini ditunjukan untuk siswa berbakat kelas 4, 5, 6, 7 dan 8

Presentasi

Unduh

Video Pengantar

fira

Video Lanjutan

Pre Test

Post Test

Referensi Tambahan

Unduh

Definisi

Teorema I. (Teorema Sisa Cina) Jika $m_1,m_2,…,m_k$ adalah bilangan bulat positif dengan $(m_i,m_j)=1$ untuk setiap $1\le i<j\le k$, maka sistem $$x\equiv b_1(\text{mod }m_1),\text{ }x\equiv b_2(\text{mod }m_2),…,x\equiv b_k(\text{mod }m_k)\text{ }(21.1)$$ harus memiliki solusi untuk setiap bilangan bulat $b_1,b_2,…b_k$ dan himpunan penyelesaiannya adalah kelas kongruensi modulo $m_1m_2\cdots m_k$, yaitu penyelesaiannya dibentuk oleh angka-angka $$x\equiv M_1M_1^{-1}b_1+M_2M_2^{-1}b_2+…+M_kM_m^{-1}b_k\text{ }\text{ }\text{ }(\text{mod }m_1m_2\cdots m_k),\text{ }\text{ }\text{ }(21.2)$$ dimana $M_i=m_1m_2\cdots m_k/m_i$ dan $m_i^{-1}$ adalah pembalik dari $M_i$ modulo $m_i$ untuk $i=1,2,…,k$.
Bukti. Dengan $S_1$ dan $S_2$ kami masing-masing menyatakan himpunan penyelesaian dari sistem (21.1) dan kelas kongruensi yang diberikan oleh (21.2). Di bawah ini kami tunjukkan bahwa $S_1 = S_2$.
Dari kondisi $(m_i,M_i)=1$ untuk $i=1,2,…,k$, pembalik $M_i$ dinyatakan dengan $M_i^{-1}$ ada untuk $i=1,2,…,k$. Dan, faktanya $M_j$ mempunyai faktor $m_i$ untuk setiap $j\neq i$ menyiratkan bahwa $m_i|m_j^{-1}b_i$ untuk semua $j\neq i$. Maka, untuk setiap $x\in S_2$ dan setiap $i\in\{1,2,…,k\}$, $$x\equiv \sum_{j=1}^{k}M_jM_j^{-1}b_j\equiv M_iM_i^{-1}b_i\equiv b_i\text{ }\text{ }\text{ }(\text{mod }m_i),$$ yaitu $x\in S_2\Rightarrow x\in S_1$, maka $S_2\subseteq S_1$.
Sebaliknya, untuk menunjukkan bahwa $S_1\subseteq S_2$, cukup dengan menunjukkan bahwa semua $x\in S_1$ berada dalam kelas kongruensi yang sama modulo $m_1m_2…m_k$. Misalkan $x$ dan $x’$ adalah dua solusi berbeda dari persamaan (21.1), maka $x\equiv x’$ (mod $m_i$) untuk $i=1,2,…,k$., maka $x\equiv x’$ (mod $m_1m_2…m_k$), sehingga $x$ dan $x’$ berada dalam kelas kongruensi yang sama.
Catatan: Teorema Sisa Cina menunjukkan keberadaan solusi untuk sistem yang sangat umum (21.1), tetapi bukan berarti rumus (21.2) merupakan satu-satunya metode untuk mendapatkan solusi. Terkadang terdapat metode yang lebih langsung daripada mencari $M_1^{-1},…,M_k^{-1}$, karena perhitungannya mungkin membutuhkan waktu yang lama. Misalnya, untuk menyelesaikan sistem $$x\equiv 1\text{ }\text{ }\text{ }(\text{mod }3),\text{ }\text{ }\text{ }x\equiv 3 \text{ }\text{ }\text{ }(\text{mod }5),\text{ }\text{ }\text{ }x\equiv 9\text{ }\text{ }\text{ }(\text{mod }11),$$ akan lebih mudah jika menggunakan fakta bahwa $x+2$ habis dibagi $3, 5$ dan $11$.

Definisi 1. Untuk bilangan bulat $a$ dan $m$ dengan $m>0$ dan $(a,m)=1$, bilangan bulat positif terkecil $n$ yang memenuhi $a^n\equiv 1$ (mod $m$) disebut orde $a$ modulo $m$, dilambangkan dengan $\text{ord}_ma$.

Beberapa sifat dasar orde $n$ bilangan bulat $a$

Jika $(a,m)=1$ dan $\text{ord}_ma=k$, maka untuk $u,v\in\mathbb{N}$ $$a^u\equiv a^v\text{ }(\text{mod }m)\Leftrightarrow o\equiv v\text{ }(\text{mod }k).$$ Khususnya, $a^u\equiv 1$ (mod $m$) jika dan hanya jika $k|u$.
Bukti: Kecukupan: Jika $u \equiv v$ (mod $k$), misalkan $u\ge v$, maka $u-v=kn$ untuk beberapa $n\in\mathbb{N}_0$ dan $$a^u-a^v=a^v(a^{u-v}-1)=a^v((a^k)^n-1)\equiv 0\text{ }\text{ }(\text{mod }m).$$ kebutuhan: Mialkan $u>v$ dan $a^u-^v\equiv 0$ (mod $m$). Karena $(a,m)=1,a^v(a^{u-v}-1)\equiv 0\Rightarrow a^{u-v}\equiv 1$ (mod $m$). Misalkan $u-v=kq+r$, dimana $0\le r<k$, maka $a^r\equiv 1$ (mod $m$), dan $k=\text{ord}_ma$ menyiratkan bahwa $r=0$, yaitu $u-v\equiv 0$ (mod $k$).
Jika $(a,m)=1$ dan $\text{ord}_ma=k$, maka $k|\varphi(m)$. Khususnya, $\text{ord}_ma\le \varphi(m)$, dan $k|(p-1)$ jika $m=p$ adalah prima.
Bukti: $a^{\varphi(m)}\equiv 1$ (mod $m$) $\Rightarrow a^{\varphi(m)}\equiv a^k$ (mod $m$), oleh karena itu $\varphi(m)\equiv k$ (mod $k$) dari properti (1), maka $\varphi(m)\equiv 0$ (mod $k$). Jadi, $k|\varphi(m)$. Khususnya, untuk $m=p$, kita memiliki $\varphi(p)=p-1$, maka $k|(p-1)$.

Definisi 2. Untuk bilagan bulat $r$ dan $m$ dengan $m>0$ dan $(r,m)=1$, $r$ dikatakan menjadi akar primitif modulo $m$ jika $\text{ord}_mr=\varphi(m).$
Catatan: Telah dibuktikan dalam teori bilangan bahwa akar primitif hanya ada untuk $m=1,2,4,p^n,2p^n$, di mana $p$ adalah bilangan prima ganjil.

Contoh Soal

Misalkan $a$ dan $b$ bilangan bulat positif sehingga $a^n+n$ membagi $b^n+n$ untuk setiap bilangan bulat positif $n$. Tunjukkkan bahwa $a=b$.
Solusi: Asumsikan bahwa $b\neq a$. Mengambil $n=1$ menunjukkan bahwa $a+1$ membagi $b+1$, sehingga $b>a$. Misalkan $p>b$ bilangan prima dan misalkan $n$ bilangan bulat positif sehingga $$n\equiv 1(\text{mod }p-1)\text{ dan }n\equiv -a(\text{mod }p).$$
Sehingga $n$ itu ada berdasarkan teorema sisa Cina. (Tanpa teorema sisa Cina, kita dapat melihat bahwa $n=(a+1)(p-1)+1$ memiliki sifat ini).
Berdasarkan teorema kecil Fermat, $a^n=a(a^{p-1})^k\equiv a$ (mod $p$) dan oleh karena itu $a^n+n\equiv 0$ (mod $p$). $p$ membagi $a^n+n$ dan oleh karena itu $p$ juga membagi $b^n+n$. Namun, berdasarkan teorema kecil Fermat, kita mendapatkan $b^n+n$, secara analogis $b^n+n\equiv b-a$ (mod $p$). Oleh karena itu, kita sampai pada kesimpulan $p|(b-a)$, yang merupakan kontradiksi.
Buktikan bahwa ada bilangan bulat positif $n$ sehingga $k^2+k+n$ tidak memiliki faktor prima kurang dari $2008$ untuk setiap bilangan bulat $k$.
Solusi: Misalkan $p$ adalah bilangan prima tertentu yang kurang dari $2008$. Maka ada bilangan bulat $r=r(p)$ (yaitu nilai $r$ bergantung pada $p$), sehingga $k^2+k\not\equiv r$ (mod $p$) untuk setiap $k$. Faktanya, ketika $k\equiv 0$ atau $p-1$ (mod $p$), maka $k^2+k\equiv 0$(mod $p$). Oleh karena itu sistem bilangan $p$ $$A=\{(k^2+k)\text{ }(\text{mod }p)|k\equiv 0,1,2,…(p-1)\text{ }(\text{mod }p)\}$$ bukan sistem residu lengkap modulo $p$, sehingga terdapat bilangan bulat $r\in A$, sehingga $k^2+k\not\equiv r$ (mod $p$). Misalkan himpunan $\{p_1,p_2,…,p_m\}$ terdiri dari semua bilangan prima kurang dari $2008$. Misalkan $n$ adalah bilangan bulat positif yang memenuhi sistem $$n\equiv p_j-r(p_j)\text{ }(\text{mod }p_j),\text{ }\text{ }j=1,2,…,m.$$ Teorema Sisa Cina mengindikasi bahwa pasti ada solusi positif $n$. Maka $k^2+k+n\equiv p_j+(k^2+k-r(p_j))\neq 0$ (mod $p_j$) untuk $j=1,2,…,m$, yaitu $n$ tidak dapat dibagi oleh masing-masing $p_j,j=1,2,…,m$. Kesimpulan nya, $n$ memenuhi persyaratan pada pertanyaan ini.
Untuk bilangan bulat $n>1$ manakah terdapat bilangan asli $b_1,b_2,…,b_n$ yang tidak semuanya sama sehingga $(b_1+k)(b_2+k)\cdots (b_n+k)=a^b$ dengan $a,b\in \mathbb{N}$ dan $a,b>1$ untuk setiap bilangan asli $k$? (Eksponen $a,b$ mungkin bergantung pada $k$).
Solution: Ketika $n$ adlah gabungan, maka $n=rs$ dimana $r>1$ dan $s>1$. Misalkan $b_1=b_2=\cdots b_r=1,b_{r+1}=\cdots =b_n=2$, maka $$(b_1+k)(b_2+k)\cdots (b_n+k)=(1+k)^r(2+k)^{r(s-1)}=[(1+k)(2+k)^{s-1}]^r$$ yang merupakan pangkat $r$ dari bilangan bulat positif $(1+k)(2+k)^{s-1}$.
Ketika $n$ adalah bilangan prima, misalkan ada bilangan bulat positif $b_1,b_2,…,b_n$ tidak semuanya sama sehingga $(b_1+k)(b_2+k)\cdots (b_n+k)=a^b$ dengan $a,b\in\mathbb{N}$ dan $a,b>1$ untuk setiap bilangan asli $k$ (dimana $a,b$ mungkin bergantung pada $k$). Tanpa kehilangan keumuman, kita berasumsi bahwa $b_1,b_2,…,b_l(l>1)$ berbeda tetapi masing-masing $b_{l+1},…,b_n$ sama dengan satu $b_1,b_2,…,b_l$ dan pada $b_1,b_2,…,b_n$, jumlah $b_i$ adalah $s_i$ untuk $i=1,2,…,l$, maka $s_1+s_2+…+s_l=n$.
Misalkan $p_1,p_2,…,p_l>\max \{b_1,b_2,…,b_l\}$ adalah $i$ bilangan prima yang berbeda. Dengan teorema sisa Cina, sistem pada $m$ $$b_1+m\equiv p_1\text{ }(\text{mod }p_1^2),…,b_l +m\equiv p_l\text{ }(\text{mod }p_l^2)$$ memiliki solusi bilangan bulat poitif. Berarti untuk setiap bilangan bulat positif $m$ bilangan $m+b_i$ adalah kelipatan $p_i$ tetapi bukan kelipatan $p_i^2$ untuk $i=1,2,…,l$. Karena $|b_i-b_j|<p_i$ untuk semua $j\neq i,1\le i,j\le l,b_j+m$ tidak dapat menjadikelipatan $p_i$, maka $$a^b=(b_1+m)(b_2+m)…(b_n+m)$$ adalah kelipatan dari $p_i^{si}$ tetapi bukan $p_i^{s_i+1}$, maka $b|s_i$ untuk $i=1,2,…,l$, oleh karena itu $b|n$. Namun, $b<n$ karena $l>1$, jadi $b=1$, kontradiksi.
Bilangan berbentuk $2^p-1$ dengan $p$ prima disebut bilangan Mersenne dalam teori bilangan. Buktikan bahwa jika $p$ prima ganjil dan $q$ merupakan faktor prima dari $2^p-1$, maka (i) $q>p;$ (ii) $q$ berbentuk $2np+1$, dengan $n\in \mathbb{N}$.
Solusi: $q$ harus ganjil. Misalkan $k=\text{ord}_q2$. Maka $2^p-1\equiv 0$ (mod $q$) $\Rightarrow 2^p\equiv 1$ (mod $q$) $\Rightarrow k|p$, maka $k=1$ atau $k=p$. $q>1$ menyiratkan $2\neq 1$ (mod $q$), oleh karena itu $k=p$.
Dengan teorema kecil Fermat, $2^{q-1}\equiv 1$ (mod $q$), oleh karena itu $p|(q-1)$ dan hasil bagi harus genap, maka (i) $p\le q-1\Rightarrow q>p$; dan (ii) $q-1=2np$, yaitu $q=2pn+1$.
Bilangan berbentuk $2^{2^n}+1$ (dilambangkan dengan $F_n$), $n\in\mathbb{N}$ disebut bilangan Fermat dalam teori bilangan. Buktikan bahwa
(i) Setiap faktor prima dari $F_n$ harus berbentuk $2^{n+1}k+1$, dengan $k\in\mathbb{N}$.
(ii) Buktikan bahwa terdapat bilangan prima tak terhingga banyaknya yang berbentuk $2^sm+1,s,m\in,\mathbb{N}.$
Solusi: (i) Misalkan $p$ adalah faktor prima $F_n=2^{2^n}+1$. Misalkan $k=\text{ord}_p2$. Maka $$2^{2^n}\equiv -1\text{ }\text{ }(\text{mod }p)\Rightarrow 2^{2^{n+1}}\equiv 1\text{ }\text{ }(\text{mod }p)\Rightarrow k|2^{n+1}$$ yaitu, $k$ adalah pangkat $2$. Misalkan $k=2^l$, dimana $0\le l\le n+1$. Jika $\le n$, maka $$2^{2^n}=(2^{2^l})^{2^n{n-l}}\equiv 1\text{ }(\text{mod }p)$$ yang kontradiksi $2^{2^n}\equiv -1$ (mod $p$), oleh karena itu $l=n+1$ yaitu, $k=2^{n+1}$. Maka teorema kecil Fermat menghasilkan $2^{n+1}|(p-1)$, maka $p=2^{n+1}m+1$.
(ii) Hasil dari (i) menyiratkan bahwa faktor prima $p$ pada $F_n=2^{2^n}+1$ memenuhi $p\equiv 1$ (mod $2^{n+1}$), Oleh karena itu, bilangan prima ini berbentuk $p=2^{n+1}k+1=2^sm+1$ untuk semua $n\ge s$.
Di bawah ini kita tunjukkan $(F_n,F_m)=1$ untuk $n>m$. Karena $2^m|2^n$, jadi $F_n-2=2^{2^n}-1$ habis dibagi $F_m$. Misalkan $(F_n,F_m)=d$, maka $d|F_m$ menyiratkan $d|F_n-2$, jadi $d|2$. Karena $F_m,F_n$ keduanya ganjil, maka $d\neq 2$, karena $d=1$.
Dengan demikian, semua faktor prima dari $F_n$ dan faktor prima dari $F_m$ berbeda untuk $n ≠ m$, terdapat bilangan prima tak terhingga banyaknya yang berbentuk $2^sm + 1$.
Bilangan palindromik adalah bilangan yang tidak berubah ketika urutan digitnya dibalik. Buktikan bahwa deret aritmatika $18, 37,…$ mengandung bilangan palindromik tak terhingga banyaknya.
Solusi: Pada Soal A8 Bab 20, kami membuktikan bahwa suku $\frac{10^k-1}{9}$ berada dalam A.P. yang diberikan jika $k = 6 + 18t, t \in\mathbb{N}_0$. Di sini kami membuktikan bahwa kondisi $10^k\equiv 11$ (mod $19$) mencukupi untuk suku $\frac{10^k-1}{9}$ berada dalam A.P..
Misalkan $k_0 = \text{ord}_{19}10$. Karena $10 = 2\cdot 5$ adalah akar primitif, maka $k_0 =\varphi (19) = 18$.
Atau, karena $10^{18} \equiv 1$ (mod $19$), maka $k_0 | 18$, yaitu, $k_0$ adalah salah satu dari $1, 2, 3, 6, 9, 12, 18$. Hasil yang sama dapat diperoleh dari tabel sisa $10^k$ modulo $19$ berikut sekaligus:

Jika $10^k\equiv 11$ (mod $19$) untuk $k>6$, maka $$10^{k-6}\equiv \text{ }(\text{mod }19)\Leftrightarrow k-6=18t\Leftrightarrow k=6+18t,$$ Maka $10^k\equiv 11$ (mod $19$) jika dan hanya jika $k=6+18t,t\in\mathbb{N}_0$.
$m$ adalah bilangan bulat positif. Jika $2^{m+1}+1$ membagi $3^{2^m}+1$, buktikan bahwa $2^{m+1}+1$ adalah bilangan prima.
Solusi: Misalkan $q=2^{m+1}+1$. Maka $q|(3^{2^m}+1)$, jadi $$3^{2^m}\equiv -1\text{}(\text{mod }q).\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }\text{ }(21.3)$$ Maka $(3,q)=1$. Mengambil kuadrat pada kedua sisi $(21.3)$: $$3^{2^{m+1}}\equiv 1\text{ }\text{ }(\text{mod }q).$$ Misalkan $k = \text{ord}_q3$, maka $k$ adalah faktor dari $2^{m+1} = q – 1$. Oleh karena itu, $k$ memiliki bentuk $2^r$, di mana $r$ adalah bilangan bulat positif dengan $r ≤ m + 1$. Jika $r ≤ m$, maka $3^{2^m}\equiv 1$ (mod $q$), yang bertentangan dengan (21.3). Jadi, $r = m + 1$.
Di sisi lain, berdasarkan Teorema Euler, $k$ adalah faktor dari $\varphi(q$), sehingga $2^{m+1}= q – 1$ membagi $\varphi(q)$, yaitu $q– 1 ≤ \varphi(q)$. Karena $\varphi(q) ≤ q – 1$, maka $\varphi(q) = q – 1$, yaitu $q$ adalah bilangan prima.
Misalkan $p$ bilangan prima. Buktikan bahwa terdapat bilangan prima $q$ sehingga untuk setiap bilangan bulat $n$, bilangan $n^p – p$ tidak habis dibagi $q$.
Solusi: Karena $(p^p – 1)/(p — 1) = 1 + p + p^2 +…+ p^{p-1} \equiv p +1$ (mod $p^2$), kita bisa mendapatkan setidaknya satu pembagi prima dari $(p^p -1)/(p – 1)$ yang tidak kongruen dengan $1$ modulo $p^2$.
Faktanya, tulis $M=\frac{p^p-1}{p-1}=p_1^{\alpha_1}\cdots p_s^{\alpha_s}$. Jika $p_i\equiv 1$ (mod $p^2$) untuk $i=1,2,…,s$, maka $$M\equiv \prod_{i=1}^{s}(k_ip^2+1)^{\alpha_i}\equiv 1\text{ }\text{ }(\text{mod }p^2),$$ kontradiksi.
Nyatakan pembagi prima tersebut dengan $q$. $q$ ini memenuhi syarat yang dimaksud.
Pembuktiannya adalah sebagai berikut.
Jelas bahwa $q\neq p$. Asumsikan terdapat bilangan bulat $n$ sehingga $n^p \equiv p$ (mod $q$), maka $q\nmid n$, dan kita peroleh $n^{p^2} \equiv p^p \equiv 1$ (mod $q$). Di sisi lain, dari teorema kecil Fermat, $n^{q-1} \equiv 1$ (mod $q$).
Karena $p^2$ tidak membagi $q – 1$, misalkan $\text{ord}_qn = k$, maka $k | p^2$ dan $k | q – 1$, sehingga $k = 1$ atau $p$. Dalam masing-masing dari dua kasus ini, kita peroleh $n^p \equiv 1$ (mod $q$). Dengan demikian, kita peroleh $p \equiv 1$ (mod $q$). Namun, ini menyiratkan $1 + p + .. + p^{p-1} \equiv p$ (mod $q$). Dari definisi $q$, hal ini mengarah pada $p \neq 0$ (mod $q$), sebuah kontradiksi.

Solusi dari setiap Permasalahan diberikan pada kelas online

“Confidence is like a muscle. The more you use it, the stronger it gets.”