Kembali ke sekolah dasar.kita belajar 4 inti operasi
pada angka (bilangan bulat),yaitu penjumlahan (+),pengurangan(-),perkalian(x
atau . ) dan pembagian (/).untuk setiap dua bilangan bulat a dan b,penjumlahan
a + b,pengurangan a-b dan b-a,serta perkalian ab adalah semuanya bilangan
bulat,semenatara hasil bagi a/b dan b/a tidak selalu bilangan bulat.
Untuk satu
bilangan bulat m dan satu bilangan bulat tidak nol n, kita mengatakan bahwa m
dapat dibagi oleh n atau n membagi habis m jika terdapat bilangan bulat k,
sedemikin hingga m=kn,berarti m/n adalah bilangan bulat.kita notasikan hal
tersebut dengan n│m.jika m dibagi habis oleh n maka m disebut kelipatan dari n,
dan n disebut faktor dari m.
Karena
0=0.n,ini menunjukkan bahwa n│0 untuk setiap bilangan bulat n.untuk bilangan
bulat tertentu n,kelipatan dari n adalah 0, ±n, ±2n,....karenanya tidak sulit
untuk menunjukkan bahwa terdapat kelipatan dari n untuk tiap-tiap n yang
berurutan.jika m tidak habis dibagi oleh n maka kita tuliskan n│m(catatan bahwa
0│m untuk setiap bilangan bulat m tidak nol karena m≠0=k.0 untuk setiap
bilangan bulat k).
Proposisi1.1bentuk
x,y, dan z bilangan bulat,kita punya dasar sebagai berikut:
A. x│x (sifat refleksif)
B. jika x│y dan y│z maka x│z
(sifat transitif)
C. jika x│y dan y ≠0 maka│x│≤│y│
D. jika x│y dan x│z maka x│
y +
z untuk setiap bilangan bulat
dan
E. jika x│y dan x│y±z maka x│z
F. jika x│y dan
y│x maka │x│=│y│
G. jika x│y dan y ≠0 mak a
│y
H. untuk z ≠0, x│y jika dan
hanya jika xz│yz
Sifat di atas dapat dibuktikan secara langsung dari
definisi.kita menyajikan bikti ini hanya untuk memberikan kepada pembaca
beberapa contoh yang relevan dari bukti penulisan.
Bukti:
Untuk
A.kita notasikan bahwa x=1.x.pada B.sampai H. Kondisi x│y telah diberika sehingga y=kx untuk suatu
bilangan bulat k.
Untuk
B. Kta mempunyai y│z sehingga
untuk suatu
bilangan bulat
. Maka
atau x│z.
Untuk
C. Kita notasikan bahwa jika y ≠0 maka │k│≥1 dan juga │y│=│k│.│x│≥│x│
Untuk
D. Selanjutnya kita asumsikan bahwa
Maka
Untuk
E. Kita peroleh
atau
. Ini menunjukkan bahwa
.
Untuk
F. Karena x│y dan y│x,ini menunjukkan bahwa x≠0 dan y≠0.dari C. Kita punya
bahwa │y│≥│x│ dan │x│≥│y│.Karenanya │x│=│y│
Untuk
G.
adalah suatu bilangan bulat.karena
Untuk
H. Karena z≠0,x ≠0 jika dan hanya jika xz ≠0.dinotasikan bahwa y=kx jika dan
hanya jika yz=kxz.
Sifat
G. Sederhana tetapi sangat membantu. Untuk bilangan bulat tak nol n, terdapat
suatu bilangan genap positif pembagi n
kecuali jika n adalah perfect square yaitu
untuk suatu
bilangan bulat m.(Jika suatu bilangan bulat tidak dapat dibagi oleh suatu
bilangan perfect square maka
bilangan tersebut disebut square free.Jika
untuk suatu
bilangan bulat m, maka n disebut sebagai
perfect cube. Secara umum,
jika
untuk bilangan
bulat m dan s dengan s ≥ 2, maka n disebut perfect
power.)Ini adalah karena semua pembagi y nampak berpasangan,yaitu
dan
(amati bahwa
jika y bukan sebuah perfect square).Ini adalah masalah klasik yang sangat sulit:
Contoh 1.1 Dua puluh murid yang
sedang bosan mengambil giliran berjalan pada suatu lorong yang berisi sebaris
loker yang tertutup,bernomor 1 sampai 20.Murid pertama membuka semua
loker,murid kedua menutup semua loker yag bernomor
2,4,6,8,10,12,14,16,18,20;murid ketiga membuka loker bernomor 3,6,9,12,15,18 jika loker tersebut dalam
keadaan tertutup dan menutup loker tersebut jika dalam keadaan terbuka.untuk
setiap murid ke-i bekerja pada loker yang bernomor kelipatan dari i,jika loker
tertutup akan dibuka dan jika loker terbuka maka akan ditutup.loker nomor
berapa yang masih terbuka setelah semua murid selesai berjalan?
Penyelesaian : Catatan bahwa loker
ke-i akan dioperasikan oleh murid j jika dan hanya jika j│i.Berdasarkan sifat
G. Ini bisa terjadi jika dan hanya jika loker tersebut juga akan dioperasikan
oleh murid
.Dengan demikian hanya loker nomor 1 =
, 4=22,9=32 dan 16=42
akan dioperasikan dalam waktu yang bernilai ganjil loker ini akan ditinggalkan
terbuka setelah semua operasi dilakukan.Maka dari itu jawabannya adalah loker 4.
Humpunan
dari bilangan bulat ditandakan oleh Z
dapat dipartisikan menjadi dua subset
yaitu himpunan dari bilangan bulat ganjil dan himpunan bilangan bulat
genap:
(±1,±3,
±5,...) dan (0, ±2, ±4,...),
Berturut-turut.
Walau konsep bilangan bulat ganjil dan bilangan bulat genap terlihat secara
langsung,dapat menyelesaikan berbagai masalah teori bilangan.berikut ini
diberikan beberapa ide dasar:
1.
bilangan
ganjil merupakan bentuk 2k+1 untuk suatu bilangna bulat k.
2.
Bilangan
genap adalah bentuk 2m untuk suatu bilangan bulat m,
3.
Penjumlahan
dari dua bilangan ganjil adalah sebuah bilangan genap,
4.
Penjumlahan
dari dua bilangan genap adalah bilangan genap,
5.
Penjumlahan
dari suatu bilangan ganjil dengan suatu bilangan genap adalah bilangan ganjil,
6.
Perkalian
dari dua bilangan ganjil adalah sebuah bilangan ganjil,
7.
Perkalian
bilangan bulat genap jika dan hanya jika sedikitnya satu dari faktor bilangan
tersebut adalah bilangan genap.
Contoh 1.2 Asumsikan n bilangan bulat lebih besar dari 1. Buktikan
bahwa
a.
2n
adalah penjumlahan dari dua buah bilangan bulat ganjil yang berurutan;
b.
3n
adalah penjumlahan dari tiga bilangan bulat yang berurutan.
Bukti:Untuk a. Hubungan 2n=(2k-1)+(2k+1)
didapatkan bahwa k = 2n-2
dan kita peroleh
2n=(2n-1-1)+(2n-1+1).
Untuk b. Hubungan 3n=(s-1)+s+(s+1)
didapatkan bahwa s=3n-1 dan kita peroleh penyajiannya sebagai berikut 3n=(3n-1-1)+3n-1+(3n-1+1)
Contoh 1.3.Asumsikan k merupakan
bilangan genap. Apakah mungkin untuk menulis 1 sebagai jumlah kebalikan k
bilangan bulat ganjil?
Penyelesaian: jawabannya adalah
tidak.
Kita
gunakan pendekatan tidak langsung. Asumsikan bahwa:
Untuk
suatu bilangan bulat negatif n1,....,nk;maka jelas bahwa
penyebut n1....nk=s1+....+sk
dimana si semuanya benilai ganjil.tetapi hal ini tidak mungkin,karena pada sisi
kiri adalah bilangan ganjil dan pada sisi kanan adalah bilangan genap.
Jika
k adalah bilangan ganjil , penyajian demikian adalah mungkin.Berikut ini contoh
untuk k=9 dan n1,....,n9 adalah bilangan bulat positif ganjil
yang berbeda:
Contoh 1.4.[HMMT 2004]Zach memilih
lima angka dari himpunan {1,2,3,4,5,6,7}. Jika dia memberitahu Claudia hasil
kali dari angka yang dipilihnya, maka hal tersebut tidak akan cukup
menginformasikan kepada Claudia untuk menebak hasil penjumlahan dari angka yang
dipilih Zach genap atau ganjil. Berapakah hasil kali dari angka yang dipilih
Zach?
Penyelesaian: jawabannya adalah 420
Memberikan
hasil kali dari angka-angka yang dipilih adalah sama dengan memberikan hasil
kali dari dua angka yang tidak dipilih. satu-satunya
kemungkinan hasil kali yang dicapai oleh lebih dari satu pasangan dari
angka-angka berikut 12({3,4}) dan {2,6})dan 6({1,6}dan{2,3}).tetapi dalam kasus
kedua penjumlahan dari dua bilangan (tidak dipilih) adalah ganjil(dan
penjumlhan dari kelima bilangan yang dipilih adalah ganjil). Karena itu
digunakan kemungkinan yang pertama,dan hasil kali dari lima angka yang dipilih
sama dengan:
ALGORITMA PEMBAGIAN
Hasil berikut disebut algoritma
pembagian dan ini memainkan satu peran penting dalam teori bilangan:
Teorema
1.2a. untuk setiap bilangan bulat positif a
dan b terdapat satu pasangan tunggal (q,r) dari bilangan bulat tidak negatif
sedemikian hingga b = aq +r dan r < a.kita sebut q sebagai hasil bagi dan r
sebagai sisa ketika b dibagi oleh a.
Untuk membuktikan hasil ini, kita perlu
membuktikan dua bagian: keberadaan pasangan bilangan dan ketunggalannya.
Bukti:
untuk menunjukkan keberadaannya,kita mempertimbangkan tiga kasus.
1) Dalam
kasus ini kita asumsikan bahwa a>b.kita bisa membentuk q=0 dan r=
b<a;sehingga (q,r)=(0,b).
2) Andaikan
a=b.kita bisa membentuk q=1 dan r = 0 < a;sehingga (q,r)=(1,0).
3) Terakhir,
asumsikan bahwa a < b. Terdapat bilangan bulat positif n sedemikian hingga
na > b.q bilangan bulat positif terkecil untuk yang mana (q+1)a > b.maka
qa≤b.r=b-aq. Ini menunjukkan bahwa b = aq+r dan 0≤r<a. Dengan
mengkombinasikan tiga kasus tersebut,kita telah menentukan keberadaannya.
Untuk ketunggalannya,
bahwa b=aq’ + r’,dimana q’ dan r’ juga merupakan bilangan bulat tidak negatif
sehingga 0≤r’<a.maka aq+r=aq’+r’,berakibat a(q-q’)=r’-r dan juga a│r’-r.
Karenanya │r’-r│≥a atau │r’-r│=0. Karena 0≤r,r’<a maka hasilnya │r’-r│
<a,kita ditinggalkan dengan │r’-r│=0,berakibat r’=r,sehingga q’=q.
Contoh 1.5.n adalah
bilangan bulat positif. Buktikan bahwa
dapat dibagi
habis oleh 2 tetapi tidak habis dibagi oleh 4.
Bukti: jelas bahwa
adalah bilangan ganjil dan
adalah bilangan
genap.catat bahwa
=
. Ingat kembali teorema binomial
Masukkan nilai x=8,y=1,
dan m=2n-1 pada persamaan atas,kita lihat bahwa masing-masing
penjumlahan,kecuali yang terakhir (ym=1)adalah kelipatan dari 8(yang
merupakan kelipatan dari 4). Karenanya sisa dari
dibagi oleh 4
sama dengan 1, dan sisa dari
dibagi oleh 4
sama dengan 2. Pendapat di atas dapat disederhanakan ke dalam notasi kongruen
modulo 4. Kongruensi merupakan bagian penting dari teori bilangan. Kita akan
membicarakan ini secara ekstensif. Algoritma pembagian dapat diperluas untuk
bilangan bulat:
Teorema 1.2b. untuk
setiap bilangan bulat a dan b,a≠0,terdapat dengan tunggal pasangan (q,r) dari
bilangan bulat sedemikian hingga b=aq+r dan 0≤r<│a│.
Kita tinggalkan bukti
perluasan ini untuk pembaca.
PRIMA
Bilangan bulat p>1
disebut prima(atau bilangan prima)jika tidak terdapat bilangan bulat d dengan
d>1 dan d≠p sedemikian hingga d│p.sebarang bilangan bulat n>1 mempunyai paling
sedikit satu bilangan prima pembagi. Jika n adalah bilangan prima, maka
bilangan prima pembaginya adalah dirinya sendiri. Jika n bukan bilangan
prima,maka a>1 menjadi pembagi terkecil. Maka n=ab,dimana 1<a≤b. jika a
bukan bilangan prima maka a=a1a2 dengan 1<a1≤a2<a
dan a1│n,terjadi kontradiksi dengan keminimalan dari a.
Bilangan bulat n>1
yang bukan bilangan prima disebut bilangan komposit. Jika n adalah bilangan
bulat komposit, maka mempunyai pembagi prima p tidak lebih dari
. Bahwasanya sebagai di atas,n=ab, dimana 1<a≤b dan
a adalah pembagi terkecil dari n. Maka n≥a2;karenanya a≤
. ide ini ditemukan pada zaman Yunani kuno oleh
seorang ahli matematika bernama Eratoshenes(250 BCE).
Catatan bahwa semua
bilangan genap positif lebih dari 2 adalah bilangan komposit. Di sisi lain,2
adalah satu-satunya bilangan prima yang genap dan terkecil.Semua bilangan prima
yang lain adalah bilangan ganjil;bilangan-bilangan tersebut tidak dapat dibagi
oleh 2. Bilangan terkecil pertama adalah 2,3,5,7,11,13,17,19,23,29. Berapa
banyak bilangan tersebut? Apakah kita
benar-benar yakin bahwa bilangan prima jumlahnya tidak terhitung. Lihat teorema
1.3 di bawah ini. Perbandingan antara angka dari unsur pada dua setelan tanpa
batas adalah samar-samar,tetapi jelas nyata bahwa lebih banyak bilangan
komposit daripada bilangan prima. Kita tahu bahwa 2 dan 3 adalah satu-satunya
bilangan prima yang berurutan. Urutan bilangan prima yang berselang, misalnya 3
dan 5,5 dan 7,41 dan 43,disebut bilangan prima kembar. Masih menjadi pertanyaan
apakah bilangan prima kembar jumlahnya tak hingga. Brun telah memperlihatkan,
sekalipun terdapat tak hinnga bilangan prima yang kembar,jumlah dari
kebalikannya adalah konvergen. Pembuktian untuk hal tersebut sangat sulit.
Contoh 1.6. temukan
semua bilangan bulat positif n yang memenuhi 3n-4,4n-5,dan 5n-3 sehingga
ketiganya merupakan bilangan prima.
Penyelesaian: jumlah
dari ketiga bilangan tersebut adalah suatu bilangan genap, jadi paling sedikit
salah satu dari ketiganya adalah bilangan genap. Satu-satunya bilangan prima
yang genap adalah 2. Hanya 3n-4 dan 5n-3 yang merupakan bilangan genap. Penyelesaian
dari persamaan
3n-4=2 dan 5n-3=2
berturut-turut adalah n=2 dan n=1. Mudah untuk mengecek bahwa n=2 menjadikan
ketiga angka tersebut menjadi bilangan prima.
Contoh 1.7. [AHSME1976]
Jika p dan q adalah bilangan prima dan
mempunyai dua
akar bilangan bulat yang berbeda,tentukan p dan q.
Penyelesaian:misalkan
dan
merupaka
aka-akar dari persamaan tersebut,dengan
<
,,maka
, berakibat p=
+
dan q=
. Karena q adalah bilangan prima,
=1. Dengan demikian q=
dan p=
+1 adalah bilangan prima yang berurutan,sehingga
diperoleh q=2 dan p=3.
Contoh 1.8. temukan 20
bilangn komposit yang berurutan.
Penyelesaian: angka 20!
+2,20!+3,....,20! Merupakan penyelesaiannya.
Hasil berikut oleh
Euclid telah diketahui lebih dari 2000 tahun:
Teorema 1.3a. terdapat
tak hinga bilangan prima.
Bukti: andaikan
banyaknya bilangan prima terhingga:
pertimbangkan
angka
. Jika P merupakan bilangan prima maka P>
. Kontradiksi dengan diketahui bahwa bilangan prima
terbesar adalah
. Karena itu P merupakan bilangan komposit dan
mempunyai pembagi prima p>1,yaitu salah satu bilangan prima dari
katakan
. Sehingga
. Berakibat
membagi
,maka
membagi 1.
Terjadi kontradiksi.
Walaupun terdapat tak
hingga bilangan prima,tidak ada rumus tertentu untuk menemukannya. Teorema 1.3b
pada bagian berikutnya akan mengungkapkan bagian dari penalaran.
Teorema fundamental
aritmatika
Hasil fundamental dalam
aritmatika menyinggung masalah faktor prima dari bilangan bulat:
Teorema 1.4. [Teorema
Fundamental Aritmatika]
Sebarang bilangan bulat
lebih dari 1 mempunyai penyajian tunggal sebagai perkalian dari bilangan prima.
Bukti:Keberadaan dari
penyajian seperti itu dapat diperoleh dengan:
adalah bilangan prima pembagi n. Jika
maka
adalah faktor
prima dari n. Jika
maka
,dimana
. Jika
adalah bilangan
prima, maka
dimana
adalah faktor dari
n yang diinginkan. Jika
adalah bilangan
komposit, maka
dimana
adalah bilangan
prima,
dan
. Jika
bilangan prima,
maka
,
dan
. Jika
bilangan
komposit, maka kita lanjutkan algoritma ini,dengan memperoleh satu urutan
bilangan bulat
. Setelah berhingga bilangan pada urutan tersebut,kita
dapatkan
,karena itu
.
Untuk sifat
ketunggalan, kita asumsikan bahwa terdapat paling sedikit stu bilangan bulat
positif n yang mempunyai dua faktor prima yang berbeda,yaitu:
, dimana
adalah bilangan
prima, dengan
dan
sehingga
k-tuple
tidak sama
dengan h-tuple
. Jelas bahwa
dan
. n merupakan bilangan bulat terkecil. Kita akan
memperoleh kontradiksi dengan menemukan bilangan bulat positif yang lebih kecil
yang juga mempunyai dua faktor prima yang berbeda.
Kita klaim bahwa
,untuk setiap i=1,2,...,k, j=1,2,...,h. Untuk contoh,
, maka
dan
,kontradiksi dengan minimality n. Tanpa meninggalkan
keumuman bahwa
;
adalah faktor
prima terkecil dari n pada penyajian di atas. Dengan menggunakan algoritma
pembagian diperoleh
Dimana
.
Kita punya
.
Memperluas perkalian yang terakhir,kita peroleh
untuk suatu
bilangan bulat positif m.
Bentuk
kita punyai
. Hali ini menunjukkan bahwa
dan
. Kita tulis
dimana
adalah bilangan
prima.
Di sisi lain, faktor prima dari
,semua faktornya kurang dari
. Dari
, berdasarkan
hal tersebut n’ mempunyai faktor prima dalam bentuk
, dimana
. Faktor ini berbeda dengan
. Tetapi
, terjadi kontradiksi dengan minimality n.
Berdasarkan teorema di atas,diperoleh bahwa untuk
setiap bilangan bulat n>1 dapat dituliskan ketunggalannya dalam bentuk
,
Dimana
adalah bilangan prima yang berbeda dan
bilangan bulat
positif. Penyajian ini disebut faktor
kanonik(atau faktori) dari n. Tidak sulit untuk menunjukkan bahwa faktor
kanonik dari perkalian dua buah bilangan
bulat adalah perkalian dari faktor kanonik kedua bilangan tersebut. Faktorisasi ini memudahkan kita untuk
menentukan sifat fundamental pada bilangan prima.
Kesimpulan 1.5. a dan b bilangan bulat. Jika
bilangan prima p membagi habis ab, maka
p membagi habis a atau b.
Bukti: karena p membagi habis b,p harus merupakan
faktor kanonik dari ab. Faktor kanonik dari a,b,dan ab adalah tunggal,dan
faktor kanonik dari ab dalah perkalian dari faktor kanonik a dan b. karena itu, p harus merupakan paling tidak
salah satu dari faktor kanonik a dan b,mengakibatkan hasil yang diinginkan.
Penggunaan langsung yang lain dari teorema faktorisasi prima adalah cara lain
untuk membuktikan bahwa terdapat tak hingga bilangan prima.
Seperti dalam bukti teorema 1.3,asumsikan bahwa
terdapat berhingga bilangan prima:
.
Di sisi lain, dengan memperluas dan menggunakan
faktorisasi kanonik dari bilangan bulat positif, kita peroleh
Menghasilkan
Terjadi kontradiksi. Kita telah menggunakan fakta
paling umum:
a.
Rangkaian
selaras
,divergen
b.
Rumus
expansi
Khusus untuk
bilangan real x dengan
. Ruus ekxpansi ini bisa juga diinterpretasikan
sebagai rumus penjumlahan untuk kemajuan geometri tak terbatas
Dari rumus,
,
Menggunakan
pertidaksamaan
kita dapat dengan mudah memperoleh
Untuk
bilangan prima p kita katakan bahwa
spenuhnya
membagi n dan ditulis
jika k bilangan
positif terbesar sehingga
.
Contoh 1.9.
[ARML 2003] Temukan bilangan pembagi terbesar dari 1001001001
yang tidak melebihi 10000.
Penyelesaian:
kita punya
Catatan
bahwa
kita simpulkan
bahwa
dan juga 1001001001=7.11.13.101.9901. tidak sulit
untuk mengecek bahwa tidak ada kombinasi dari 7, 11, 13, dan 101 yang bisa
menghasilkan perkalian lebih dari 9901 dan
kurang dari 10000,jadi jawabannya adalah 9901.
Contoh 1.10.
tentukan n sedemikian hingga
.
Penyelesaian:
jawabannya adalah 12
Perhatikan
bahwa
dan
. Kita punya,
Dari contoh 1.5,
untuk bilangan
bulat positif k.karena itu,jawabannya Teorema 1.4 mengindikasikan bahwa semua
bilangan bulat dihasilkan dari bilangan prima. Karena pentingnya bilanngan prima,banya orang telah
mencoba untuk menemukan rumus untuk menghasilkan
bilangan prima. Sejauh ini,semua upaya adalah, 9+2+1=12.
belum
lengkap. Di sisi lain, terdapat beberapa hasil
yang negatif. Di bawah ini suatu khas yang berhubungan dengan Goldbach:
Teorema 1.3b.
untuk setiap bilangan bulat m,tidak ada
bentuk polinomial
dengan
koefisien bilangn bulat sehingga
adalah bilangan prima untuk semua bilangan bulat n
dengan
.
Bukti: andaikan terdapat polinomial
Dengan
bilangan bulat
dan
Jika
merupakan bilangan komposit, maka penganddaian kita
salah. Sehingga aasumsi kita adalah
=p adalah bilangan prima. Maka
dengan i
merupakan bilangan bulat positif.
Perhatikan
bahwa
karena
itu
adalah
kelipatan dari p. Hal ini menunjukkan bahwa
adalah
kelipatan dari p. Karena
adalah kelipatan dari p. Dari asumsi kita
juga merupakan bilangan prima. Krena itu kemungkinan
nilai dari
adalah 0,p, dan
–p untuk setiap i bilangan bulat positif
. di sisi lain persamaan
dapat punya
akar paling banyak 3k. Oleh sebab itu
terdapat tak berhingga i sedemikian hingga
bukanlah solusi
dari persamaan
. Kita mendapatkan sebuah kontradiksi. Karena itu
pengandaian kita harus diingkar. Tidak ada polinomial yang semua koefisiennya
merupakan bilangan prima.
Tidak ada
cara yang pasti untuk menentukan bilangan prima, kepadatan dari bilangan prima
(yaitu, rata-rata yang terlihat dari bilangan prima dan bilangan bulat)telah
diketahui sekitar 100 tahun yang lalu. hasil luar biasa
di bidang matematika ini pada analitik teori bilangan diperlihatkan sebagai
berikut
Dimana
menandakan dari bilangan prima
. Hubungan di atas dikenal sebagai teori bilangan
prima. Hal ini telah dibuktikan oleh Hamadard dan De la Vallee Poussin pada
tahun 1896. Satu keunsuran kecuali bukti yang sulit telah diberikan oleh Erdos
dan Selberg.