Koprima (bilangan)

Dua bilangan bulat a dan b dikatakan koprima (relatif prima atau saling prima) apabila FPB kedua bilangan adalah 1. Contohnya adalah 4 dan 9 karena fpb(4,9)=1. Karena algoritme Euklidean merupakan cara yang cepat untuk menghitung FPB, algoritme tersebut juga merupakan cara yang cepat untuk memeriksa sifat koprima.

Notasi

Notasi standar untuk bilangan bulat yang relatif prima $a$ dan $b$ adalah: $gcd(a, b) = 1$ (bahasa Indonesia: $fpb(a, b) = 1$ dan $(a, b) = 1$ . Pada makalah tahun 1989, Graham, Knuth, dan Patashnik mengusulkan notasi $a\perp b$ digunakan untuk menandakan bahwa $a$ dan $b$ relatif prima dan istilah "prima" digunakan bukannya koprima (misalnya $a$ prima terhadap $b$ ).^[1]

Sifat

Bilangan 1 dan −1 adalah satu-satunya bilangan bulat yang koprima dengan setiap bilangan bulat, dan satu-satunya yang koprima dengan 0.

Beberapa pernyataan berikut bersifat ekuivalen dengan menyebut $a$ dan $b$ koprima:

Tidak ada bilangan prima yang membagi baik $a$ maupun $b$ .
Terdapat bilangan bulat $x$ dan $y$ sehingga $ax + by = 1$ (see identitas Bézout).
Bilangan bulat $b$ punya invers perkalian modulo $a$ , artinya ada suatu bilangan bulat $y$ yang menyebabkan $by \equiv 1 (mod a)$ .
Setiap pasang relasi kekongruenan dengan variabel $x$ , dalam bentuk $x \equiv k (mod a)$ dan $x \equiv m (mod b)$ , punya penyelesaian (teorema sisa Tiongkok); bahkan penyelesaiannya bisa digambarkan dengan satu relasi kekongruenan modulo $ab$ .
Kelipatan persekutuan terkecil $a$ dan $b$ sama dengan hasil kali $ab$ , dalam bentuk persamaan $lcm(a, b) = ab$ .^[2]

Catatan kaki

^ Graham, R. L.; Knuth, D. E.; Patashnik, O. (1989), Concrete Mathematics / A Foundation for Computer Science, Addison-Wesley, hlm. 115, ISBN 0-201-14236-8
^ Ore 1988, p. 47