Zahlentheorie. Kongruenz

13.11.2006, 21:11

piloan

Zahlentheorie. Kongruenz

hi jungs und maeddls... :-)

ich habe mal eine frage und hoffe, dass mir einer bei der vorgehensweise helfen kann ...

ich soll folgendes bestimmen $\begin{eqnarray*} 5x \equiv 2 (mod 3) \end{eqnarray*}$

nun ich brauch nun alle y fuer die gilt :

5x-2=3y nun hab ich gelesen, dass man die gleichung mit dem euklidischen algorithmus loesen kann .... nun braeucht ich mal die hilfe wie das funktioniert.
oder ob es bessere/andere moeglichkeiten gibt...
gruß und danke

13.11.2006, 21:22

Abakus

Auf diesen Beitrag antworten »

RE: Zahlentheorie. Kongruenz
Deine Gleichung wirst du einfach nach x umstellen können, dann hast du die gewünschten Lösungen.

Für den Euklidischen Algorithmus siehe hier.

Grüße Abakus smile

13.11.2006, 21:27

piloan

Auf diesen Beitrag antworten »

hi abakus

die gleichung nach x umstellen kann ich noch Augenzwinkern

...und den euklidischen alg. kann ich eigentlich auch ...
dann hab ich

$\begin{eqnarray*} x=(3y+2)/5 \end{eqnarray*}$

nur wie schreib ich jetzt meine loesungen auf ...das ist das problem...das sind ja nun mal unendlich viele loesungen ...wie stell ich das dar ?...das sind eher meine probleme und beim algori. ist es die frage wovon ich da den teiler bestimme...
gruß

13.11.2006, 21:34

Abakus

Auf diesen Beitrag antworten »

Wie gefällt dir folgende Notation ?

$\begin{eqnarray*} L = \{x : x = \frac{3k+2}{5},~ k \in \mathbb Z\} \end{eqnarray*}$

Grüße Abakus smile

EDIT: Latex

13.11.2006, 21:59

piloan

Auf diesen Beitrag antworten »

hmhm
wenn du meinst ....es scheint mir nur ein wenig leicht da das niveau unserer zettel eigentlich recht hoch ist und die ganze aufgabe aus aehnlichen kongruenzen zusammengestellt ist...
gruß

13.11.2006, 22:01

Auf diesen Beitrag antworten »

Zitat:

Original von piloan
nun ich brauch nun alle y fuer die gilt :

5x-2=3y nun hab ich gelesen, dass man die gleichung mit dem euklidischen algorithmus loesen kann ....

Genauer gesagt: Mit dem erweiterten euklidischen Algorithmus, der liefert nämlich ganze Zahlen $\begin{eqnarray*} a,b \end{eqnarray*}$ mit

$\begin{eqnarray*} 5a+3b = \operatorname{ggT}(5,3) \end{eqnarray*}$ , wobei ja $\begin{eqnarray*} \operatorname{ggT}(5,3) = 1 \end{eqnarray*}$ .

Hier wären das $\begin{eqnarray*} a=2,b=-3 \end{eqnarray*}$ , d.h. a=2 ist das inverse Element von 5 modulo 3. Damit ist die Lösung von $\begin{eqnarray*} 5x\equiv 2\mod 3 \end{eqnarray*}$ gleich

$\begin{eqnarray*} x \equiv 2\cdot 5^{-1} \equiv 2\cdot 2 \equiv 1\mod 3 \end{eqnarray*}$ .

14.11.2006, 00:36

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von piloan
wenn du meinst ....es scheint mir nur ein wenig leicht da das niveau unserer zettel eigentlich recht hoch ist und die ganze aufgabe aus aehnlichen kongruenzen zusammengestellt ist...

Wenn du alle ganzen Zahlen y suchst, macht der Euklidische Algorithmus hier Sinn. Das habe ich aus deiner Frage aber nicht heraus gelesen.

Grüße Abakus smile

14.11.2006, 08:31

Auf diesen Beitrag antworten »

@Abakus

Das geht doch aus

Zitat:

Original von piloan
ich soll folgendes bestimmen $\begin{eqnarray*} 5x \equiv 2 (mod 3) \end{eqnarray*}$

hervor. Und das war ja wohl die ursprüngliche Aufgabe... Augenzwinkern

14.11.2006, 13:03

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Das geht doch aus

Zitat:

Original von piloan
ich soll folgendes bestimmen $\begin{eqnarray*} 5x \equiv 2 (mod 3) \end{eqnarray*}$

hervor. Und das war ja wohl die ursprüngliche Aufgabe... Augenzwinkern

Damit ist $\begin{eqnarray*} 5x \in \mathbb Z \end{eqnarray*}$ , für die eigentlich reelle Variable $\begin{eqnarray*} x \end{eqnarray*}$ folgt das nicht. Dass der Sinn der Aufgabe ein anderer war, hab ich nun gesehen, ok Augenzwinkern

.

Grüße Abakus smile

14.11.2006, 13:40

piloan

Auf diesen Beitrag antworten »

habs nun auch verstanden und bedanke mich bei euch beiden...

nun hab ich noch ein problem bei einer induktion ( auch zahlentheorie, deswegen lass ich das mal in diesem Thema)

ich soll per induktion beweisen,dass

$\begin{eqnarray*} {\phi^{n-2}<F_{n}<\phi^{n-1}} \end{eqnarray*}$ wobei

$\begin{eqnarray*} \phi =\frac{1+\sqrt{5}}{2} \end{eqnarray*}$ und $\begin{eqnarray*} F_{n} \end{eqnarray*}$ die Fibonacci Folge.

Nun habe ich den Induktionsanfang und mache nun den Induktionsschritt..

$\begin{eqnarray*} {\phi^{n-1}=\phi^{n-2}\phi < F_{n}}\phi \end{eqnarray*}$ aber wie komme ich jetzt damit auf $\begin{eqnarray*} F_{n+1} \end{eqnarray*}$ ...

habe $\begin{eqnarray*} \phi \end{eqnarray*}$ schon abgeschaetzt, so dass $\begin{eqnarray*} 2F_{n} \end{eqnarray*}$ da steht, dies ist jedoch größer als das gebrauchte...
danke

14.11.2006, 13:53

Auf diesen Beitrag antworten »

Zitat:

Original von piloan
ich soll per induktion beweisen,dass

$\begin{eqnarray*} {\phi^{n-2}<F_{n}<\phi^{n-1}} \end{eqnarray*}$

Zwei Fragen:

1.Wo startet deine Fibonacci-Folge, d.h., mit $\begin{eqnarray*} F_0=0,F_1=1 \end{eqnarray*}$ oder doch eher $\begin{eqnarray*} F_0=1,F_1=1 \end{eqnarray*}$ (da gibt es Unterschiede).

2.Für welche $\begin{eqnarray*} n \end{eqnarray*}$ soll die Ungleichung gelten? Für $\begin{eqnarray*} n\leq 2 \end{eqnarray*}$ ist sie sicher falsch.

14.11.2006, 14:17

piloan

Auf diesen Beitrag antworten »

hi
ja sorry ...vergessen anzugeben..

diese Aussage gilt fuer $\begin{eqnarray*} n\geq 3 \end{eqnarray*}$ und fuer die Fibonacci Folge gilt $\begin{eqnarray*} F_0=0,F_1=1, F_2=1 \end{eqnarray*}$

14.11.2006, 14:28

Auf diesen Beitrag antworten »

Kennst du die explizite Darstellung $\begin{eqnarray*} F_n = \frac{1}{\sqrt{5}} \left( \phi^n-(-\phi)^{-n} \right) = \frac{\phi^n}{\sqrt{5}} \left( 1-(-\phi^2)^{-n} \right) \end{eqnarray*}$ ? Wenn nötig, kannst du die durch Induktion beweisen.

Der Rest sind relativ einfache Abschätzungen - wenn man sich geschickt anstellt. Augenzwinkern

14.11.2006, 15:34

piloan

Auf diesen Beitrag antworten »

alles klar ...habs auch :-)

15.11.2006, 11:00

piloan

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Genauer gesagt: Mit dem erweiterten euklidischen Algorithmus, der liefert nämlich ganze Zahlen $\begin{eqnarray*} a,b \end{eqnarray*}$ mit

$\begin{eqnarray*} 5a+3b = \operatorname{ggT}(5,3) \end{eqnarray*}$ , wobei ja $\begin{eqnarray*} \operatorname{ggT}(5,3) = 1 \end{eqnarray*}$ .

Hier wären das $\begin{eqnarray*} a=2,b=-3 \end{eqnarray*}$ , d.h. a=2 ist das inverse Element von 5 modulo 3. Damit ist die Lösung von $\begin{eqnarray*} 5x\equiv 2\mod 3 \end{eqnarray*}$ gleich

$\begin{eqnarray*} x \equiv 2\cdot 5^{-1} \equiv 2\cdot 2 \equiv 1\mod 3 \end{eqnarray*}$ .

das hab ich verstanden und auch fuer andere aufgaben berechnet.
...zb sollte ich

$\begin{eqnarray*} 323x\equiv 120\mod 1001 \end{eqnarray*}$ bestimmen....

habe nun die

$\begin{eqnarray*} a,b \end{eqnarray*}$ bestimmt fuer die gilt

$\begin{eqnarray*} 1001a+323b=ggt(1001,323)=1 \end{eqnarray*}$ hier ist

$\begin{eqnarray*} a=-111, b=344 \end{eqnarray*}$

nun sagt ja $\begin{eqnarray*} 323x\equiv 120\mod 1001 \end{eqnarray*}$

dass $\begin{eqnarray*} 323x-120=1001y \end{eqnarray*}$

warum bestimme ich dann $\begin{eqnarray*} a , b \end{eqnarray*}$ (hab da irgendwie verstaendnis probleme)...wie komme ich auf das inverse , was wohl nur existiert wenn der ggt=1 ist ...
gruß

15.11.2006, 11:05

Auf diesen Beitrag antworten »

Du hast das Inverse von 323 doch vorliegen, es ist das b=344: $\begin{eqnarray*} 323b = 1-1001a \equiv 1 \mod 1001 \end{eqnarray*}$

Folglich kannst du dann rechnen $\begin{eqnarray*} x = 323^{-1} \cdot 120 = 344\cdot 120 \mod 1001 \end{eqnarray*}$

Klar klappt das mit dem Inversen nur bei ggT=1. Im Fall ggT>1 hat ja die Kongruenz auch entweder mehrere oder überhaupt keine Lösungen!

15.11.2006, 11:32

piloan

Auf diesen Beitrag antworten »

genau diesen schritt versteh ich einfach nicht ...
Folglich kannst du dann rechnen $\begin{eqnarray*} x = 323^{-1} \cdot 120 = 344\cdot 120 \mod 1001 \end{eqnarray*}$

der rest ist mir klar.....

15.11.2006, 11:41

Auf diesen Beitrag antworten »

Was genau verstehst du nicht? Dass $\begin{eqnarray*} 323^{-1}\equiv 344\mod 1001 \end{eqnarray*}$ ist?

15.11.2006, 11:58

piloan

Auf diesen Beitrag antworten »

ich soll doch $\begin{eqnarray*} 323x \equiv 120 \mod 1001 \end{eqnarray*}$ bestimmen...

nun hab ich das inverse
und rechne $\begin{eqnarray*} 344*323x \equiv 120*344 \mod 1001 \end{eqnarray*}$

und das ist $\begin{eqnarray*} x \equiv 344*120 \mod 1001 \end{eqnarray*}$ ?

und das vielfache was ich bei 1001 multipliziere ist egal

15.11.2006, 14:16

piloan

Auf diesen Beitrag antworten »

kann das einer bestaetigen oder hab ichs einfach net kapiert ?

15.11.2006, 14:19

Auf diesen Beitrag antworten »

Ja, ist richtig (war schwer als Frage zu erkennen!).

16.11.2006, 15:46

piloan

Auf diesen Beitrag antworten »

so nun noch eine letzte frage zu kongruenzen ...

ich soll
$\begin{eqnarray*} x (mod)1001 \end{eqnarray*}$ bestimmen s.d gilt

$\begin{eqnarray*} x^3+x+1\equiv 0(mod)1001 \end{eqnarray*}$

also muss $\begin{eqnarray*} x^3+x+1=1001y \end{eqnarray*}$ sein. und hier ist ja ende mit

algorithmus oder sehe ichs nicht ?

16.11.2006, 16:03

Auf diesen Beitrag antworten »

Es ist $\begin{eqnarray*} 1001=7\cdot 11\cdot 13 \end{eqnarray*}$ . Nach chinesischem Restsatz ist $\begin{eqnarray*} x \end{eqnarray*}$ genau dann Lösung von $\begin{eqnarray*} x^3+x+1\equiv 1001 \end{eqnarray*}$ , wenn $\begin{eqnarray*} x \end{eqnarray*}$ gleichzeitig Lösung von

$\begin{eqnarray*} x^3+x+1\equiv 0 \mod 7 \end{eqnarray*}$
$\begin{eqnarray*} x^3+x+1\equiv 0 \mod 11 \end{eqnarray*}$
$\begin{eqnarray*} x^3+x+1\equiv 0 \mod 13 \end{eqnarray*}$

ist. Da bereits die erste dieser 3 Kongruenzen überhaupt keine Lösung hat (wie man leicht durch Einsetzen aller 7 Restklassen überprüfen kann), hat sich die Sache erledigt.

Neue Frage »

Antworten »

Zahlentheorie. Kongruenz

Verwandte Themen