Bagian 2.7 Sage
Banyak sifat objek aljabar yang akan kita pelajari dapat ditentukan dari sifat bilangan bulat yang terkait. Sage mempunyai banyak fungsi canggih untuk menganalisis bilangan bulat.
Subbagian 2.7.1 Algoritma Pembagian
Kode
a % b mengembalikan sisa pembagian \(a\) oleh \(b\text{.}\) Dengan kata lain, hasilnya adalah bilangan bulat unik \(r\) sedemikian sehingga (1) \(0\leq r\lt b\text{,}\) dan (2) \(a=bq+r\) untuk suatu bilangan bulat \(q\) (hasil bagi), sebagaimana dijamin oleh Algoritma Pembagian (Teorema 2.2.1). Maka \((a-r)/b\) akan sama dengan \(q\text{.}\) Sebagai contoh,
Kode Sage (cadangan statis)
r = 14 % 3 r
Keluaran referensi (cadangan statis)
2
Kode Sage (cadangan statis)
q = (14 - r)/3 q
Keluaran referensi (cadangan statis)
4
Hasil bagi dan sisa juga dapat diperoleh sekaligus dengan metode
.quo_rem() (hasil bagi dan sisa).
Kode Sage (cadangan statis)
a = 14 b = 3 a.quo_rem(b)
Keluaran referensi (cadangan statis)
(4, 2)
Sisa nol menunjukkan keterbagian. Jadi,
(a % b) == 0 akan mengembalikan True jika \(b\) membagi \(a\text{,}\) dan jika tidak, akan mengembalikan False.
Kode Sage (cadangan statis)
(20 % 5) == 0
Keluaran referensi (cadangan statis)
True
Kode Sage (cadangan statis)
(17 % 4) == 0
Keluaran referensi (cadangan statis)
False
Metode
.divides() merupakan pilihan lain.
Kode Sage (cadangan statis)
c = 5 c.divides(20)
Keluaran referensi (cadangan statis)
True
Kode Sage (cadangan statis)
d = 4 d.divides(17)
Keluaran referensi (cadangan statis)
False
Subbagian 2.7.2 Faktor Persekutuan Terbesar
Faktor persekutuan terbesar dari \(a\) dan \(b\) diperoleh dengan perintah
gcd(a, b), dengan \(a\) dan \(b\) berupa bilangan bulat pada penggunaan awal kita. Kelak, \(a\) dan \(b\) dapat berupa objek lain yang mempunyai gagasan keterbagian dan “kebesaran,” seperti polinomial. Sebagai contoh,
Kode Sage (cadangan statis)
gcd(2776, 2452)
Keluaran referensi (cadangan statis)
4
Kita dapat menggunakan perintah
gcd untuk menentukan apakah sepasang bilangan bulat relatif prima.
Kode Sage (cadangan statis)
a = 31049 b = 2105 gcd(a, b) == 1
Keluaran referensi (cadangan statis)
True
Kode Sage (cadangan statis)
a = 3563 b = 2947 gcd(a, b) == 1
Keluaran referensi (cadangan statis)
False
Perintah
xgcd(a,b) (“FPB diperluas”) mengembalikan suatu tripel yang elemen pertamanya merupakan faktor persekutuan terbesar dari \(a\) dan \(b\) (seperti pada perintah gcd(a,b) di atas), sedangkan dua elemen berikutnya merupakan nilai \(r\) dan \(s\) sedemikian sehingga \(ra+sb=\gcd(a,b)\text{.}\)
Kode Sage (cadangan statis)
xgcd(633,331)
Keluaran referensi (cadangan statis)
(1, -137, 262)
Bagian-bagian tripel dapat diekstrak dengan menggunakan
[ ] (“pengindeksan”) untuk mengakses entri-entri tripel, dimulai dengan entri pertama sebagai nomor 0. Sebagai contoh, kode berikut seharusnya selalu mengembalikan hasil True, sekalipun Anda mengubah nilai a dan b. Cobalah mengubah nilai a dan b di bawah ini untuk melihat bahwa hasilnya selalu True.
Kode Sage (cadangan statis)
a = 633 b = 331 extended = xgcd(a, b) g = extended[0] r = extended[1] s = extended[2] g == r*a + s*b
Keluaran referensi (cadangan statis)
True
Mempelajari blok kode ini akan sangat membantu Anda memanfaatkan keluaran Sage secara optimal. Perhatikan bahwa
= digunakan untuk menetapkan suatu nilai kepada variabel, sedangkan, seperti pada baris terakhir, == digunakan untuk membandingkan dua objek berdasarkan kesamaan.
Subbagian 2.7.3 Bilangan Prima dan Faktorisasi
Metode
.is_prime() menentukan apakah suatu bilangan bulat prima atau tidak.
Kode Sage (cadangan statis)
a = 117371 a.is_prime()
Keluaran referensi (cadangan statis)
True
Kode Sage (cadangan statis)
b = 14547073 b.is_prime()
Keluaran referensi (cadangan statis)
False
Kode Sage (cadangan statis)
b == 1597 * 9109
Keluaran referensi (cadangan statis)
True
Perintah
random_prime(a, proof=True) menghasilkan bilangan prima acak antara \(2\) dan \(a\text{.}\) Bereksperimenlah dengan menjalankan dua sel komputasi berikut beberapa kali. (Mengganti proof=True dengan proof=False akan mempercepat pencarian, tetapi ada peluang yang sangat, sangat, sangat kecil bahwa hasilnya bukan prima.)
Kode Sage (cadangan statis)
a = random_prime(10^21, proof=True) a
Keluaran referensi (cadangan statis)
424729101793542195193
Kode Sage (cadangan statis)
a.is_prime()
Keluaran referensi (cadangan statis)
True
Perintah
prime_range(a, b) mengembalikan daftar terurut semua bilangan prima dari \(a\) hingga \(b-1\text{,}\) termasuk kedua batas tersebut. Sebagai contoh,
Kode Sage (cadangan statis)
prime_range(500, 550)
Keluaran referensi (cadangan statis)
[503, 509, 521, 523, 541, 547]
Perintah
next_prime(a) dan previous_prime(a) merupakan cara lain untuk memperoleh satu bilangan prima dengan ukuran yang diinginkan. Cobalah perintah tersebut di bawah ini jika tersedia sel komputasi kosong (sebagaimana akan tersedia jika Anda membaca melalui Sage Notebook atau versi daring). (Simbol pagar, #, digunakan untuk menandai baris “komentar”, yang tidak akan dievaluasi oleh Sage. Jadi, hapus baris ini atau mulailah pada baris di bawahnya.)
Selain memeriksa apakah bilangan bulat prima atau tidak, atau menghasilkan bilangan prima, Sage juga dapat menguraikan sebarang bilangan bulat menjadi faktor-faktor primanya, sebagaimana dijelaskan oleh Teorema Dasar Aritmetika (Teorema 2.2.7).
Kode Sage (cadangan statis)
a = 2600 a.factor()
Keluaran referensi (cadangan statis)
2^3 * 5^2 * 13
Jadi \(2600 = 2^3\times 5^2\times 13\text{,}\) dan inilah satu-satunya cara untuk menuliskan \(2600\) sebagai hasil kali bilangan prima (selain menyusun ulang urutan bilangan-bilangan prima dalam hasil kali tersebut).
Meskipun Sage mencetak faktorisasi dengan rapi, secara internal faktorisasi tersebut disimpan sebagai daftar pasangan bilangan bulat, dengan setiap pasangan terdiri atas basis (bilangan prima) dan eksponen (bilangan bulat positif). Pelajari bagian berikut dengan saksama, karena bagian ini merupakan latihan yang baik untuk mengolah keluaran Sage berbentuk daftar.
Kode Sage (cadangan statis)
a = 2600 factored = a.factor() first_term = factored[0] first_term
Keluaran referensi (cadangan statis)
(2, 3)
Kode Sage (cadangan statis)
second_term = factored[1] second_term
Keluaran referensi (cadangan statis)
(5, 2)
Kode Sage (cadangan statis)
third_term = factored[2] third_term
Keluaran referensi (cadangan statis)
(13, 1)
Kode Sage (cadangan statis)
first_prime = first_term[0] first_prime
Keluaran referensi (cadangan statis)
2
Kode Sage (cadangan statis)
first_exponent = first_term[1] first_exponent
Keluaran referensi (cadangan statis)
3
Sel komputasi berikut menampilkan bentuk internal faktorisasi dengan meminta daftar yang sebenarnya. Kita juga menunjukkan cara menentukan dengan tepat banyaknya suku dalam faktorisasi menggunakan perintah panjang,
len().
Kode Sage (cadangan statis)
list(factored)
Keluaran referensi (cadangan statis)
[(2, 3), (5, 2), (13, 1)]
Kode Sage (cadangan statis)
len(factored)
Keluaran referensi (cadangan statis)
3
Dapatkah Anda mengekstrak dua bilangan prima berikutnya, beserta eksponennya, dari
a?
