Diskrete Mathe (Modulare Arithmetik)

Wissenschaft Physik
1

Hi @ all!

ich bereite mich jetzt zu der Prüfung in diskrete Mathe und suche nach einer Tabelle von modularen Inversen (für Ringe Z 1 bis Z 50)

Z7|
__|Element_| Inverses_
1 1
2 4
3 5
4 2
5 3
6 6

(in der Klausur darf man alles außer Taschenrechner benutzen)

weiss jemand, wo ich so etwas finde?

Danke im Voraus
Andre

2

Hallo,
das multiplikative Inverse der primen Restklassengruppe kann man mit dem erweiterten euklidischen Algorithmus bestimmen. Der liefert für zwei Zahlen a und n eine Darstellung von ggT(a,n) als ra+sn. Im Falle ggT(a,n)=1 ist damit r das multiplikative Inverse von a modulo n.

Gruss
Enno

3

Nachtrag
Hallo,
ist das n sehr groß und muß man für mehrere Werte (modulo n) das multiplikative Inverse berechnen, bietet sich zudem der chin. Restsatz an. Ist n=∏1 ti eine Zerlegung von n in paarweise teilerfremde ti (z.B. die eindeutige Primfaktorzerlegung), kann man mittels dieses Satzes die Inversenbestimmung in den einzelnen ti absolvieren. Für z.B. n=273=3713 würde man 32-1 bestimmen, indem man zunächst

2-1 mod 3=2 (Anm: 32 mod 3=2)
4-1 mod 7=2 (Anm: 32 mod 7=4)
6-1 mod 13=11 (Anm: 32 mod 13=6)

bestimmen und dann ein x mit x mod 3=2, x mod 7=2 und x mod 13=11 suchen. Dazu bestimmt man:

(273/3)-1 mod 3=1-1 mod 3=1
(273/7)-1 mod 7=4-1 mod 7=2
(273/13)-1 mod 13=8-1 mod 13=5

und bildet

(2-1 mod 3)273/3((273/3)-1 mod 3) +
(4-1 mod 7)+273/7*((273/7)-1 mod 7) +
(6-1 mod 13)+273/13*((273/13)-1 mod 13) mod 273=
2911+2392+11215 mod 273=128

Damit gilt 32-1 mod 273=128

Gruss
Enno

4

Moin,

der Chinesische Restsatz ist wirklich gut, aber in der Klausur hat man keine Zeit um die Inversen auszurechnen.:frowning:(

ich würde gern eine Excel Tabelle erstellen, aber weiß nicht wie es schnell geht

_____„Das Inverse von Element“

Z___01__02__03__04__05__06__07…50
02__01
03__01__02
04__01______03
05__01__03__02__04
.
.
.
50__01______17______________43

Kann man in Excel Schleifen programmieren?

Danke im Voraus

5

Hallo,
habe ich beim zweiten lesen auch so gesehen. Mail ist ja schon angekommen. Ob’s mit Excel gehen würde - „vermutlich“ aber ich meide weitgehenst MS-Software *g*.

Gruss
Enno