Previous Up Next

1.25.11  Ταυτότητα Bézout : egcd gcdex

Αυτή η συνάρτηση υπολογίζει τους πολυωνυμικούς συντελεστές της ταυτότητας Bézout (επίσης γνωστής και ως Επεκταμένος Μέγιστος Κοινός Διαιρέτης — Extended Greatest Common Divisor). Δοθέντων δύο πολυωνύμων A(x),B(x), η egcd υπολογίζει 3 πολυώνυμα U(x),V(x) και D(x) τέτοια ώστε :

U(x)*A(x)+V(x)*B(x)=D(x)=GCD(A(x),B(x)) 

egcd παίρνει 2 ή 3 ορίσματα: τα πολυώνυμα A και B σαν παραστάσεις μιας μεταβλητής (εάν η μεταβλητή δεν δίνεται ορίζεται από προεπιλογή το x). Εναλλακτικά, τα A και B μπορεί να δίνονται και σαν λίστες πολυωνύμων.
Είσοδος :

egcd(x^2+2*x+1,x^2-1)

Έξοδος :

[1,-1,2*x+2]

Είσοδος :

egcd([1,2,1],[1,0,-1])

Έξοδος :

[[1],[-1],[2,2]]

Είσοδος :

egcd(y^2-2*y+1,y^2-y+2,y)

Έξοδος :

[y-2,-y+3,4]

Είσοδος :

egcd([1,-2,1],[1,-1,2])

Έξοδος :

[[1,-2],[-1,3],[4]]

Previous Up Next