| [Pengunjung (113.218.*.*)]jawaban [Cina ] | Waktu :2024-06-24 | Perluas algoritma Euclidean
Algoritma Euclidean yang diperluas, atau disingkat EXGCD, umumnya digunakan untuk menyelesaikan persamaan tak tentu, persamaan kongruensi linier, elemen terbalik dari modulo, dan sebagainya
Lemma: Kehadiran x , y sedemikian rupa sehingga gcd(a,b)=ax by
Membuktikan:
Ketika b = 0, gcd (a, b) = a, pada titik mana x = 1, y = 0
Ketika b!=0,
Biarkan ax1 by1=gcd(a,b)=gcd(b,a%b)=bx2 (a%b)y2
dan karena a%b=a-a/b*b
maka ax1 by1=bx2 (a-a/b*b)y2
ax1 by1=bx2 ay2-a/b*by2
ax1 by1=ay2 bx2-b*a/b*y2
ax1 by1=ay2 b(x2-a/b*y2)
Solusinya menghasilkan x1=y2, y1=x2-a/b*y2
Karena ketika b = 0 ada x, y adalah rangkaian solusi terakhir
Solusi untuk setiap kelompok dapat diperoleh dari kelompok yang terakhir
Jadi solusi dari kelompok pertama x , y harus ada
Terbukti
Berdasarkan bukti di atas, praktik rekursif digunakan saat menerapkan
Secara rekursif lanjutkan ke lapisan berikutnya, dan kembalikan x = 1 dan y = 0 ketika lapisan terakhir tercapai, yaitu b = 0
Kemudian menurut x = y ', y = x '-a / b / y '(x 'dan y 'adalah x dan y dari lapisan berikutnya) untuk mendapatkan solusi dari lapisan saat ini
Terus menghitung solusi dari lapisan saat ini dan kembali, dan akhirnya kembali ke lapisan pertama untuk mendapatkan solusi asli |
|
