Kongruenz lösen

04.10.2011, 13:56

Steffen2361

Auf diesen Beitrag antworten »

Kongruenz lösen

Meine Frage:
Hi, ich soll alle Lösungen der folgende Kongruenz finden:

$\begin{eqnarray*} 33x \equiv 72 (114) \end{eqnarray*}$

Meine Ideen:
Also zuerst ahbe ich den ggt(33,114)= 3 berechnet und da 3|72 ist die Kongruenz lösbar. Demnach hat die Kongruenz auch 3 Löungen.

Dannach habe ich die Gleichung durch 3 "geteilt".

$\begin{eqnarray*} 33x \equiv 72 (114) \end{eqnarray*}$
$\begin{eqnarray*} 11x \equiv 24 (38) \end{eqnarray*}$
Nun auf der rechten Seite erweitert mit 24 + 4*38:
$\begin{eqnarray*} 11x \equiv 176 (38) \end{eqnarray*}$
Daraus folgt:
$\begin{eqnarray*} x \equiv 16 (38) \end{eqnarray*}$

das heißt die 3 Lösungen sind
$\begin{eqnarray*} x \equiv 16 (114) \end{eqnarray*}$
$\begin{eqnarray*} x \equiv 16+38 (114) \Rightarrow x \equiv 54 (114) \end{eqnarray*}$
$\begin{eqnarray*} x \equiv 16 +76 (114) \Rightarrow x \equiv 92 (114) \end{eqnarray*}$

Ist das so richtig??

mfg
Danke für alles

04.10.2011, 13:59

René Gruber

Auf diesen Beitrag antworten »

RE: Kongurenz lösen
Alles vollkommen richtig, und auch sauber begründet. Freude

Freude

04.10.2011, 14:12

Steffen2361

Auf diesen Beitrag antworten »

RE: Kongurenz lösen
Wunderbar...

dann komme ich jetzt zu einem Beispiel, dass ich überhaupt nicht verstehe. Soll ich dafür einen neuen Thread aufmachen?

mfg

04.10.2011, 14:26

René Gruber

Auf diesen Beitrag antworten »

Normalerweise ja, aber wenn es wieder eine Kongruenz ist, dann poste sie ruhig hier. Es ist ja deutlich erkennbar, dass die erste Aufgabe jetzt hier abgehakt ist (Chaos gibt es nur, wenn verschachtelt mehrere offene Probleme in einem Thread behandelt werden).

04.10.2011, 14:33

Steffen2361

Auf diesen Beitrag antworten »

Danke dir

smile

Ich soll zeigen, dass für alle ungerade Primzahlen gilt:
$\begin{eqnarray*} p \in P \end{eqnarray*}$ (rimzahlen)

$\begin{eqnarray*} (2p-2)*(2p-4)*....*4*2 \equiv -1(mod p) \end{eqnarray*}$
----------------------------------------------------------------------------

Also ich schätze mal ich soll mit dem "Satz von Wilson" arbeiten. Dieser gibt mir an ob eine Zahl eine Primzahl ist oder eben eine zusammengestzte Zahl.

Satz von Wilson : $\begin{eqnarray*} (p-1)!\equiv-1 (mod p) \end{eqnarray*}$

Einen weiteren Ansatz habe ich bis jetzt noch nicht.... verwirrt

verwirrt

04.10.2011, 14:39

René Gruber

Auf diesen Beitrag antworten »

Eigentlich musst du ja nur aus jedem der $\begin{eqnarray*} (p-1) \end{eqnarray*}$ Faktoren den Faktor 2 herauslösen:

$\begin{eqnarray*} (2p-2)\cdot (2p-4) \cdot \ldots \cdot 4 \cdot 2 = (2(p-1))\cdot (2(p-2)) \cdot \ldots \cdot (2\cdot 2) \cdot (2\cdot 1) = 2^{p-1}\cdot (p-1)! \end{eqnarray*}$

Dann Wilson sowie ... ja, was? Augenzwinkern

Augenzwinkern

Anzeige

04.10.2011, 15:00

Steffen2361

Auf diesen Beitrag antworten »

Zitat:

Dann Wilson sowie ... ja, was? Augenzwinkern

Augenzwinkern

Mit dieser Aussage komm ich nicht ganz mit.

Aber das mit dem herauslösen war ein echt guter Tipp smile

smile

Könnte man dann weiterrechnen mit

$\begin{eqnarray*} 2^{p-1}\cdot (p-1)! \equiv -1 (p) \end{eqnarray*}$

Da dann $\begin{eqnarray*} 2^{p-1}\cdot \end{eqnarray*}$ ein vielfaches vom modul $\begin{eqnarray*} (mod p) \end{eqnarray*}$ ist, weglassen und die Kongruenz würde lauten.

$\begin{eqnarray*} (p-1)! \equiv -1 (p) \end{eqnarray*}$

Dies würde nun dem Satz von Wilson entsprechen, ich das hilft mir aber nicht weiter oder??
Bzw. habe ich sicher einige grundlegenden Fehler bezüglich rechnen mit Kongruenzen begangen

mfg

04.10.2011, 15:02

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von Steffen2361
Da dann $\begin{eqnarray*} 2^{p-1}\cdot \end{eqnarray*}$ ein vielfaches vom modul $\begin{eqnarray*} (mod p) \end{eqnarray*}$ ist

Wie bitte?

04.10.2011, 15:05

Steffen2361

Auf diesen Beitrag antworten »

haha...dachte ich mir schon, dass das nicht stimmen kann

04.10.2011, 15:11

Steffen2361

Auf diesen Beitrag antworten »

Nun gut nachdem Sie es mir schön aufgelöst haben folgt

$\begin{eqnarray*} 2^{p-1}\cdot (p-1)! \equiv -1 (mod p) \end{eqnarray*}$

Aber was mache ich jetzt daraus..... verwirrt

verwirrt

04.10.2011, 15:15

René Gruber

Auf diesen Beitrag antworten »

Ich weiß gar nicht, warum du immer wieder die Behauptung wiederholst. Wo sind wir bisher:

1) Dein Produkt enspricht $\begin{eqnarray*} 2^{p-1}\cdot (p-1)! \end{eqnarray*}$

2) Laut Wilson gilt $\begin{eqnarray*} (p-1)! \equiv -1\bmod p \end{eqnarray*}$ .

3) Damit die Behauptung gilt, muss also irgendwie noch $\begin{eqnarray*} 2^{p-1}\equiv 1\bmod p \end{eqnarray*}$ begründet werden.

Tja, und bei diesem "irgendwie" dachte ich, dass dir die Struktur $\begin{eqnarray*} a^{p-1} \bmod p \end{eqnarray*}$ doch eigentlich bekannt sein müsste.

04.10.2011, 15:38

Steffen2361

Auf diesen Beitrag antworten »

hehe...wenn ich Sie richtig verstanden habe wollen sie auf den kleinen Fermatschen Satz hinaus smile

smile

hoffe ich zumindest .....

$\begin{eqnarray*} a^{p-1} \equiv \bmod p \end{eqnarray*}$ (soll ich ihn noch mit der eulerschen phi Funktion erweitern?)

Ich seh aber noch immer keinen Zusammenhang wie ich die Angabe zeigen soll... verwirrt

verwirrt

04.10.2011, 15:47

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von Steffen2361
hehe...wenn ich Sie richtig verstanden habe wollen sie auf den kleinen Fermatschen Satz hinaus

Ja, wollte ich (übrigens duzen wir uns hier).

Und eigentlich ist jetzt alles gezeigt, weshalb ich ein wenig verwundert darüber bin, dass dir das anscheinend nicht bewusst ist. Augenzwinkern

Augenzwinkern

Oder gehören Wilson & Fermat nicht zu den bekannten Aussagen, die du im Beweis deiner Aussage verwenden darfst? verwirrt

verwirrt

04.10.2011, 15:58

Steffen2361

Auf diesen Beitrag antworten »

Mein Gott, Ich muss den "Wald vor lauter Bäume nicht sehen"

Also wenn ich das mal zusammenfasse:

Zuerst wurde die Gleichung ungeformt zu:
$\begin{eqnarray*} 2^{p-1}\cdot (p-1)! \equiv -1\bmod p \end{eqnarray*}$

Dadurch gilt laut Wilson:
$\begin{eqnarray*} (p-1)! \equiv -1\bmod p \end{eqnarray*}$

Und es bleibt noch das $\begin{eqnarray*} 2^{p-1} \end{eqnarray*}$ übrig.

Dies wird mit dem kleinen fermatschen Satz gezeigt.

$\begin{eqnarray*} a^{p-1} \equiv 1 (mod p) \end{eqnarray*}$ für a =2

Habe ich das richtig verstanden??

mfg
PS: Dann war das herausheben ja das schwierigste an der ganzen sache... smile

smile

04.10.2011, 16:17

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von Steffen2361
Zuerst wurde die Gleichung ungeformt zu:
$\begin{eqnarray*} 2^{p-1}\cdot (p-1)! \equiv -1\bmod p \end{eqnarray*}$

Dadurch gilt laut Wilson:
$\begin{eqnarray*} (p-1)! \equiv -1\bmod p \end{eqnarray*}$

Und es bleibt noch das $\begin{eqnarray*} 2^{p-1} \end{eqnarray*}$ übrig.

Dies wird mit dem kleinen fermatschen Satz gezeigt.

Deine logische Anordnung der Gedanken finde ich äußerst befremdlich, vor allem dieses "dadurch". Ich wiederhole nochmal meinen Beweisablauf von oben, nunmehr vervollständigt:

Zitat:

1) Dein Produkt enspricht $\begin{eqnarray*} 2^{p-1}\cdot (p-1)! \end{eqnarray*}$

2) Laut Wilson gilt $\begin{eqnarray*} (p-1)! \equiv -1\bmod p \end{eqnarray*}$ .

3) Laut kleinem Fermat gilt $\begin{eqnarray*} 2^{p-1}\equiv 1\bmod p \end{eqnarray*}$ .

2) und 3) multipliziert ergibt die Behauptung.

So gehört das ganze m.E. hin, vom Kopf auf die Füße. Bei deinen Ausführungen weiß man immer nicht "was ist nun noch offene Behauptung, was ist gesicherte Aussage".

04.10.2011, 16:19

Steffen2361

Auf diesen Beitrag antworten »

Ach soooooooooo jetzt hat es klick gemacht.....das multiplizieren an dem bin ich gehangen.....

Danke dir vielmals smile

smile

mfg

04.10.2011, 16:22

René Gruber

Auf diesen Beitrag antworten »

Ach DAS war das Problem? Darauf wäre ich nie gekommen, dass jemand bei der Struktur $\begin{eqnarray*} 2^{p-1} \cdot (p-1)! \end{eqnarray*}$ NICHT darauf kommt, die beiden Teilergebnisse miteinander zu multiplizieren... Big Laugh

Big Laugh

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »