Forum Sains Indonesia

Ilmu Alam => Matematika => Topik dimulai oleh: Mtk Kerajaan Mataram pada Juni 14, 2009, 09:13:02 PM

Judul: Soal Teori Bilangan untuk Pemula
Ditulis oleh: Mtk Kerajaan Mataram pada Juni 14, 2009, 09:13:02 PM
1. Buktikan ! (1 poin)
   (i) Jika k adalah bilangan asli ganjil, maka jumlah k bilangan bulat yang berturutan habis
       dibagi oleh k. (contoh : k=5 maka -3+(-2)+(-1)+0+1 habis dibagi 5, juga
       23+24+25+26+27 habis dibagi 5).
   (ii) Jika a,b, dan c bilangan asli, dan GCD(a,b)=1 serta c|b ("b habis dibagi c"),
        maka GCD(a,c)=1. (Ket : Ingat GCD(p,q)=1 <==> ada m,n bulat sehingga mp+nq=1)


2. Selesaikan sistem kongruensi ! (1 poin)
   (i) x \equiv 2(mod 9) dan x \equiv 4(mod 10)
   (ii) 5x \equiv 14(mod 17) dan 3x \equiv 2(mod 13)

3. Jika GCD(a,n) =1, maka bilangan asli terkecil, katakanlah k yang memenuhi
    a^k \equiv 1(mod n) disebut dengan 'order perkalian (multiplicative order)'
    dari [a] dalam group Z_n^{\times}. (Contoh : GCD(3,5)=1 dan
    3^4 =81 \equiv 1(mod 5) maka order perkalian [3] dalam group Z_5^{\times} adalah 4.
    Sekarang tentukan order perkalian dari  (1 poin)
    (i)  [5] dan [11] dalam group Z_{17}^{\times}
    (ii) tiap elemen dari group Z_8^{\times} (yakni [1],[2],...,[7])

Judul: Re: Soal Teori Bilangan untuk Pemula
Ditulis oleh: Nabih pada Juni 16, 2009, 01:22:12 AM
2. Selesaikan sistem kongruensi ! (1 poin)
   (i) x \equiv 2(mod 9) dan x \equiv 4(mod 10)
x \equiv 2(mod 9)\equiv 74(mod 90)
x \equiv 4(mod 10)\equiv 74(mod 90)
jawabanya74(mod 90)
   (ii) 5x \equiv 14(mod 17) dan 3x \equiv 2(mod 13)
5x \equiv 14(mod 17) \equiv 65(mod 17)
x \equiv 13(mod 17)
3x \equiv 2(mod 13) \equiv 15(mod 13)
x \equiv 5(mod 17)
x \equiv 13(mod 17) \equiv 200(mod 221)
x \equiv 5(mod 13) \equiv 200(mod 221)
jawabanya x \equiv 200(mod 221)

Bener ga ???
Judul: Re: Soal Teori Bilangan untuk Pemula
Ditulis oleh: Mtk Kerajaan Mataram pada Juni 16, 2009, 02:40:01 AM
@Nabih
(i) Bisakah anda menjelaskan lagi bagaimana cara memperoleh 74 dan 90, jawaban sudah benar.

(ii)
5x \equiv 14(mod 17) \equiv 65(mod 17)
x \equiv 13(mod 17)
3x \equiv 2(mod 13) \equiv 15(mod 13)
x \equiv 5(mod 13)

Bagaimana diperoleh 65 dan 15 di atas?
Ternyata jawabannya juga betul, padahal langkah2nya kurang menjelaskan untuk dipahami.
Terima kasih, monggo dilanjut penjelasannya lagi.
Judul: Re: Soal Teori Bilangan untuk Pemula
Ditulis oleh: Nabih pada Juni 16, 2009, 02:57:21 AM
@Nabih
(i) Bisakah anda menjelaskan lagi bagaimana cara memperoleh 74 dan 90, jawaban sudah benar.

(ii)
5x \equiv 14(mod 17) \equiv 65(mod 17)
x \equiv 13(mod 17)
3x \equiv 2(mod 13) \equiv 15(mod 13)
x \equiv 5(mod 13)

Bagaimana diperoleh 65 dan 15 di atas?
Ternyata jawabannya juga betul, padahal langkah2nya kurang menjelaskan untuk dipahami.
Terima kasih, monggo dilanjut penjelasannya lagi.

kalau 90 ma 221 itu KPK
90 KPK dari 9 dan 10
221 KPK dari 13 dan 17

untuk asal 74, caranya dibuat deret bantu
2 11 20 ... 74
4 14 24 ... 74
(memang kurang efektif, bis bisanya baru itu)

kalo 15 dan 65, sama dengan deret bantu sampai bisa dibagi modulonya
14 31 ... 65
2  15

saja jawab ini agar om mtk bisa njelasin yang lebih mudah

sudah cukup syarat unuk IQ +1 belum?
Judul: Re: Soal Teori Bilangan untuk Pemula
Ditulis oleh: Mtk Kerajaan Mataram pada Juni 16, 2009, 12:00:18 PM
untuk asal 74, caranya dibuat deret bantu
2 11 20 ... 74
4 14 24 ... 74
(memang kurang efektif, bis bisanya baru itu)
kalo 15 dan 65, sama dengan deret bantu sampai bisa dibagi modulonya
14 31 ... 65
2  15

2,11,20,...,74,... = 9m+2 
4,14,24,...,74,... = 10n+4

Dari kedua barisan di atas cari suku yang nilainya sama kalau mungkin (disini ternyata diperoleh untuk m=8 dan n=7).

Cari bilangan2 lain yang seperti 74 (yang sekaligus berbentuk 9m+2 dan 10n+4), yaitu ada dua cara :

- Berdasarkan barisan pertama buat suatu barisan dengan suku pertamanya = m = 8 dan bedanya = n = 10 sehingga kita peroleh 10p+8, lalu nilai2 pada barisan ini merupakan nilai2 m yang baru atau katakanlah m=10p+8, lalu substitusikan ke x = 9m+2 sehingga x=9(10p+8)+2 = 90p+74 dan diperoleh penyelesaian x=74(mod 90).
- Berdasarkan barisan kedua....silahkan anda buat sendiri.......(*)

Anda bisa melihat kesalahan pada apa yang anda tuliskan berikut tidak ?
x \equiv 2(mod 9)\equiv 74(mod 90)
x \equiv 4(mod 10)\equiv 74(mod 90)
dan
x \equiv 13(mod 17) \equiv 200(mod 221)
x \equiv 5(mod 13) \equiv 200(mod 221)
........................(**)

saja jawab ini agar om mtk bisa njelasin yang lebih mudah
sudah cukup syarat unuk IQ +1 belum?
Semoga yang di atas cukup menjelaskan. Dan tolong yaa jelaskan dahulu yang dua pertanyaan di atas..sepertinya anda masih mengalami kegamangan. Saya bukan menyulit-nyulitkan lho...tapi supaya semakin tajam dan tajam pengertiannya....Good Luck.
Judul: Re: Soal Teori Bilangan untuk Pemula
Ditulis oleh: Nabih pada Juni 17, 2009, 08:19:35 AM
- Berdasarkan barisan pertama buat suatu barisan dengan suku pertamanya = m = 7 dan bedanya = n = 9 sehingga kita peroleh 9q+7, lalu nilai2 pada barisan ini merupakan nilai2 m yang baru atau katakanlah m=9q+7, lalu substitusikan ke x = 9m+7 sehingga x=10(9q+7)+4 = 90q+74 dan diperoleh penyelesaian x=74(mod 90)
*) udah bener belom ???

 
5x \equiv 14(mod 17) \equiv (17-14)17+14(mod 17)
x \equiv 13(mod 17)
3x \equiv 2(mod 13) \equiv 13 + 2(mod 13)
x \equiv 5(mod 13)
**) wah, tetep ga dapet polanya
Judul: Re: Soal Teori Bilangan untuk Pemula
Ditulis oleh: Mtk Kerajaan Mataram pada Juni 17, 2009, 11:41:05 AM
Jawaban (*) tepat sekali, untuk (**) bukan itu yang dimaksud, tapi soal yang pertama, silahkan perhatikan lagi mana yang salah tulis. Satu poin untuk anda untuk hal ini.
Untuk 5x=14(mod 17) cukup cari 17h+14 yang habis dibagi 5 :
5 | (17h+14) ==> 5 | (2h+4) <karena 10 dan 15 habis dibagi 5, bisa dicancel>
                  ==> diperoleh yang pertama adalah 5 | (2.3+4), yaitu h=3.
                  ==> 17.3+14=65
                  ==> 5x=65(mod 17) ==> x=13(mod 17)
Selamat !     
Judul: Re: Soal Teori Bilangan untuk Pemula
Ditulis oleh: Nabih pada Juni 17, 2009, 12:07:07 PM
5 | (17h+14) ==> 5 | (2h+4) <karena 10 dan 15 habis dibagi 5, bisa dicancel>
                  ==> diperoleh yang pertama adalah 5 | (2.3+4), yaitu h=3
                dari mana???


1. Buktikan ! (1 poin)
   (i) Jika k adalah bilangan asli ganjil, maka jumlah k bilangan bulat yang berturutan habis
       dibagi oleh k. (contoh : k=5 maka -3+(-2)+(-1)+0+1 habis dibagi 5, juga
       23+24+25+26+27 habis dibagi 5).
   (ii) Jika a,b, dan c bilangan asli, dan GCD(a,b)=1 serta c|b ("b habis dibagi c"),
        maka GCD(a,c)=1. (Ket : Ingat GCD(p,q)=1 <==> ada m,n bulat sehingga mp+nq=1)
setahu saya yang namanya bilangan ganjil pasti asli, emangnya bilangan negatif ada ganjil genap

thanks buat om Mtk atas kesabaranya 1 poin buat om Mtk
Judul: Re: Soal Teori Bilangan untuk Pemula
Ditulis oleh: Mtk Kerajaan Mataram pada Juni 17, 2009, 08:23:45 PM
2h+4 untuk h=0,1,2,3,... yang pertama kali habis dibagi 5 adalah 2.3+4 (untuk h=3).
Bilangan -1,-3,-5,... juga sering disebut bil ganjil.
Judul: Re: Soal Teori Bilangan untuk Pemula
Ditulis oleh: Nabih pada Juni 18, 2009, 05:30:59 AM
2h+4 untuk h=0,1,2,3,... yang pertama kali habis dibagi 5 adalah 2.3+4 (untuk h=3).
Bilangan -1,-3,-5,... juga sering disebut bil ganjil.

berarti cara awal saya benar, buktinya om Mtk menggunakan cara yang sama
Judul: Re: Soal Teori Bilangan untuk Pemula
Ditulis oleh: Mtk Kerajaan Mataram pada Juni 18, 2009, 12:14:59 PM
Hiya yaa...makanya kukasih 1 poin. Selamat.
Judul: Re: Soal Teori Bilangan untuk Pemula
Ditulis oleh: Nabih pada Juni 18, 2009, 12:24:48 PM
1. Buktikan ! (1 poin)
   (i) Jika k adalah bilangan asli ganjil, maka jumlah k bilangan bulat yang berturutan habis
       dibagi oleh k. (contoh : k=5 maka -3+(-2)+(-1)+0+1 habis dibagi 5, juga
       23+24+25+26+27 habis dibagi 5).
   (ii) Jika a,b, dan c bilangan asli, dan GCD(a,b)=1 serta c|b ("b habis dibagi c"),
        maka GCD(a,c)=1. (Ket : Ingat GCD(p,q)=1 <==> ada m,n bulat sehingga mp+nq=1)

mau jawab yang (ii) ah

GCD(a,b)=1  <==>  ap + bq=1
b=xc           <==>  ap + xcq=1
                           ap + cr=1 maka GCD(a,c)=1

yang (i)
k=2n+1
maka jumlahan k bilangan berurutan (misal suku tengah x)

(x-n) + (x-n+1) + ... + x + (x+1) + ... + (x+n) = (2n+1)x = kx

misal n=0, jumlah deret=x
n=1, jumlah deret=2x

asumsikan benar untuk n=m
(x-m) + (x-m+1) + ... + x + (x+1) + ... + (x+m) = (2m+1)x = kx

lalu sunstitusikan n=m+1
(x-m+1) + (x-m+2) + ... + x+1 + (x+2) + ... + (x+m+1) = k(x+1)
= (x-m) + (x-m+1) + ... + x + (x+1) + ... + (x+m) + 2m+1
= kx + k
= k(x+1)
Terbukti

demikian juga dengan perubahan x (juag pake induksi)
Tebukti juga dech

Gimana?

untuk no 3, saya harus belajar lagi

Judul: Re: Soal Teori Bilangan untuk Pemula
Ditulis oleh: Mtk Kerajaan Mataram pada Juni 18, 2009, 12:59:38 PM
Untuk yang nomor (ii) sempurna.

Untuk yang nomor (i) : ada beberapa yang perlu saya tanyakan, sbb:

yang (i)
k=2n+1
maka jumlahan k bilangan berurutan (misal suku tengah x)
(x-n) + (x-n+1) + ... + x + (x+1) + ... + (x+n) = (2n+1)x = kx
misal n=0, jumlah deret=x
n=1, jumlah deret=2x

kalau n=0, banyak bil =k=1 ==> x
kalau n=1 banyak bil =k=3  ==> bukankah x-1 + x + x+1 = 3x ?

asumsikan benar untuk n=m
(x-m) + (x-m+1) + ... + x + (x+1) + ... + (x+m) = (2m+1)x = kx

lalu sunstitusikan n=m+1
(x-m+1) + (x-m+2) + ... + x+1 + (x+2) + ... + (x+m+1) = k(x+1)

= (x-m) + (x-m+1) + ... + x + (x+1) + ... + (x+m) + 2m+1
= kx + k
= k(x+1)
Terbukti

Mengapa kok menjadi
= (x-m) + (x-m+1) + ... + x + (x+1) + ... + (x+m) + 2m+1 ?
Judul: Re: Soal Teori Bilangan untuk Pemula
Ditulis oleh: Nabih pada Juni 18, 2009, 01:23:13 PM
kalau n=1 banyak bil =k=3  ==> bukankah x-1 + x + x+1 = 3x ?
yang ini kurang ketik



rumus suku tengah

Mengapa kok menjadi
= (x-m) + (x-m+1) + ... + x + (x+1) + ... + (x+m) ?

kan tadinya
(x-m+1) + (x-m+2) + ... + x+1 + (x+2) + ... + (x+m+1) =
saya rubah menjadi
(x-m)+1 + (x-m+1)+1 + ... + (x)+1 + (x+1) +1 + ... + (x+m) +1
karena 1 ada k, kan di soal k bilangan berurutan
jadi saya rubah
(x-m) + (x-m+1) + ... + x + (x+1) + ... + (x+m)


cukup runtut kah?

kalo ini lembar jawab OSN, dari 7 saya dapet berapa?

(saya jadi tahu, kenapa saya ga dapet medali waktu OSN)
Judul: Re: Soal Teori Bilangan untuk Pemula
Ditulis oleh: Mtk Kerajaan Mataram pada Juni 18, 2009, 01:52:32 PM
(x-m+1) + (x-m+2) + ...+(x-1)+ (x) + (x+1) + (x+2) + ... +(x+m)+ (x+m+1) =

[(x-m)+1] + [(x-m+1)+1] + ... + [(x-2)+1] + [(x-1)+1] + [(x)+1] +[(x+1)+1] + ... +[(x+m-1)+1]+ [(x+m) +1] =

{(x-m) + (x-m+1) + ... + x + (x+1) + ... + (x+m)} + k dengan k=2m+1
= kx + k <berdasar asumsi>
=k(x+1)

Okay, bagus sudah benar, 1 poin buat anda. Saya bukan panitia OSN, sehingga tidak tahu bagaimana penilaiannya.
Judul: Re: Soal Teori Bilangan untuk Pemula
Ditulis oleh: Nabih pada Juni 23, 2009, 04:55:04 AM
3. Jika GCD(a,n) =1, maka bilangan asli terkecil, katakanlah k yang memenuhi
    a^k \equiv 1(mod n) disebut dengan 'order perkalian (multiplicative order)'
    dari [a] dalam group Z_n^{\times}. (Contoh : GCD(3,5)=1 dan
    3^4 =81 \equiv 1(mod 5) maka order perkalian [3] dalam group Z_5^{\times} adalah 4.
    Sekarang tentukan order perkalian dari  (1 poin)
    (i)  [5] dan [11] dalam group Z_{17}^{\times}
    (ii) tiap elemen dari group Z_8^{\times} (yakni [1],[2],...,[7])



Z_n^{\times} maksudnya apaan
Judul: Re: Soal Teori Bilangan untuk Pemula
Ditulis oleh: Mtk Kerajaan Mataram pada Juni 23, 2009, 01:00:54 PM
Z_n^{\times} maksudnya apaan

Z_n^{\times} adalah himpunan beranggotakan [1],[2],...,[n-1] yang didalamnya berlaku operasi perkalian ("x").
Contoh :
Z_5^{\times} beranggotakan [1],[2],[3],[4].
[2]x[2]=[4] karena 2x2 (mod 5)=4(mod 5)
[2]x[3]=[1] karena 2x3 (mod 5)=1(mod 5)
Perkaliannya bersifat tertutup karena hasil perkaliannya juga anggota Z_5^{\times}.
Z_n^{\times} bersama operasi biner perkalian kongruensi merupakan semigroup (syarat adanya invers pada group dihilangkan).
Jika p merupakan bilangan prima maka Z_p^{\times} merupakan group multiplikatif yang anggota-anggotanya kelas-kelas kongruensi [1],[2],...,[n-1].
Kita review sebentar tentang group :
Group adalah sebuah himpunan G bersama sebuah operasi biner * yang memenuhi sifat :
- tertutup : utk setiap a,b anggota G maka a*b juga anggota G
- assosiatif : utk setiap a,b,c anggota G maka a*(b*c)=(a*b)*c
- ada elemen identitas e dalam G sehingga utk setiap a anggota G e*a=a*e=a
- untuk setiap a anggota G ada b anggota G sehingga a*b=e (invers).
Judul: Re: Soal Teori Bilangan untuk Pemula
Ditulis oleh: Kholil pada Juni 24, 2009, 01:10:34 AM
Gimana cara nentuin elemen identitasnya ???

dari group tersebut
Judul: Re: Soal Teori Bilangan untuk Pemula
Ditulis oleh: Nabih pada Juni 24, 2009, 01:59:25 AM
Gimana cara nentuin elemen identitasnya ???

dari group tersebut
Wah! kok pertanyaannya sama dengan saya?
Judul: Re: Soal Teori Bilangan untuk Pemula
Ditulis oleh: Mtk Kerajaan Mataram pada Juni 24, 2009, 03:17:31 AM
Lo yaa disini elemen identitasnya [1]. karena untuk setiap x anggota{[1],[2],...,[p-1]}, maka 1.x=x.1=x (mod p).
Judul: Re: Soal Teori Bilangan untuk Pemula
Ditulis oleh: Nabih pada Juni 24, 2009, 03:29:52 AM
 untuk semua Z_n^{\times} kah?

@mtk utang IQ saya dah lunas, lihat postingan saya tentang pembuktian bahwa bilangan prima berbentuk 6n+1dan6n-1
Judul: Re: Soal Teori Bilangan untuk Pemula
Ditulis oleh: Mtk Kerajaan Mataram pada Juni 24, 2009, 11:25:42 AM
" untuk setiap x anggota{[1],[2],...,[n-1]}, maka 1.x=x.1=x (mod n) jelas bahwa untuk setiap n bilangan asli sifat ini selalu terpenuhi.
Yang invers tidak selalu terpenuhi, hanya untuk n bilangan prima saja yang menjamin bahwa setiap anggota Z_n^{\times} punya invers. 
Contoh untuk Z_{17}^{\times} adalah sebagai berikut :

Elemen Order    Invers
[1]        1          [1]
[2]        8          [9]
[3]       16          [6]
[4]        4          [13]
[5]       16          [7]
[6]       16          [3]
[7]       16          [5]
[8]        8           [15]
[9]        8           [2]
[10]     16           [12]
[11]     16           [14]
[12]     16           [10]
[13]      4            [4]
[14]     16            [11]
[15]      8             [8]
[16]      2             [16]

Saya ambil misal elemen [11] punya invers [14] karena 11\times 14 = 154 \equiv 1(mod17).
Dan [11] punya order 16 karena 11^{16}=45949729863572161 \equiv 1(mod 17).
 
Judul: Re: Soal Teori Bilangan untuk Pemula
Ditulis oleh: Nabih pada Juni 25, 2009, 08:56:14 AM
Kalau itu saya tahu, saya hanya asing dengan notasinya, saya masih perlu buka buku lagi nich!
Judul: Re: Soal Teori Bilangan untuk Pemula
Ditulis oleh: Nabih pada Desember 08, 2009, 11:34:05 AM
Setelah belajar struktur aljabar, akhirnya saya mengerti maksud pertanyaanya mas Mataram
3. a
5^n = \equiv 1(mod 17)
11^n = \equiv 1(mod 17)
pake fermat kan dua-duanya 16

3.b
1^n = \equiv 1(mod 8), order [1]= 1
2^n = \equiv 1(mod 8), order [2]= ga ada
3^n = \equiv 1(mod 8), order [3]= 2
4^n = \equiv 1(mod 8), order [4]= ga ada
5^n = \equiv 1(mod 8), order [1]= 2
6^n = \equiv 1(mod 8), order [6]= ga ada
7^n = \equiv 1(mod 8), order [1]= 2

kalo yang ga ada, jelas, itu tak saling prima dengan 8, tapi kenapa yang lain banyak yang 2, aa yang bisa jawab?
Judul: Re: Soal Teori Bilangan untuk Pemula
Ditulis oleh: Mtk Kerajaan Mataram pada Desember 16, 2009, 11:40:46 AM
@Nabih
Syukurlah sudah tahu maksudnya, jawabannya sudah benar, +1 IQ.

kalo yang ga ada, jelas, itu tak saling prima dengan 8, tapi kenapa yang lain banyak yang 2, aa yang bisa jawab?
Hayo silahkan selidiki...
Judul: Re: Soal Teori Bilangan untuk Pemula
Ditulis oleh: Nabih pada Desember 17, 2009, 06:35:11 AM
4. Tentukan order dari Z_a^{\times}xZ_b^{\times}xZ_c^{\times}
a. Terhadap perkalian
b. Terhadap penjumlahan
c. Terhadap pembagian
d. Terhadap pengurangan
e. Terhadap operasi pangkat
Judul: Re: Soal Teori Bilangan untuk Pemula
Ditulis oleh: Mtk Kerajaan Mataram pada Desember 17, 2009, 12:11:35 PM
@Nabih
Ehh..saya kok aneh dengan soal ini yaa....?
Z_a^{\times}xZ_b^{\times}xZ_c^{\times} adalah group yang merupakan direct product dari group Z_a^{\times}, Z_b^{\times}, dan Z_c^{\times}.
Order dari suatu group tidak lain adalah banyaknya anggota dari group tersebut, jadi tidak terkait dengan terhadap operasi perkalian atau penjumlahan.
Order dari suatu elemen yang terkaitkan dengan operasi biner,
misal order dari elemen a terhadap perkalian adalah m jika a^m=1, dimana 1 adalah identitas perkalian (elemen netral pada perkalian),
atau order dari a terhadap penjumlahan adalah m jika \underbrace{a+a+ \cdots +a}_{ sebanyak-m}=0, dimana 0 adalah identitas penjumlahan (elemen netral untuk penjumlahan).
Kita juga tahu tidak ada elemen netral untuk pembagian dan pengurangan.
Judul: Re: Soal Teori Bilangan untuk Pemula
Ditulis oleh: Nabih pada Desember 18, 2009, 10:32:07 AM
bukanya elemen netral pada penjumlahan dan pengurangan sama2 nol
sedangkan pada perkalian dan pembagian satu, lalu soal itu saya kutip dari OST-DIY dan saya juga tidak bisa mengerjakannya