Modulare Inverse

17.01.2015, 15:30	Lena95	Auf diesen Beitrag antworten »
Modulare Inverse Hey Ich habe mal wieder eine Aufgabe. Diesmal geht es um die modulare Inverse. Aufgabe lautet: Es sei n $\begin{eqnarray} n \in \mathbb N, n\geq 2 \end{eqnarray}$ . Die Zahlen $\begin{eqnarray} a \in \mathbb Z \end{eqnarray}$ und $\begin{eqnarray} n \end{eqnarray}$ seien teilerfremd. Zeigen Sie: (4 P.) i) Es existiert ein $\begin{eqnarray} a \in \mathbb Z \end{eqnarray}$ mit $\begin{eqnarray} xa\equiv 1 (mod\, n) \end{eqnarray}$ . Hinweis: Ein solches x heißt eine Inverse modulo n von a. ii) Mit $\begin{eqnarray} x \end{eqnarray}$ ist auch $\begin{eqnarray} x+kn , k \in \mathbb Z \end{eqnarray}$ eine Inverse modulo n von a, d.h. es gibt unendlich viele Inverse modulo n von a. iii) Die Bedingung der Teilerfremdheit von a und n für die Existenz einer Inversen modulo n von a ist notwendig, d.h. für ein b € Z mit ggT(b, n) > 1 gilt xb =/= 1 (mod n) für alle x € Z. Die erste Aufgabe sollte ja über das Lemma von Bezout gehen. Also a,n sind teilerfremd. Also ggt(a,n)=1. Also $\begin{eqnarray} s\cdot n+t \cdot b=1. \end{eqnarray}$ Jetzt bin ich mir nicht sicher, wie ich den Sprung auf die modulare Arithmetik mache. Also: $\begin{eqnarray} s\cdot a+t \cdot b=1. \end{eqnarray}$ => $\begin{eqnarray} s \cdot a\equiv 1 (mod\, n) \end{eqnarray}$ Weil, das tn mod n ja 0 ist. Jetzt weiß ich nicht ob man das einfach so schreiben darf, oder wie man diesen Schritt von = auf das modulare = macht. Zu b) Hab keine wirkliche Idee. Ich meine in der Vorlesung gehört zu haben, dass man, wenn man "mod n" rechnet, beliebig oft "mod n" praktisch rechnen darf auf beiden Seiten. Dann wäre ja sowas möglich: $\begin{eqnarray} (a+kn)x \equiv 1 (mod \, n)\\<br /> (a+(kn))x \equiv 1(mod \, n)\\<br /> (a+(kn\, (mod\, n)))x\equiv 1(mod \, n)\\<br /> (a+0)x\equiv 1 (mod \, n)\\<br /> ax\equiv 1 (mod \, n)<br /> \end{eqnarray*}$ Nur nicht sicher, ob das so möglich ist, bzw falls ja, ob das dann schon genug ist. Bei c) habe ich leider keine wirkliche Idee. Vllt auch wieder über das Lemma von Bezout.Vllt kann mir da einer einen Tipp geben. Grüße und Danke schonmal
19.01.2015, 13:16	Elvis	Auf diesen Beitrag antworten »
(i) Am Anfang geht bei dir a,b,n,x wüst durcheinander. Außerdem fehlen Quantoren ("es existiert"). Das musst du etwas sorgfältiger machen, dann stimmt es. (ii) So geht das nicht. Eine beliebige Sammlung von Kongruenzen ist kein Beweis. Der Beweis besteht aus einer Voraussetzung $\begin{eqnarray} xa\equiv 1(n) \end{eqnarray}$ , ein paar logischen Folgerungen $\begin{eqnarray} ...\Rightarrow ... \end{eqnarray}$ und dem Schluß $\begin{eqnarray} x+kn\equiv 1(n) \end{eqnarray}$ für alle $\begin{eqnarray} k\in\mathbb Z \end{eqnarray}$ . (iii) Das Lemma von Bezout ist ein guter Startpunkt. Vermutlich enthält es eine hierfür nützliche Äquivalenzaussage.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »