Kongruensi 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

Definisi 1. Ketika suatu bilangan bulat $n$ dibagi dengan bilangan bulat bukan nol $m$, harus terdapat hasil bagi integral $q$ dan sisa $r$, di mana $0 ≤ |r| < m$. Hubungan ini dilambangkan dengan $$n=mq+r,$$ dan proses untuk mendapatkan hubungan ini disebut pembagian dengan sisa.

Definisi 2. Dua bilangan bulat $a$ dan $b$ dikatakan kongruen modulo $m$, dilambangkan dengan $a ≡ b$ (mod $m$), jika $a$ dan $b$ memiliki sisa pembagian yang sama ketika dibagi dengan bilangan bulat bukan nol $m$. Jika sisa pembagiannya berbeda, maka $a$ dan $b$ dikatakan tidak kongruen modulo $m$, dilambangkan dengan $a ≡ b$ (mod $m$).
Berdasarkan definisi kongruensi, empat hubungan ekuivalen berikut ini jelas: $$a\equiv b\text{ }\text{ (mod m)}\Longleftrightarrow a-b=km\Longleftrightarrow a-b\equiv \text{ }\text{ (mod m)}\Longleftrightarrow m|(a-b).$$

Sifat Dasar Kongruensi

Jika $a\equiv b$ (mod $m$) dan $b\equiv c$ (mod $m$), maka $a\equiv c$ (mod $m$).
Jika $a\equiv b$ (mod $m$) dan $c\equiv d$ (mod $m$), maka $$(a+c)\equiv (b+d)\text{ }\text{ (mod m)},\text{ }(a-c)\equiv (b-d)\text{ }\text{ (mod m)}.$$
Jika $a\equiv b$ (mod $m$) dan $c\equiv d$ (mod $m$), maka $a\cdot c\equiv b\cdot d$ (mod $m$).
Jika $a\equiv b$ (mod $m$) maka $a^n\equiv b^n$ (mod $m$) untuk semua bilangan asli $n$.
Jika $ac\equiv bc$ (mod $m$) dan $(c,m)=1$, maka $a\equiv b$ (mod $m$).

Digit Satuan Pangkat Bilangan Bulat Positif $a^n$

Misalkan $P$ adalah digit satuan dari bilangan bulat positif $a$, dan $n$ adalah pangkat bilangan bulat positif dari $a$. Maka, digit satuan dari $a^n$ ditentukan oleh digit satuan dari $P^n$, dilambangkan dengan $U(P^n)$, dan deret $\{U(P^n), n = 1, 2, 3, . . .\}$ mengikuti aturan berikut:

(I) Urutan tersebut mengambil nilai konstan untuk $P = 0, 1, 5, 6$, yaitu $U(P^n)$ tidak berubah ketika $n$ berubah.
(II) Urutannya periodik dengan periode $2$ untuk $P = 4$ atau $9$.
(III) Urutannya periodik dengan periode $4$ untuk $P = 2, 3, 7, 8$.

Dua Digit Terakhir Dari Beberapa Bilangan Bulat Positif

Dua digit terakhir dari $5^n (n ≥ 2)$ adalah $25$.
Pasangan terurut dari dua digit terakhir dari $6^n (n ≥ 2)$ berubah dengan periode “$36, 96, 76, 56$” seiring dengan perubahan $n$.
Pasangan terurut dari dua digit terakhir dari $7^n (n ≥ 2)$ berubah dengan periode “$07, 49, 43, 01$” seiring dengan perubahan $n$.
Pasangan terurut dari dua digit terakhir $76^n$ selalu $76$.

Contoh Soal

Ketika suatu bilangan tiga digit dibagi dengan $2, 3, 4, 5$, dan $7$, sisanya semuanya $1$. Tentukan nilai minimum dan maksimum dari bilangan tiga digit tersebut.
Solusi: Misalkan $x$ adalah bilangan tiga digit dengan sisa $1$ jika dibagi dengan $2, 3, 4, 5$, dan $7$. Maka $x − 1$ habis dibagi oleh masing-masing $2, 3, 4, 5, 7$, jadi $$x-1=k\cdot [2,3,4,5,7]=420k.$$ Jadi, nilai minimum $x$ adalah $420 + 1 = 421$, dan nilai maksimum $x$ adalah $2 × 420 + 1 = 841.$
Diketahui bahwa $2726, 4472, 5054$, dan $6412$ memiliki sisa yang sama ketika dibagi dengan bilangan asli dua digit $m$. Tentukan nilai $m$.
Solusi: Untuk mengecualikan efek sisa yang tidak diketahui, tiga selisih dari empat angka yang diberikan dapat digunakan untuk menggantikan empat angka asli. Lalu $$m | (4472 − 2726) ⇒ m | 1746.\text{ }\text{ }\text{ }\text{ }\text{ } 1746 = 2 · 3^2· 9^7;$$ $$m | (5054 − 4472) ⇒ m | 582.\text{ }\text{ }\text{ }\text{ }\text{ } 582 = 2 · 3 · 97;$$ $$m | (6412 − 5054) ⇒ m | 1358.\text{ }\text{ }\text{ }\text{ }\text{ } 1358 = 2 · 7 · 97.$$ Karena $97$ merupakan pembagi persekutuan dua digit yang unik dari selisihnya, maka $m = 97$.
$3^3 = 27 ≡ 1$ (mod 13) menyediakan metode untuk mengurangi pangkat dari $3$, maka $$3^{2000} ≡ (3^3)^{666} · 3^2 ≡ 3 ≡ 9 \text{ (mod 13)}.$$ Jadi, sisanya adalah $9$.
Catatan: Untuk mencari sisa pangkat besar bilangan bulat positif, penting untuk mencari pangkat minimum dengan sisa 1, atau melihat apakah sisa tetap konstan seiring dengan perubahan pangkat.
Temukan bilangan bulat positif terkecil $k$ sehingga $2^{69}+k$ habis dibagi $127$.
Solusi: $2^7 ≡ 1$ (mod $127$) menyiratkan $2^{7m} ≡ (2^7)^m ≡ 1^m ≡ 1$ (mod $127$), maka $$2^{69} = [(2^7)^9](2^6) ≡2^6 ≡ 64 \text{ (mod 127)},$$ Oleh karena itu nilai minimum $k$ sama dengan $127 − 64 = 63.$
Berapa sisa jika $6^{273} + 8^{273}$ dibagi dengan $49$?
Solusi: Secara umum, untuk bilangan bulat positif ganjil $n$, $$a^n+b^n=(a+b)(a^{n-1}-a^{n-2}b+a^{n-3}b^2-…+b^{n-1}),$$ sehingga $$6^{273}+8^{273}=(6+8)(6^{272}-6^{271}\cdot 8+6^{270}\cdot 8^2-…+8^{272})=14M,$$ dimana $M=6^{272}-6^{271}\cdot 8+6^{270}\cdot 8^2-…+8^{272}$. Lebih jauh lagi, $$M\equiv \underset{273\text{ suku}}{\underbrace{(-1)^{272}-(-1)^{271}+(-1)^{270}-…+1}}\equiv 273\equiv 0\text{ (mod 7)}$$ oleh karena itu $7 | M$, maka $49 | 14M$, artinya sisanya adalah $0$.
Temukan sisa bilangan $2005^{2007^{2009}}$ jika dibagi $7$.
Solusi: Pertama-tama $2005^{2007^{2009}}\equiv 3^{2007^{2009}}$ (mod 7). Karena $3^3\equiv -1$ (mod 7) menghasilkan $3^6\equiv (3^3)^2 \equiv 1$ (mod 7), $$2007^{2009}\equiv 3^{2009}\equiv 3\text{ }\text{ (mod 6)},$$ maka diperoleh $2007^{2009}=6k+3$ untuk bilangan bulat positif $k$. Oleh karena itu $$2005^{2007^{2009}}\equiv 3^{6k+3}\equiv 3^3\equiv 6\text{ }\text{ (mod 7)}.$$ Jadi sisanya adalah $6$.
Temukan bilangan bulat positif terkecil $n$ yang mana $1000 ≤ n ≤ 1100$ dan $1111^n + 1222^n + 1333^n + 1444^n$ habis dibagi $10$.
Solusi: Misalkan $N=1111^n+1222^n+1333^n+1444^n$. Maka $$N\equiv 1^n+2^n+3^n+4^n\text{ }\text{ (mod 10)}.$$ Untuk memperkirakan nilai minimum $n$, kita menguji $n = 1000$. Kemudian $$N ≡ 1 + (2^4)^{250} + (3^4)^{250} + (4^2)^{500} ≡ 1 + 6 + 1 + 6 ≡ 4 \text{ (mod 10)}.$$ Maka untuk $n=1001$, $$N ≡ 1 + 6 · 2 + 1 · 3 + 6 · 4 ≡ 1 + 2 + 3 + 4 ≡ 0 \text{ (mod 10)}.$$ Jadi $n_{\text{min}}=1001$.
Buktikan bahwa untuk setiap bilangan asli ganjil $n$, bilangan $1^{2007} + 2^{2007} +· · · + n^{2007}$ tidak habis dibagi $n + 2$.
Solusi: Dengan mengambil modulo $n + 2$, dan mempartisi suku-suku tersebut sebagai kelompok yang masing-masing terdiri dari dua suku, $$1^{2007}+2^{2007}+…+n^{2007}$$ $$=1+\left\lfloor 2^{2007}+n^{2007}\right\rfloor+…+\left\lfloor \left(\frac{n+1}{2}\right)^{2007}+\left(\frac{n+3}{2}\right)^{2007} \right\rfloor$$ $$\equiv 1+\left\lfloor 2^{2007}+(-2)^{2007} \right\rfloor +…+\left\lfloor \left(\frac{n+1}{2}\right)^{2007}+\left( -\frac{n+1}{2}\right)^{2007} \right\rfloor$$ $$\equiv 1\text{ (mod }n+2).$$ Dengan demikian, kesimpulannya terbukti.
Tuliskan empat digit terakhir dari angka tersebut $7^{128}$.
Solusi: Di sini metode rekursif efektif. Mulai dari $7^4 = 2401$, maka $$7^4=2401\equiv 2401\text{ }\text{ (mod }10^4),$$ $$7^8=(7^4)^2=(2400+1)^2=(2400)^2+4800+1\equiv 4801\text{ (mod }10^4),$$ $$7^{16}\equiv (4800+1)^2\equiv 9601\text{ (mod }10^4),$$ $$7^{32}\equiv (9600+1)^2\equiv 9201\text{ (mod }10^4),$$ $$7^{64}\equiv (9200+1)^2\equiv 8401\text{ (mod }10^4),$$ $$7^{128}\equiv (8400+1)^2\equiv 6801\text{ (mod }10^4).$$ Oleh karena itu empat digit terakhir dari $7^{128}$ adalah $6801$.

Solusi dari setiap Permasalahan diberikan pada kelas online

“Experience is a hard teacher because she gives the test first, the lesson afterwards.”