Aplikasi basis Gröbner pada penyelesaian sistem kongruensi Aplikasi basis Gröbner pada penyelesaian sistem kongruensi atas ring polinomial multivariabel dan implementasi pada Singular-CAS

INDONESIA

Diberikan ring polinomial multivariabel k[x_1,x_2,…,x_n] dengan k adalah suatu lapangan dan n adalah bilangan bulat positif. Basis Gröbner bagi ideal I⊆k[x_1,x_2,…,x_n] adalah suatu himpunan pembangun bagi I yang memiliki sifat penting dalam pembagian polinomial, yaitu sisa pembagian polinomial oleh basis Gröbner bersifat tunggal. Konsep basis Gröbner dapat digunakan untuk menyelesaikan sistem persamaan polinomial pada k[x_1,x_2,…,x_n]. Misalkan f,g∈k[x_1,x_2,…,x_n]. Polinomial f dikatakan kongruen g modulo I jika f-g∈I. Diberikan sistem kongruensi atas k[x_1,x_2,…,x_n], yakni kumpulan kongruensi polinomial modulo ideal yang simultan. Masing-masing kongruensi pada sistem kongruensi tersebut dapat diubah menjadi persamaan polinomial, sehingga terbentuk sistem persamaan polinomial. Oleh karena itu, tujuan dari penelitian ini adalah mengkaji cara menyelesaikan sistem kongruensi atas k[x_1,x_2,…,x_n] dengan basis Gröbner. Kemudian metode dari penyelesaian sistem kongruensi atas k[x_1,x_2,…,x_n] dengan basis Gröbner diimplementasikan pada Singular-CAS. Berdasarkan hasil dan pembahasan, untuk menyelesaikan sistem kongruensi atas k[x_1,x_2,…,x_n], pertama bentuk ideal J dan polinomial g yang bersesuaian dengan sistem kongruensi. Kemudian cari basis Gröbner G bagi ideal J dengan menetapkan terlebih dahulu order eliminasi. Setelah itu cari sisa pembagian dari g oleh G. Sisa pembagian ini menentukan eksistensi dari solusi bagi sistem kongruensi yang diberikan. Langkah penyelesaian ini kemudian diimplementasikan dalam bentuk dua prosedur yang berbeda pada Singular-CAS. Kesimpulan pada penelitian ini adalah diperoleh metode penyelesian sistem kongruensi atas k[x_1,x_2,…,x_n] dengan basis Gröbner dan metode penyelesaian tersebut berhasil diimplementasikan pada Singular-CAS dalam bentuk dua prosedur.

ENGLISH

Given a multivariable polynomial ring k[x_1,x_2,…,x_n] where k is a field and n is a positive integer. A Gröbner basis for an ideal I⊆k[x_1,x_2,…,x_n] is a generating set for I that has an important property in polynomial division, namely that the remainder of a polynomial division by a Gröbner basis is unique. The concept of Gröbner bases can be used to solve systems of polynomial equations in k[x_1,x_2,…,x_n]. Let f,g∈k[x_1,x_2,…,x_n]. The polynomial f is said to be congruent to g modulo I if f-g∈I. Given a system of congruence equations over k[x_1,x_2,…,x_n], that is a collection of simultaneous polynomial congruences modulo an ideal. each congruence in the congruence system can be transformed into a polynomial equation, thus forming a system of polynomial equations. Therefore, the purpose of this research is to examine how to solve systems of congruence equations over k[x_1,x_2,…,x_n] using Gröbner bases. Then, the method for solving systems of congruence equations over k[x_1,x_2,…,x_n] using Gröbner bases is implemented in Singular-CAS. Based on the results and discussion, to solve a system of congruence equations over k[x_1,x_2,…,x_n ], first form an ideal J and a polynomial g corresponding to the congruence system. Then, compute the Gröbner basis G for J by first determining the elimination order. After that, find the remainder of the division of g by G. The remainder of the division process determines the existence of a solution for the given congruence system. These methods then implemented in the form of two different procedures in Singular-CAS.

ARABIC

بفرض وجود حلقة كثيرة حدود متعددة المتغيرات k[x_1,x_2,…,x_n] حيث k يمثل حقلاً و n عدد صحيح موجب. قاعدة جروبنر للمثالي I⊆k[x_1,x_2,…,x_n] هي مجموعة مولدة لـ Iتمتلك خاصية مهمة في قسمة كثيرات الحدود، وهي أن باقي قسمة كثيرة الحدود على قاعدة جروبنر يكون وحيدًا. يمكن استخدام مفهوم قواعد جروبنر لحل أنظمة معادلات كثيرات الحدود في k[x_1,x_2,…,x_n]. نظام معادلات التطابق على k[x_1,x_2,…,x_n] هو مجموعة من تطابقات كثيرات الحدود المتزامنة بمقياس مثالي. بينما بالنسبة لكثيرتي الحدود f,g∈k[x_1,x_2,…,x_n]، يُقال إن كثيرة الحدود f تطابق gبمقياس I إذا كان f-g∈I. إذا أُعطي نظام من معادلات التطابق على k[x_1,x_2,…,x_n]، يمكن تحويل كل تطابق في هذا النظام إلى معادلة كثيرة حدود، مما يشكل نظامًا من معادلات كثيرات الحدود. لذلك، هدف هذا البحث إلى دراسة كيفية حل أنظمة معادلات التطابق على k[x_1,x_2,…,x_n] باستخدام قواعد جروبنر. بعد ذلك، تم تطبيق طريقة حل أنظمة معادلات التطابق على k[x_1,x_2,…,x_n] باستخدام قواعد جروبنر في برنامج . Singular-CAS بناءً على النتائج والمناقشة، لحل نظام معادلات التطابق على k[x_1,x_2,…,x_n]، كوّن أولاً المثالي J وكثيرة الحدود gالمتوافقة مع نظام التطابق. ثم أوجد قاعدة جروبنر G للمثالي J بتحديد ترتيب الحذف أولاً. بعد ذلك، أوجد باقي قسمة g على G. يحدد باقي القسمة هذا وجود حل لنظام التطابق المعطى. ثم ُطبقت خطوات الحل هذه في شكل إجراءين مختلفين في برنامجSingular-CAS.