Kongruenzen lösen

20.01.2012, 21:06

Olaftrofal

Kongruenzen lösen

Meine Frage:
Hi ich komm bei 2 Aufgaben nicht weiter:
$\begin{eqnarray*} 5x\equiv 2 mod \; 3 4x\equiv 7 mod \; 9 2x \equiv 4 mod \; 10 \end{eqnarray*}$

und
$\begin{eqnarray*} x\equiv 1 mod \; 2 x\equiv 2 mod \; 3 x\equiv 5 mod \; 6 x\equiv 5 mod \; 12 \end{eqnarray*}$

Meine Ideen:
zur ersten aufgabe keine Ahnung. Hab versucht iwie [latex]5x\equiv 1 mod \; m [latex] dastehen zu haben damit ich iwie weiter komme... aber mir fällt nichts ein.

Zur zweiten weiß ich das man, zusammenfassen kann. weil die haben alle ein kgV., weiß dann aber auch nicht wie ich weiter machen könnte. Habs mit 5 mod 24 versucht...

21.01.2012, 11:51

Olaftrofal

Auf diesen Beitrag antworten »

Niemand da, der mir kurzen helfen könnte, paar Hinweise oder so^^

21.01.2012, 13:26

Olaftrofal

Auf diesen Beitrag antworten »

Wenn der Thread schon offen ist hab ich gleich noch ne Frage^^

Es geht um den Fermatschen Primzahltest

$\begin{eqnarray*} 2^{3572} \equiv 256 \neq 1 mod 3573 \end{eqnarray*}$

Ich versteh nicht wie man auf die 256 kommt. Ich hab versucht die 2 hoch 3572 zu vereinfachen mit square und multiply und sonstnoch was... das haut alles nicht in einer entsprechenden zeit hin.
Man kanns mit 4x 893 zerlegen und die 3573 mit 3x1191...

Vllt könnt ihr mir auch hier bisschen helfen

21.01.2012, 14:24

galoisseinbruder

Auf diesen Beitrag antworten »

Hallo,

die Äquivalenzklassen mod n haben standardmäßig die Representanten $\begin{eqnarray*} 0,1, \ldots , n-1 \end{eqnarray*}$ also $\begin{eqnarray*} 5\equiv ? \mod 3 \end{eqnarray*}$ .
Ansonsten: Wie invertiert man Zahlen in Restklassenringen? (steht bestimmt im Skript)

Zitat:

Zur zweiten weiß ich das man, zusammenfassen kann. weil die haben alle ein kgV., weiß dann aber auch nicht wie ich weiter machen könnte. Habs mit 5 mod 24 versucht.

Ist das geraten? Oder hast du ein Verfahren zur Lösung simultaner Kongruenzen verwendet?

Und zum letzten Post:
Mit der Carmichael-Funktion ist die Rechnung ganz kurz, die kennst du aber mit sehr hoher W-keit nicht. Mit Satz von Euler wird´s auch kürzer.
Ansonsten: Square-and Multiply, dauert etwas (Integrale rechnet man auch nicht immer in 5 Sekunden aus) .
Ach ja: Faktorzerlegungen sollte man wenn schon dann ganz machen.

21.01.2012, 15:27

Olaftrofal

Auf diesen Beitrag antworten »

Representanten wären 1 und 2.
Das Inverse -1. Bekommt man über den erweiterten euklidischen alghoritmus.
Versteh dennoch nicht wie man diese simultane kongruenz löst.

Ich werd den chin. Restsatz gebrauchen. Den entwickle ich immer mit der Newton methode.

Zu meinen letzen Post. Ich habs mit Euler versucht. Bekomms einfach nicht kürzer.
Square und multiply dauert einfach zu lang. Würde so in der klausur nicht dran kommen.

Ich könnte die beiden noch soweit zerlegen:
2x2x893 und 3x3x397 so. Phi von 3 = 2. Dann hab ich noch ein bisschen rumgespielt aber kam nicht brauchbares dabei raus.

Danke schon mal für die bisherige Hilfe

21.01.2012, 15:35

galoisseinbruder

Auf diesen Beitrag antworten »

Zitat:

Representanten wären 1 und 2.

$\begin{eqnarray*} 5 \equiv 1 \equiv 2\mod 3 \end{eqnarray*}$ ?

Zitat:

Bekommt man über den erweiterten euklidischen alghoritmus. (sic.)

Dann los.

Zitat:

Versteh dennoch nicht wie man diese simultane kongruenz löst.

Wenn du versteht wie man zwei simultane kongruenzen löst, dann nimm dir die ersten zwei und die letzten zwei gleichungen vor und dann nochmal die entstaehenden zwei gleichungen.

Zitat:

Ich habs mit Euler versucht. Bekomms einfach nicht kürzer.

Einfache Frage. Was ist $\begin{eqnarray*} \varphi (3573) \end{eqnarray*}$ ?

Und ich finde die letzte Aufgabe als Rechenaufgabe in einer Klausur nicht so abwegig.

21.01.2012, 17:31

Olaftrofal

Auf diesen Beitrag antworten »

Zur ersten Aufgabe

$\begin{eqnarray*} x\equiv 1 mod 3 x\equiv 1 mod 3 x\equiv 2 mod 5 \end{eqnarray*}$

$\begin{eqnarray*} x\equiv 7 mod 15 \end{eqnarray*}$ kam dabei raus. In den Lösugen steht aber $\begin{eqnarray*} x\equiv 22mod 45 \end{eqnarray*}$

$\begin{eqnarray*} \phi(3573) \end{eqnarray*}$ keine Ahnung, wenns ne primzahl ist 3572

21.01.2012, 18:19

galoisseinbruder

Auf diesen Beitrag antworten »

Zitat:

Zur ersten Aufgabe $\begin{eqnarray*} x\equiv 1 mod 3 x\equiv 1 mod 3 x\equiv 2 mod 5 \end{eqnarray*}$ $\begin{eqnarray*} x\equiv 7 mod 15 \end{eqnarray*}$ kam dabei raus. In den Lösugen steht aber $\begin{eqnarray*} x\equiv 22mod 45 \end{eqnarray*}$

Die zweite lösung ist falsch. Wie wird aus dem mod 9 ein mod 3?

Zitat:

$\begin{eqnarray*} \phi(3573) \end{eqnarray*}$ keine Ahnung, wenns ne primzahl ist 3572

Klick mich

21.01.2012, 18:47

Olaftrofal

Auf diesen Beitrag antworten »

Aus mod 9 wird mod 3 weil ich die 9 mit dem china restsatz zerleg.

21.01.2012, 19:39

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von galoisseinbruder
Einfache Frage. Was ist $\begin{eqnarray*} \varphi (3573) \end{eqnarray*}$ ?

Noch passender wäre hier allerdings die Carmichael-Funktion, also $\begin{eqnarray*} \lambda(3573) \end{eqnarray*}$ - das bringt gleich die für die Berechnung passende Reduktion des Exponenten.

EDIT: Entschuldigung, ich hätte den ganzen Thread lesen sollen, die Carmichael-Funktion hattest du ja hier schon erwähnt. Hammer

Neue Frage »

Antworten »

Kongruenzen lösen

Verwandte Themen