Bagaimana menyelesaikan persamaan Diophantine linier

Pengarang: Mark Sanchez
Tanggal Pembuatan: 5 Januari 2021
Tanggal Pembaruan: 1 Juli 2024
Anonim
M903 Teori Bilangan : Persamaan Diophantine
Video: M903 Teori Bilangan : Persamaan Diophantine

Isi

Untuk menyelesaikan persamaan Diophantine linier, Anda perlu menemukan nilai variabel "x" dan "y", yang merupakan bilangan bulat. Solusi integer lebih kompleks dari biasanya dan membutuhkan serangkaian tindakan tertentu. Pertama, Anda perlu menghitung faktor persekutuan terbesar (FPB) dari koefisien, dan kemudian menemukan solusinya. Setelah Anda menemukan satu solusi bilangan bulat untuk persamaan linier, Anda dapat menggunakan pola sederhana untuk menemukan jumlah tak terbatas dari solusi lain.

Langkah

Bagian 1 dari 4: Cara Menulis Persamaan

  1. 1 Tuliskan persamaan dalam bentuk standar. Persamaan linier adalah persamaan yang eksponen variabelnya tidak melebihi 1. Untuk menyelesaikan persamaan linier tersebut, pertama-tama tuliskan dalam bentuk standar. Bentuk standar persamaan linear terlihat seperti ini: SEBUAHx+Bkamu=C{ displaystyle Axe + By = C}, di mana SEBUAH,B{} gaya tampilan A, B} dan C{} gaya tampilan C} - bilangan bulat.
    • Jika persamaan diberikan dalam bentuk yang berbeda, bawa ke bentuk standar menggunakan operasi aljabar dasar. Misalkan diberikan persamaan 23x+4kamu−7x=−3kamu+15{ gaya tampilan 23x + 4th-7x = -3y + 15}... Berikan istilah yang mirip dan tulis persamaannya seperti ini: 16x+7kamu=15{ gaya tampilan 16x + 7y = 15}.
  2. 2 Sederhanakan persamaan (jika mungkin). Saat Anda menulis persamaan dalam bentuk standar, lihat koefisiennya SEBUAH,B{} gaya tampilan A, B} dan C{} gaya tampilan C}... Jika peluang ini memiliki GCD, bagi ketiga peluang dengannya. Solusi untuk persamaan yang disederhanakan seperti itu juga akan menjadi solusi untuk persamaan aslinya.
    • Misalnya, jika ketiga koefisien itu genap, bagilah dengan setidaknya 2. Misalnya:
      • 42x+36kamu=48{ gaya tampilan 42x + 36y = 48} (semua anggota habis dibagi 2)
      • 21x+18kamu=24{ gaya tampilan 21x + 18 tahun = 24} (sekarang semua anggota habis dibagi 3)
      • 7x+6kamu=8{ gaya tampilan 7x + 6y = 8} (persamaan ini tidak dapat disederhanakan lagi)
  3. 3 Periksa apakah persamaan dapat diselesaikan. Dalam beberapa kasus, Anda dapat langsung menyatakan bahwa persamaan tersebut tidak memiliki solusi. Jika koefisien "C" tidak habis dibagi dengan FPB dari koefisien "A" dan "B", persamaan tersebut tidak memiliki solusi.
    • Misalnya, jika kedua koefisien SEBUAH{ gaya tampilan A} dan B{} gaya tampilan B} genap, maka koefisien C{} gaya tampilan C} harus genap. Tapi jika C{} gaya tampilan C} aneh, maka tidak ada solusi.
      • persamaan 2x+4kamu=21{ gaya tampilan 2x + 4y = 21} tidak ada solusi bilangan bulat.
      • persamaan 5x+10kamu=17{ gaya tampilan 5x + 10y = 17} tidak ada solusi bilangan bulat karena ruas kiri persamaan habis dibagi 5 dan ruas kanan tidak habis.

Bagian 2 dari 4: Cara menulis algoritma Euclid

  1. 1 Memahami algoritma Euclid. Ini adalah serangkaian pembagian berulang di mana sisa sebelumnya digunakan sebagai pembagi berikutnya. Pembagi terakhir yang membagi bilangan secara integral adalah pembagi persekutuan terbesar (FPB) dari kedua bilangan tersebut.
    • Sebagai contoh, mari kita cari KPK dari bilangan 272 dan 36 menggunakan algoritma Euclid:
      • 272=7∗36+20{ gaya tampilan 272 = 7 * 36 + 20} - Bagilah bilangan yang lebih besar (272) dengan bilangan yang lebih kecil (36) dan perhatikan sisanya (20);
      • 36=1∗20+16{ gaya tampilan 36 = 1 * 20 + 16} - bagi pembagi sebelumnya (36) dengan sisa sebelumnya (20). Perhatikan residu baru (16);
      • 20=1∗16+4{ gaya tampilan 20 = 1 * 16 + 4} - bagi pembagi sebelumnya (20) dengan sisa sebelumnya (16). Perhatikan residu baru (4);
      • 16=4∗4+0{ gaya tampilan 16 = 4 * 4 + 0} - Bagilah pembagi sebelumnya (16) dengan sisa sebelumnya (4). Karena sisanya adalah 0, kita dapat mengatakan bahwa 4 adalah FPB dari dua bilangan asli 272 dan 36.
  2. 2 Terapkan algoritma Euclid pada koefisien "A" dan "B". Ketika Anda menulis persamaan linier dalam bentuk standar, tentukan koefisien "A" dan "B" dan kemudian terapkan algoritma Euclid untuk menemukan GCD. Misalnya, diberikan persamaan linier 87x−64kamu=3{ gaya tampilan 87x-64y = 3}.
    • Berikut adalah algoritma Euclid untuk koefisien A = 87 dan B = 64:
      • 87=1∗64+23{ gaya tampilan 87 = 1 * 64 + 23}
      • 64=2∗23+18{ displaystyle 64 = 2 * 23 + 18}
      • 23=1∗18+5{ gaya tampilan 23 = 1 * 18 + 5}
      • 18=3∗5+3{ gaya tampilan 18 = 3 * 5 + 3}
      • 5=1∗3+2{ gaya tampilan 5 = 1 * 3 + 2}
      • 3=1∗2+1{ gaya tampilan 3 = 1 * 2 + 1}
      • 2=2∗1+0{ gaya tampilan 2 = 2 * 1 + 0}
  3. 3 Temukan Faktor Persekutuan Terbesar (FPB). Karena pembagi terakhir adalah 1, GCD 87 dan 64 adalah 1. Jadi, 87 dan 64 adalah bilangan prima relatif satu sama lain.
  4. 4 Analisis hasilnya. Ketika Anda menemukan koefisien gcd SEBUAH{ gaya tampilan A} dan B{} gaya tampilan B}, bandingkan dengan koefisien C{} gaya tampilan C} persamaan aslinya. Jika C{} gaya tampilan C} habis dibagi gcd SEBUAH{ gaya tampilan A} dan B{} gaya tampilan B}, persamaan memiliki solusi bilangan bulat; jika tidak, persamaan tidak memiliki solusi.
    • Misalnya persamaan 87x−64kamu=3{ gaya tampilan 87x-64y = 3} dapat diselesaikan karena 3 habis dibagi 1 (gcd = 1).
    • Misalkan GCD = 5. 3 tidak habis dibagi 5, jadi persamaan ini tidak memiliki solusi bilangan bulat.
    • Seperti yang ditunjukkan di bawah ini, jika suatu persamaan memiliki satu solusi bilangan bulat, persamaan tersebut juga memiliki banyak solusi bilangan bulat lainnya.

Bagian 3 dari 4: Cara Menemukan Solusi Menggunakan Algoritma Euclid

  1. 1 Beri nomor langkah-langkah untuk menghitung GCD. Untuk mencari solusi persamaan linier, Anda perlu menggunakan algoritma Euclidean sebagai dasar untuk proses substitusi dan penyederhanaan.
    • Mulailah dengan memberi nomor pada langkah-langkah untuk menghitung GCD. Proses perhitungannya terlihat seperti ini:
      • Langkah 1:87=(1∗64)+23{ displaystyle { teks {Langkah 1}}: 87 = (1 * 64) +23}
      • Langkah 2:64=(2∗23)+18{ displaystyle { teks {Langkah 2}}: 64 = (2 * 23) +18}
      • Langkah 3:23=(1∗18)+5{ displaystyle { teks {Langkah 3}}: 23 = (1 * 18) +5}
      • Langkah 4:18=(3∗5)+3{ displaystyle { teks {Langkah 4}}: 18 = (3 * 5) +3}
      • Langkah 5:5=(1∗3)+2{ displaystyle { teks {Langkah 5}}: 5 = (1 * 3) +2}
      • Langkah 6:3=(1∗2)+1{ displaystyle { teks {Langkah 6}}: 3 = (1 * 2) +1}
      • Langkah 7:2=(2∗1)+0{ displaystyle { teks {Langkah 7}}: 2 = (2 * 1) +0}
  2. 2 Perhatikan langkah terakhir, di mana ada sisa. Tulis ulang persamaan untuk langkah ini untuk mengisolasi sisanya.
    • Dalam contoh kita, langkah terakhir dengan sisa adalah langkah 6. Sisanya adalah 1. Tulis ulang persamaan pada langkah 6 sebagai berikut:
      • 1=3−(1∗2){ gaya tampilan 1 = 3- (1 * 2)}
  3. 3 Pisahkan sisa langkah sebelumnya. Proses ini adalah langkah-demi-langkah "naik". Setiap kali Anda akan mengisolasi sisanya dalam persamaan pada langkah sebelumnya.
    • Pisahkan sisa persamaan pada Langkah 5:
      • 2=5−(1∗3){ gaya tampilan 2 = 5- (1 * 3)} atau 2=5−3{ gaya tampilan 2 = 5-3}
  4. 4 Substitusi dan sederhanakan. Perhatikan bahwa persamaan pada Langkah 6 berisi angka 2, dan dalam persamaan pada Langkah 5, angka 2 diisolasi. Jadi, alih-alih "2" dalam persamaan di langkah 6, gantikan ekspresi di langkah 5:
    • 1=3−2{ gaya tampilan 1 = 3-2} (persamaan langkah 6)
    • 1=3−(5−3){ gaya tampilan 1 = 3- (5-3)} (bukan 2, ekspresi diganti)
    • 1=3−5+3{ gaya tampilan 1 = 3-5 + 3} (kurung terbuka)
    • 1=2(3)−5{ gaya tampilan 1 = 2 (3) -5} (disederhanakan)
  5. 5 Ulangi proses substitusi dan penyederhanaan. Ulangi proses yang dijelaskan, bergerak melalui algoritma Euclidean dalam urutan terbalik. Setiap kali Anda akan menulis ulang persamaan dari langkah sebelumnya dan memasukkannya ke dalam persamaan terakhir yang Anda dapatkan.
    • Langkah terakhir yang kita lihat adalah langkah 5. Jadi lanjutkan ke langkah 4 dan pisahkan sisanya dalam persamaan untuk langkah itu:
      • 3=18−(3∗5){ gaya tampilan 3 = 18- (3 * 5)}
    • Substitusi ekspresi ini untuk "3" dalam persamaan terakhir:
      • 1=2(18−3∗5)−5{ gaya tampilan 1 = 2 (18-3 * 5) -5}
      • 1=2(18)−6(5)−5{ gaya tampilan 1 = 2 (18) -6 (5) -5}
      • 1=2(18)−7(5){ gaya tampilan 1 = 2 (18) -7 (5)}
  6. 6 Lanjutkan dengan proses substitusi dan penyederhanaan. Proses ini akan diulang sampai Anda mencapai langkah awal dari algoritma Euclidean. Tujuan dari proses ini adalah untuk menulis persamaan dengan koefisien 87 dan 64 dari persamaan asli yang akan diselesaikan. Dalam contoh kami:
    • 1=2(18)−7(5){ gaya tampilan 1 = 2 (18) -7 (5)}
    • 1=2(18)−7(23−18){ gaya tampilan 1 = 2 (18) -7 (23-18)} (mengganti ekspresi dari langkah 3)
      • 1=2(18)−7(23)+7(18){ gaya tampilan 1 = 2 (18) -7 (23) +7 (18)}
      • 1=9(18)−7(23){ gaya tampilan 1 = 9 (18) -7 (23)}
    • 1=9(64−2∗23)−7(23){ gaya tampilan 1 = 9 (64-2 * 23) -7 (23)} (mengganti ekspresi dari langkah 2)
      • 1=9(64)−18(23)−7(23){ gaya tampilan 1 = 9 (64) -18 (23) -7 (23)}
      • 1=9(64)−25(23){ gaya tampilan 1 = 9 (64) -25 (23)}
    • 1=9(64)−25(87−64){ gaya tampilan 1 = 9 (64) -25 (87-64)} (mengganti ekspresi dari langkah 1)
      • 1=9(64)−25(87)+25(64){ gaya tampilan 1 = 9 (64) -25 (87) +25 (64)}
      • 1=34(64)−25(87){ gaya tampilan 1 = 34 (64) -25 (87)}
  7. 7 Tulis ulang persamaan yang dihasilkan sesuai dengan koefisien aslinya. Ketika Anda kembali ke langkah pertama dari algoritma Euclidean, Anda akan melihat bahwa persamaan yang dihasilkan mengandung dua koefisien dari persamaan aslinya. Tulis ulang persamaan tersebut sehingga urutan suku-sukunya sesuai dengan koefisien persamaan aslinya.
    • Dalam contoh kita, persamaan asli 87x−64kamu=3{ gaya tampilan 87x-64y = 3}... Oleh karena itu, tulis ulang persamaan yang dihasilkan sehingga koefisiennya menjadi garis.Berikan perhatian khusus pada koefisien "64". Dalam persamaan asli, koefisien ini negatif, dan dalam algoritma Euclidean, itu positif. Oleh karena itu, faktor 34 harus dibuat negatif. Persamaan akhir akan ditulis seperti ini:
      • 87(−25)−64(−34)=1{ gaya tampilan 87 (-25) -64 (-34) = 1}
  8. 8 Terapkan pengganda yang sesuai untuk menemukan solusi. Perhatikan bahwa dalam contoh kita, FPB = 1, jadi persamaan akhirnya adalah 1. Tetapi persamaan aslinya (87x-64y) adalah 3. Oleh karena itu, semua suku dalam persamaan akhir harus dikalikan dengan 3 untuk mendapatkan solusinya:
    • 87(−25∗3)−64(−34∗3)=1∗3{ displaystyle 87 (-25 * 3) -64 (-34 * 3) = 1 * 3}
    • 87(−75)−64(−102)=3{ gaya tampilan 87 (-75) -64 (-102) = 3}
  9. 9 Tuliskan solusi bilangan bulat dari persamaan tersebut. Angka-angka yang dikalikan dengan koefisien persamaan asli adalah solusi untuk persamaan itu.
    • Dalam contoh kita, tulis solusinya sebagai pasangan koordinat: (x,kamu)=(−75,−102){ gaya tampilan (x, y) = (- 75, -102)}.

Bagian 4 dari 4: Temukan Solusi Lain yang Tak Terbatas

  1. 1 Pahami bahwa ada banyak solusi yang tak terbatas. Jika persamaan linear memiliki satu solusi bilangan bulat, maka persamaan tersebut harus memiliki banyak solusi bilangan bulat. Berikut adalah bukti singkatnya (dalam bentuk aljabar):
    • SEBUAHx+Bkamu=C{ displaystyle Axe + By = C}
    • SEBUAH(x+B)+B(kamu−SEBUAH)=C{ gaya tampilan A (x + B) + B (y-A) = C} (jika Anda menambahkan "B" ke "x" dan mengurangi "A" dari "y", nilai persamaan asli tidak akan berubah)
  2. 2 Catat nilai x dan y asli. Template untuk menghitung solusi (tak terbatas) berikutnya dimulai dengan satu-satunya solusi yang telah Anda temukan.
    • Dalam contoh kita, solusinya adalah sepasang koordinat (x,kamu)=(−75,−102){ gaya tampilan (x, y) = (- 75, -102)}.
  3. 3 Tambahkan faktor "B" ke nilai "x". Lakukan ini untuk menemukan nilai x baru.
    • Dalam contoh kita, x = -75, dan B = -64:
      • x=−75+(−64)=−139{ gaya tampilan x = -75 + (- 64) = - 139}
    • Jadi, nilai baru "x": x = -139.
  4. 4 Kurangi faktor "A" dari nilai "y". Agar nilai persamaan asli tidak berubah, saat menambahkan satu angka ke "x", Anda harus mengurangi angka lain dari "y".
    • Dalam contoh kita, y = -102, dan A = 87:
      • kamu=−102−87=−189{ gaya tampilan y = -102-87 = -189}
    • Jadi, nilai baru untuk "y": y = -189.
    • Pasangan koordinat baru akan ditulis seperti ini: (x,kamu)=(−139,−189){ gaya tampilan (x, y) = (- 139, -189)}.
  5. 5 Periksa solusinya. Untuk memverifikasi bahwa pasangan koordinat baru adalah solusi dari persamaan asli, masukkan nilainya ke dalam persamaan.
    • 87x−64kamu=3{ gaya tampilan 87x-64y = 3}
    • 87(−139)−64(−189)=3{ gaya tampilan 87 (-139) -64 (-189) = 3}
    • 3=3{ gaya tampilan 3 = 3}
    • Karena kesetaraan terpenuhi, keputusannya benar.
  6. 6 Tuliskan ekspresi untuk menemukan banyak solusi. Nilai "x" akan sama dengan solusi asli ditambah kelipatan dari faktor "B". Ini dapat ditulis sebagai ekspresi berikut:
    • x (k) = x + k (B), di mana “x (k)” adalah himpunan nilai “x” ​​dan “x” adalah nilai asli (pertama) dari “x” yang Anda temukan.
      • Dalam contoh kami:
      • x(k)=−75−64k{ gaya tampilan x (k) = - 75-64k}
    • y (k) = y-k (A), di mana y (k) adalah himpunan nilai y dan y adalah nilai y asli (pertama) yang Anda temukan.
      • Dalam contoh kami:
      • kamu(k)=−102−87k{ gaya tampilan y (k) = - 102-87k}

Posting Yang Menarik

Bagaimana bermeditasi dengan suara hati Anda
Bagaimana bermeditasi dengan suara hati Anda
Cara memasak dada ayam beku
Cara memasak dada ayam beku
Cara membuat pestisida organik
Cara membuat pestisida organik
Bagaimana melakukan trakeostomi dengan benar
Bagaimana melakukan trakeostomi dengan benar