Home |
Logithèque |
HP42S
Calcule l'inverse d'un nombre modulo un autre.
Code
Le programme appelle le sous-programme "BEZOUT" qui doit donc aussi être présent.
LBL "MOD-1"
STO 03
X<>Y
XEQ "BEZOUT"
RDN
X>=0?
GTO 01
RCL 03
+
LBL 01
CLA
ARCL 02
+"x"
AIP
+"="
ARCL ST Y
+"["
ARCL 03
+"]"
AVIEW
END
Le sous-programme est :
LBL "BEZOUT"
1
STO "A"
+/-
SQRT
STO "B"
LBL 01
RDN
STO 01
X<>Y
ENTER
ENTER
RCL ST T
/
IP
STO 00
RCL ST Z
*
-
RCL "B"
RCL 00
*
RCL "A"
X<>Y
-
X<>"B"
X<>"A"
RDN
1
X<=Y?
GTO 01
RCL 01
RCL "A"
COMPLEX
CLV "A"
CLV "B"
END
Tailles : 51 octets et 69 octets.
La convention +"..." a été utilisée pour représenter la continuation de chaîne alphanumérique.
Mode d'emploi
Entrer la valeur X et le modulo M sur la pile dans cet ordre.
Exécuter le programme. Il détermine l'inverse module M de l'entier X.
S'affiche les valeurs numériques satisfaisant l'équation X*U=P [M] où P est le pgcd de X et M. U est donc l'inverse de X modulo M, mais ce n'est réellement le cas que quand X et M sont premiers entre eux, car alors P vaut bien 1.
Mathématiques à l'oeuvre
On commence par résoudre l'équation de Bezout :
X*U+M*V=P
où P est le pgcd de X et M, en utilisant le même algorithme que celui de la recherche du PGCD.
Ensuite il vient naturellement que X*U=P [M]
On utilise dans le programme "BEZOUT" des nombres complexes afin de conserver les couples (Ui, Vi) sous la forme Ui+i*Vi. Cette technique permet de limiter le nombre de variables.