Die Funktion Chinrem; Die Funktion Egcd - HP 49g+ Benutzeranleitung

Modul definieren. So können wir z.B. ein bestimmtes Polynom P(X) als P(X) =
2
X (mod X ) definieren oder ein anderen Polynom als Q(X) = X + 1 (mod X-2).
Ein Polynom P(X) ist Teil eines arithmetischen Ringes von Polynomen des
Moduls M(X), wenn es ein drittes Polynom Q(X) gibt, und zwar so, dass
(P(X) – Q(X)) ein Vielfaches von M(X) darstellt. Dann würden wir schreiben:
P(X) ≡ Q(X) (mod M(X)). Letzterer Ausdruck wird als "P(X) ist kongruent mit
Q(X), modulo M(X)" interpretieren.

Die Funktion CHINREM

CHINREM steht für CHINese REMainder (Chinesischer Restesatz).
diesem Befehl kodierte Operation, löst ein System von von Kongruenten unter
Anwendung des Chinesischen Restesatz Theorems . Dieser Befehl kann mit
Polynomen, wie auch mit Integerzahlen (Funktion ICHINREM) verwendet
werden. Die Eingabe besteht aus zwei Vektoren [expression_1, modulo_1]
und [expression_2, modulo_2] – (Ausdruck_2, Modul_2) und (Ausdruck_2,
Modul_2). Die Ausgabe ist ein Vektor der [expression_3, modulo_3], wobei
modulo_3 mit der Produkt verwandt ist (modulo_1)⋅(modulo_2) . [(Ausdruck_3,
Modul_3) und (Modul_1)⋅ (Modul_2)].
1'],['X+1','X^2']) = ['X+1',-(X^4-X^2)]
Ansatz für das Chinesische Restsatz Theorem für Integerzahlen
Wenn m , m ,...,m paarweise teilerfremde natürliche Zahlen und a
1 2 r
a irgendwelche Integerzahlen sind, dann gibt es genau eine Integer x,
r
welche simultan die folgenden Kongruenzen erfüllt: x ≡ a
), ..., x ≡ a
(mod m (mod m
2 r
sind alle anderen Lösungen kongruent und gleich dem Produkt von m
m .
r

Die Funktion EGCD

EGCD steht für Extended Greatest Common Divisor (erweiterter (Euklidischer
Algorithmus) größter gemeinsamer Teiler). Für zwei Polynome A(X) und B(X),
erzeugt die Funktion EGCD die Polynome C(X), U(X), and V(X), so dass C(X)
= U(X)*A(X) + V(X)*B(X). So z.B. für A(X) = X^2+1, B(X) = X^2-1,
EGCD(A(X),B(X)) = {2, 1, -1}. d.h., 2 = 1*( X^2+1')-1*( X^2-1). Auch
Beispiel: CHINREM(['X+1', 'X^2-
). Zusätzlich, wenn x = a eine Lösung ist, dann
r
Die in
, a , ...,
1 2
), x ≡ a
(mod m
1 1 2
⋅m ⋅ ...
1 2
Seite 5-21