ConanDoyle21
Persamaan Diophantine adalah persamaan linier yang memuat beberapa variabel, namun harus diselesaikan dalam bilangan bulat. Bentuk paling sederhananya adalah :
ax + by = c
Persamaan Diophatine merupakan sub bab dari bab Teori Keterbagian, tidak banyak buku yang membahas sub bab ini. Persamaan Diophantine dapat mempunyai atau tidak mempunyai penyelesaian. Contohnya . Persamaan ini tidak mempunyai jawab di himpunan bilangan bulat, persamaan ini akan mempunyai jawab di himpunan bilangan real. Dalam kasus ia mempunyai penyelesaian maka penyelesaiannya banyak. Teorema berikut memberikan syarat perlu dan cukup persamaan Diophantine mempunyai penyelesaian.
Teorema 1 Misalkan a; b dan c bilangan bulat dimana a dan b tidak keduanya nol dan d = gcd(a; b). Maka persamaan Diophantine ax + by = c mempunyai penyelesaian jika hanya jika d|c; dalam kasus ini terdapat takberhingga banyak penyelesaian. Penyelesaian-penyelesaian ini diberikan oleh :
x = x0 + b/d(n), y = y0 - a/d(n), n€Z
dimana (x0; y0) merupakan penyelesaian khusus.
Berikut diberikan algoritma untuk menentukan penyelesaian persamaan Diophantine 1. Hitung d = gcd(a; b); dengan cara langsung atau menggunakan algoritma Euclides. a = q1b + r1; 0 < r1 < b b = q2r1 + r2; 0 < r2 < r1 r1 = q3r2 + r3; 0 < r3 < r2
2. Bila d tidak sedemikian hingga c maka persamaan Diophantine tidak mempunyai penyelesaian, stop. Bila d sedemikian hingga c, tulis c = kd. 3. Temukan bilangan bulat v dan w dengan identitas bezouth sehingga av + bw = d. Kedua ruas dikalikan k diperoleh akv + bkw = kd a(kv) + b(kw) = c: Diambil x0 = kv dan y0 = kw sebagai penyelesaian khususnya. 4. Gunakan formula (1.6) untuk membangun himpunan semua penyelesaian. 1. Jika a|c dan b|c maka ab|c. 2. Jika a|bc maka a|c.
ax + by = c
Persamaan Diophatine merupakan sub bab dari bab Teori Keterbagian, tidak banyak buku yang membahas sub bab ini.
Persamaan Diophantine dapat mempunyai atau tidak mempunyai penyelesaian. Contohnya . Persamaan ini tidak mempunyai jawab di himpunan bilangan bulat, persamaan ini akan mempunyai jawab di himpunan bilangan real.
Dalam kasus ia mempunyai penyelesaian maka penyelesaiannya banyak. Teorema berikut memberikan syarat perlu dan cukup persamaan Diophantine mempunyai penyelesaian.
Teorema 1
Misalkan a; b dan c bilangan bulat dimana a dan b tidak keduanya nol dan d = gcd(a; b). Maka persamaan Diophantine ax + by = c mempunyai penyelesaian jika hanya jika d|c; dalam kasus ini terdapat takberhingga banyak penyelesaian. Penyelesaian-penyelesaian ini diberikan oleh :
x = x0 + b/d(n), y = y0 - a/d(n), n€Z
dimana (x0; y0) merupakan penyelesaian khusus.
Berikut diberikan algoritma untuk menentukan penyelesaian persamaan Diophantine
1. Hitung d = gcd(a; b); dengan cara langsung atau menggunakan algoritma Euclides.
a = q1b + r1; 0 < r1 < b
b = q2r1 + r2; 0 < r2 < r1
r1 = q3r2 + r3; 0 < r3 < r2
2. Bila d tidak sedemikian hingga c maka persamaan Diophantine tidak mempunyai penyelesaian, stop. Bila d sedemikian hingga c, tulis c = kd.
3. Temukan bilangan bulat v dan w dengan identitas bezouth sehingga av + bw = d. Kedua ruas dikalikan k diperoleh
akv + bkw = kd
a(kv) + b(kw) = c:
Diambil x0 = kv dan y0 = kw sebagai penyelesaian khususnya.
4. Gunakan formula (1.6) untuk membangun himpunan semua penyelesaian.
1. Jika a|c dan b|c maka ab|c.
2. Jika a|bc maka a|c.