Arithmetique modulaire avec des polynomes, Fonction chinrem, Fonction egcd – HP Calculatrice graphique HP 48gII Manuel d'utilisation
Page 209: Arithmétique modulaire avec des polynômes
Page 5-20
Arithmétique modulaire avec des polynômes
De la même façon que nous avons défini un anneau arithmétique fini pour les
nombres dans une section précédente, nous pouvons définir un anneau
arithmétique fini pour les polynômes avec un polynôme donné comme module.
Par exemple, nous pouvons écrire un certain polynôme P(X) comme P(X) = X
(mod X
2
) ou un autre polynôme Q(X) = X + 1 (mod X-2).
Un polynôme P(X) appartient à un anneau arithmétique fini de modules
polynomiaux M(X), s’il existe un troisième polynôme Q(X), tel que (P(X) – Q(X))
est un multiple de M(X). Nous pourrions alors écrire : P(X)
≡ Q(X) (mod M(X)).
Cette dernière expression est interprétée comme “P(X) est congru à Q(X),
modulo M(X)”.
Fonction CHINREM
CHINREM signifie CHINese REMainder (théorème Chinois). L’opération
encodée dans cette commande résout un système de deux congruences
utilisant le Théorème Chinois. Cette commande peut être utilisée avec des
polynômes, de même qu’avec des nombres entiers (fonction ICHINREM). Les
données d’entrée’ consistent en deux vecteurs [expression_1, modulo_1] et
[expression_2, modulo_2]. Les données de sortie sont un vecteur contenant
[expression_3, modulo_3], où modulo_3 est lié au produit
(modulo_1)
⋅(modulo_2). Exemple: CHINREM([‘X+1’, ‘X^2-1’],[‘X+1’,’X^2’])
= [‘X+1’,-(X^4-X^2)]
Déclaration du Théorème Chinois pour les entiers
Si m
1
, m
2
,…,m
r
sont des nombres naturels dont chaque paire est un nombre
premier relatif et : a
1
, a
2
, …, a
r
sont des entiers quelconques, alors il existe un
entier x qui satisfait simultanément les congruences : x
≡ a
1
(mod m
1
), x
≡ a
2
(mod m
2
), …, x
≡ a
r
(mod m
r
). De plus, si x = a est une solution quelconque,
alors toutes les autres solutions sont congruentes à un modulo égal au produit
m
1
⋅m
2
⋅ … m
r
.
Fonction EGCD
EGCD signifie Extended Greatest Common Divisor (Plus grand diviseur
commun étendu). Etant donné deux polynômes, A(X) et B(X), la fonction EGCD
produit les polynômes C(X), U(X), et V(X), de telle sorte que C(X) = U(X)*A(X)