Kekongruenan

Pada post ini, author akan kembali membahas Definisi dan Teorema. Tetapi Definisi dan Teorema disini mengenai Kekongruenan pada bilangan bulat πŸ™‚

Definisi
Jika m suatu bilangan positif, maka a kongruen dengan b modulo m jika dan hanya jika m habis membagi a-b
(a\cong b\pmod m\iff m\mid a-b, m\in \mathbb{N})
Contoh:
10\cong 3 \pmod 7 \iff 7\mid 10-3
13\cong -7 \pmod 5\iff 5\mid 13-(-7)

Teorema 1
Setiap bilangan bulat kongruen modulo m dengan tepat satu diantara 0,1,2,3,\cdots, (m-1)
Contoh:
a=7, m=5, dan r=0,1,2,3,4
7\cong 2 \pmod 5

Teorema 2
a\cog b \pmod m jika dan hanya jika a dan b memiliki sisa yang sama jika dibagi m

Definisi 2
Himpunan bilangan bulat a_1, a_2, a_3, \cdots, a_m disebut sistem sisaan lengkap modulo m jika dan hanya jika setiap bilangan bulat adalah kongruen modulo m dengan satu dan hanya satu diantara r_1, r_2, r_3, \cdots, r_m
Contoh:
45\cong 0 \pmod 5
-9\cong 1 \pmod 5
22\cong 2 \pmod 5
18\cong 3 \pmod 5
34\cong 4 \pmod 5
0\le r<m
\mod 5 yaitu m=5
Jadi, r={0,1,2,3,4} (sebanyak 5)
r disini merupakan himpunan sisaan terkecil modulo 5
dan lima persamaan diatas merupakan sistem sisaan lengkap modulo 5

Teorema 3
Jika a\cong b \pmod m dan c\cong d \pmod m, maka (ac)\cong(bd)\pmod m
Bukti:
Akan dibuktikan Jika a\cong b \pmod m dan c\cong d \pmod m, maka (ac)\cong(bd)\pmod m
Perhatikan bahwa
Diketahui
a\cong b \pmod m berarti \exists k\in \mathbb{Z}, \ni a=mk+b …(1)
c\cong d \pmod m berarti \exists t\in \mathbb{Z}, \ni c=mt+d …(2)
Dari persamaan (1) dan (2) diperoleh

    \begin{align*} a+c&=(mk+b)+(mt+d)\\ &=(mk+mt)+(b+d)\\ &=m(k+t)+(b+d) \end{align*}

karena k\in \mathbb{Z} dan t\in \mathbb{Z}, maka k+t\in \mathbb{Z}
Misalkan s=k+t\in \mathbb{Z}
Sehingga, a+c=ms+(b+d)
Dengan kata lain, a+c\cong (b+d)\pmod m

Teorema 4 (perumuman Teorema 3)
Jika a\cong b \pmod m dan c\cong d \pmod m, maka untuk x dan y bilangan bulat berlaku (ax+cy)\cong (bx+dy)\pmod m
Bukti:
Akan dibuktikan Jika a\cong b \pmod m dan c\cong d \pmod m, maka untuk x dan y bilangan bulat berlaku (ax+cy)\cong (bx+dy)\pmod m
Perhatikan bahwa
Diketahui
a\cong b \pmod m berarti \exists k\in \mathbb{Z}, \ni a=mk+b …(1)
c\cong d \pmod m berarti \exists t\in \mathbb{Z}, \ni c=mt+d …(2)
Persamaan (1) dan (2) dijumlahkan, maka diperoleh
ax\cong mkt+bx
cy\cong mty+dy

ax+cy\cong m(kx+ty)+(bx+dy)
Karena k, t, x, y \in \mathbb{Z}, maka kx+ty \in \mathbb{Z}
Misalkan s=kx+ty
Sehingga, ax+cy\cong ms+(bx+dy)
Dengan kata lain ax+cy\cong (bx+dy)\pmod m

Teorema 5
Jika a\cong b \pmod m dan c\cong d \pmod m, maka (ac)\cong(bd)\pmod m

Teorema 6
Jika a\cong b \pmod m, maka (ka)\cong(kb)\pmod m untuk suatu k\in \mathbb{Z} sebarang

Teorema 7
Jika a\cong b \pmod m, maka (ka)\cong(kb)\pmod {km} untuk suatu k\in \mathbb{Z} sebarang

Teorema 8
Jika a\cong b\pmod m dan n\mid m, maka (a)\cong(b)\pmod n untuk suatu a, b, n\in \mathbb{Z}
Bukti:
Berdasarkan Definisi 1 yaitu
a\cong b \pmod m \iff m\mid a-b
Karena n\mid m dan m\mid a-b, berdasarkan Teorema 2 pada keterbagian bilangan bulat maka
n\mid a-b
Sehingga, sesuai dengan Definisi 1 dipeoleh
n\mid a-b \to a\cong b \pmod n

Teorema 9
Jika ab\cong ac \pmod m dan (a,m)=1, maka b\cong c \pmod m
(note: (a,m)=1 berarti bilangan a dan m memiliki FPB 1)
Bukti:
ab\cong ac \pmod m\iff m\mid ab-ac
m\mida(b-c)
Karena (a,m)=1, maka m\mid b-c
Dengan kata lain, b\cong c \pmod m

Teorema 10
Andaikan (c,m)=d, ac\cong bc \pmod m jika dan hanya jika a\cong b \pmod {\frac{m}{d}}

 

Kurangnya mohon dimaafkan dan dimaklumi πŸ™‚

Mudah-mudahan bermanfaat

Have a nice read, readers πŸ™‚

2 thoughts on “Kekongruenan

  1. When I originally commented I clicked the -Notify me when new comments are added- checkbox and now each time a comment is added I get four emails with the same comment. Is there any way you can remove me from that service? Thanks!

Tinggalkan Balasan

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *