Latihan 1.

1. Misalkan \(n= ab\) adalah bilangan komposit ganjil. Buktikan bahwa \(n\) dapat ditulis sebagai selisih dua kuadrat sempurna:

   \begin{equation*} n = x^2 - y^2 = (x - y)(x + y)\text{.} \end{equation*}

   Akibatnya, bilangan bulat positif ganjil dapat difaktorkan tepat ketika kita dapat menemukan bilangan bulat \(x\) dan \(y\) sedemikian sehingga \(n = x^2 - y^2\text{.}\)
2. Tulislah program yang menerapkan algoritma faktorisasi berikut berdasarkan pengamatan pada bagian (a). Ekspresi ceiling(sqrt(n)) berarti bilangan bulat terkecil yang lebih besar daripada atau sama dengan akar kuadrat \(n\text{.}\) Tulislah program lain untuk melakukan faktorisasi dengan pembagian percobaan, lalu bandingkan kecepatan kedua algoritma. Algoritma mana yang lebih cepat, dan mengapa?

x := ceiling(sqrt(n))
y := 1

1 : while x^2 - y^2 > n do
    y := y + 1

if x^2 - y^2 < n then
    x := x + 1
    y := 1
    goto 1
else if x^2 - y^2 = 0 then
    a := x - y
    b := x + y
    write n = a * b