Lineare Kongruenz Beweis

06.11.2013, 22:41

math38

Lineare Kongruenz Beweis

Meine Frage:
Könntet Ihr mir bitte helfen?

Aufgabe: "Show that when $\begin{eqnarray*} m \end{eqnarray*}$ is prime and $\begin{eqnarray*} a \neq 0 \end{eqnarray*}$ , there exists a unique Solution to the equation $\begin{eqnarray*} ax+b=0 \end{eqnarray*}$ for the integers modulo $\begin{eqnarray*} m \end{eqnarray*}$ ."

Auf Deutsch:"Zeige, wenn $\begin{eqnarray*} m \end{eqnarray*}$ eine Primzahl ist und $\begin{eqnarray*} a \neq 0 \end{eqnarray*}$ , dann existiert genau eine Lösung für die Gleichung: $\begin{eqnarray*} ax+b=0 \end{eqnarray*}$ für die ganze Zahl modulo $\begin{eqnarray*} m \end{eqnarray*}$ "

Meine Ideen:
Ich hätte die Gleichung: $\begin{eqnarray*} ax+b=0 \end{eqnarray*}$ umgestellt. Damit erhalte ich, wenn ich b mit der additive Inverse von b auf beiden Seiten addiere und danach mit der multiplikativen Inverse von a auf beiden Seiten multipliziere, die folgende Gleichung $\begin{eqnarray*} x= (-b) \times a^{-1} \end{eqnarray*}$ . Stimmt das? Wenn ja, wie muss ich dann weitermachen?

06.11.2013, 22:55

Captain Kirk

Auf diesen Beitrag antworten »

Hallo,

die Lösung ist richtig.
Die Frage ist nur: Wieso darfst du so umformen und warum ist damit die Lösung eindeutig?

06.11.2013, 23:06

math38

Auf diesen Beitrag antworten »

Wieso darf ich es umformen? Hmm… ich denke da diese Eigenschaft (Inverses Element) bei der Multiplikation und Addition bei Modulo Rechnen auch gilt. Also in den Restklassen. Wieso das Eindeutig ist, weiß ich nicht -.-

06.11.2013, 23:17

Captain Kirk

Auf diesen Beitrag antworten »

Zitat:

ich denke da diese Eigenschaft (Inverses Element) Multiplikation und Addition bei Modulo Rechnen auch gilt. Also in den Restklassen

Bei einem Beweis muss man sich sicher sein und das auch formulieren können.

Multiplikative Inverse existieren und sind eindeutig bestimmt in diesem Fall aufgrund einer speziellen Eigenschaft von m.

z.B. ist $\begin{eqnarray*} 2x+1 \equiv 0 \mod 4 \end{eqnarray*}$ überhaupt nicht lösbar und
$\begin{eqnarray*} 2x \equiv 0 \mod 4 \end{eqnarray*}$ hat zwei Lösungen.

06.11.2013, 23:26

math38

Auf diesen Beitrag antworten »

m ist eine Primzahl --> ggT(a,m)=1 , a und m sind teilerfremd ?

06.11.2013, 23:30

Captain Kirk

Auf diesen Beitrag antworten »

Der Gedanke ist richtig.

06.11.2013, 23:42

math38

Auf diesen Beitrag antworten »

Also dann heisst die komplette Aufgabe so

Wir formen zunächst die Gleichung nach x um und erhalten

$\begin{eqnarray*} x= (-b) \times a^{-1} \end{eqnarray*}$

Das können wir tun, da in den Restklassen Inverses Element für die Addition und Multiplikation existiert.

Da m eine Primzahl ist, sind a und m teilerfrem. Also gilt

$\begin{eqnarray*} ggT(a,m)=1 \end{eqnarray*}$

Da $\begin{eqnarray*} ggT(a,m)=1 \end{eqnarray*}$ ist, ist die Lösung $\begin{eqnarray*} x= (-b) \times a^{-1} \end{eqnarray*}$ eindeutig.

Ist das mathematisch Korrekt aufgeschrieben?

07.11.2013, 00:12

Captain Kirk

Auf diesen Beitrag antworten »

Zitat:

Ist das mathematisch Korrekt aufgeschrieben?

Nein.

Da p prim ist (bzw. weil ggt(a,m)=1) existiert $\begin{eqnarray*} a^{-1} \end{eqnarray*}$ hier überhaupt erst.
[Wie gesagt, sonst existiert das a nicht]
Und gleichzeitig ist es auch noch eindeutig.

P.S. Benutze \cdot . \times ist Kreuzprodukt u.ä.

07.11.2013, 00:16

math38

Auf diesen Beitrag antworten »

ahh ok vielen dank, aber das mit der Eindeutigkeit habe ich nicht wirklich so verstanden. Kann mann das einfach so sagen? Weil m prim ist, existiert die Inverse und deshalb ist es auch eindeutig?

07.11.2013, 00:19

Captain Kirk

Auf diesen Beitrag antworten »

Für primes p ist $\begin{eqnarray*} ((\mathbb Z/p\mathbb Z)^*,\cdot ) \end{eqnarray*}$ eine Gruppe, bzw $\begin{eqnarray*} \mathbb Z/p\mathbb Z \end{eqnarray*}$ ein Körper. (das dürftet ihr schon bewiesen haben)

05.12.2013, 13:50

math38

Auf diesen Beitrag antworten »

http://s1.directupload.net/images/131205/qrsl9rub.png

Also ich bin soweit gekommen (siehe Bild). Ich muss nur noch begründen können, wieso die additive Inverse für b und die multiplikative Inverse für a Eindeutig ist. Und es muss eine Vorbedingung gelten, dass a<m ist, oder ? Könnte mir vielleicht jmd. sagen, ob es danach in Ordnung ist? Für jede Hilfe bin ich Dankbar.

08.12.2013, 14:03

math38

Auf diesen Beitrag antworten »

Könnte ich bitte eine Antwort bekommen...

08.12.2013, 14:37

Captain Kirk

Auf diesen Beitrag antworten »

Du hast für dein Bildchen bereits einen neuen Thread erstellt und dort auch eine ANtwort bekommen:
matheboard.de/thread.php?threadid=532823

Wieso sollte also hier nochmals jemand zusätzlich antworten?

Und ich fänds auch ganz nett eine Antwort in unter 4 Wochen zu kriegen, aber wie man bei dir sieht wird einem nicht jeder Wunsch erfüllt. Vielleicht dann an Weihnachten.

Neue Frage »

Antworten »

Lineare Kongruenz Beweis

Verwandte Themen