Zahlentheoret. Problem < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Die Folge ganzer Zahlen [mm] (x_{1}, x_{2}, x_{3}, x_{4}...) [/mm] = (34, 67, 14,27...) wurde mit einem linearen Kongruenzgenerator [mm] x_{i} \equiv ax_{i-1} [/mm] + b mod N, i=1,2... erzeugt. Um die Werte 0 [mm] \le x_{i} \le [/mm] N (1 [mm] \le [/mm] i [mm] \le [/mm] 4) zu berechnen, wurden positive ganze Zahlen a, b, N benutzt, sowie der ganzzahlige "Keim" [mm] x_{0} [/mm] = 43. Bestimmen Sie a,b und N. |
Hallo erstmal!
Ich weiß leider nicht, wie ich bei der obigen Aufgabe weiterkomme. Bis jetzt habe ich folgende 4 Gleichungen aufgestellt:
34 [mm] \equiv [/mm] a43 +b mod N
67 [mm] \equiv [/mm] a34 + b mod N
14 [mm] \equiv [/mm] a67 + b mod N
27 [mm] \equiv [/mm] a14 +b mod N
Doch wie geht es jetzt weiter, kann mir bitte jemand helfen?
Gruß, Maren
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:45 Do 15.02.2007 | | Autor: | wauwau |
Aufgrund der Zahlenreihe muss N > 67 sein und b < N
folgendes Gl.System ist ja damit gegeben:
(1) 43a + b = [mm] k_{1}N [/mm] + 34
(2) 34a + b = [mm] k_{2}N [/mm] + 67
(3) 67a + b = [mm] k_{3}N [/mm] + 14
(4) 14a + b = [mm] k_{4}N [/mm] + 27
(1) - (2) und (2) - (4) und (3) - (1) (elimination von b)
ergeben drei neue Gleichungen
(i), (ii) und (iii) (Ausrechnen kannst du es ja selbst)
8(i)-3(iii) (elimination von a)
ergibt
204 = s.N mit einem ganzzahligen s und daher N teilt 204
analog
5(iii)-6(ii)
ergibt
340 = t.N mit einem ganzzahligen t und daher N teilt 340
d.h. N muss ein Teiler größer 67 von 204 und 340 sein - daher N=68
daher (2)
34a + b = [mm] k_{2}68 [/mm] +67 module 34 betrachtet ergibt dass
b [mm] \equiv [/mm] -1 mod 34 ist
daher entweder b=33 oder b=67 da ja b < N sein muss.
Fall 1: b=33
(4) ergibt 14a + 33 = [mm] k_{4}68 [/mm] + 27 oder
14a = [mm] 68k_{4} [/mm] - 6 (a)
(2) detto 34a = [mm] 68k_{2} [/mm] +34 (b)
7(b)-17(a): 0 = [mm] 68(7k_{2}-17k_{4})+340
[/mm]
oder aber [mm] 17k_{4}-7k_{2}=5 [/mm] mit ganzzahligen [mm] k_{i}
[/mm]
entweder du löst diese diophantische glg allgemein [mm] (k_{2}=17s-8 [/mm] und [mm] k_{4}=7s-3 [/mm] für beliebige ganzz. s) oder siehst, dass [mm] k_{2}=9 [/mm] und [mm] k_{4}=4 [/mm] eine Lösung ist.
Damit ergibt sich a=19
Da a=19, b=33 und N=68 wie man sich überzeugen kann eine Lösung ist, braucht nicht weitergesucht zu werden.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:35 Do 15.02.2007 | | Autor: | frustriert |
Vielen Dank für die tolle Antwort! Jetzt ist alles klar 
|
|
|
| |
|
| Aufgabe | Für eine beliebige Zahl n [mm] \ge [/mm] 2 betrachtet man das Gleichungssystem
2x +y -3z = 0
3x -y +2z = 0
5x +2y -7z = 0
in den Unbekannten x, y, z über dem Restklassenring [mm] \IZ/n\IZ. [/mm] Bestimmen Sie in Abhängigkeit von n die Lösungsmenge [mm] \IL_{n} [/mm] dieses Systems. |
Habe jetzt doch noch eine Frage. Muss ich diese Aufgabe genauso wie die vorherige Aufgabe lösen, d. h. erst ein n bestimmen und in Abhängigkeit davon dann x, y und z lösen?
Danke schonmal,
Grüße, Maren
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:50 Fr 16.02.2007 | | Autor: | wauwau |
Durch Umformung (elimination von x) kommst du auf
4y [mm] \equiv [/mm] 0(n) bzw
4z [mm] \equiv [/mm] 0(n)
Folgende Fälle muss man nun Unterscheiden
1) ggt(4,n) = 1
daraus folgt sofort y [mm] \equiv [/mm] 0(n) und z [mm] \equiv [/mm] 0(n) und damit aus der ersten Gleichung y [mm] \equiv [/mm] 0(n)
also (0,0,0) als Lösung
2) ggt(4,n) = 2
daraus folgt sofort y und z [mm] \equiv 0(\bruch{n}{2}) [/mm] also entweder 0 oder [mm] \bruch{n}{2}
[/mm]
daher als mögliche Lösungen
[mm] (x,0,\bruch{n}{2})
[/mm]
(x,0,0)
[mm] (x,\bruch{n}{2},0)
[/mm]
[mm] (x,\bruch{n}{2},\bruch{n}{2})
[/mm]
diese Lösung in die Gleichungen eingesetzt ergeben die Lösungen für x
damit hast du alle Lösungen für diesen Fall
3) ggt(4,n)=4
daraus folgt sofort y und z [mm] \equiv 0(\bruch{n}{4}) [/mm] also entweder 0, [mm] \bruch{n}{4}, \bruch{n}{2}, \bruch{3n}{4}
[/mm]
die möglichen 8 Lösungen setzt du wieder in die erste Gleichung ein und erhältst somit die gesuchten Gesamtlösungen
|
|
|
| |
|
Danke erstmal! Trotzdem steige ich bei manchen Dingen noch nicht so ganz durch...
> Durch Umformung (elimination von x) kommst du auf
>
> 4y [mm]\equiv[/mm] 0(n) bzw
> 4z [mm]\equiv[/mm] 0(n)
Ich komme da immer auf
-8y [mm]\equiv[/mm] 0(n)
-8z [mm]\equiv[/mm] 0(n)
(Habe erst 3*1 - 2*2, 5*1 - 2*3 umgeformt und dann nach y und z umgeformt) Das wäre dann doch ein anderes Ergebnis, oder?
> 3) ggt(4,n)=4
> daraus folgt sofort y und z [mm]\equiv 0(\bruch{n}{4})[/mm] also
> entweder 0, [mm]\bruch{n}{4}, \bruch{n}{2}, \bruch{3n}{4}[/mm]
> die
> möglichen 8 Lösungen setzt du wieder in die erste Gleichung
> ein und erhältst somit die gesuchten Gesamtlösungen
Wie kommst du auf [mm]\bruch{3n}{4}[/mm] und müssten es nicht mögliche 16 Lösungen sein?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:47 Sa 17.02.2007 | | Autor: | moudi |
Hallo Maren
Du musst aufpassen beim Lösen eines Gleichungssystems. Damit das Gleichungssystem äquivalent bleibt, darf man zu einer Gleichung ein Vielfaches einer anderen Gleichung addieren. Jedoch darf man nicht eine Gleichung mit einer Zahl multiplizieren (z.B. Wenn du in [mm] $\IZ/3\IZ$ [/mm] mit 3 multiplizierst, dann hast du ja mit 0 multipliziert und du verlierst die Information dieser Gleichung vollständig).
Du hast 3* (1)-2*(2) gerechnet, d.h. du hast zuerst Gleichung (1) mit 3 multipliziert und dann das (-2)-fache der zweiten Gleichung addiert. Das zweite ist ok, dar das erste ist nicht ok. wenn n=3, hast du die erste Gleichung mit 0 multipliziert.
Ich würde zuerst y eliminieren: nämlich (4)=(1)+(2) und (5)=(3)+2(2) und dann z eliminieren mittels (5)-3(4). Dann erhälst du die Gleichung 4x=0.
etc.
mfG Moudi
|
|
|
| |
|
Hallo Moudi!
Danke für den Hinweis mit der Multiplikation, hatte ich wirklich total vergessen. Aber hat wauwau in seinem ersten Beitrag nicht genau dasselbe getan, als er 8(i) -3(iii) ausgeführt hat?
Kannst du mir vielleicht auch noch einen Tip bezüglich meiner zweiten Frage (16 Lösungen?) geben? Das wäre wirklich super!
Schönen Sonntag noch,
Maren
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:24 Di 20.02.2007 | | Autor: | wauwau |
Siehe andere Antwort
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:32 Mo 19.02.2007 | | Autor: | wauwau |
> Für eine beliebige Zahl n [mm]\ge[/mm] 2 betrachtet man das
> Gleichungssystem
> 2x +y -3z = 0
> 3x -y +2z = 0
> 5x +2y -7z = 0
> in den Unbekannten x, y, z über dem Restklassenring
> [mm]\IZ/n\IZ.[/mm] Bestimmen Sie in Abhängigkeit von n die
> Lösungsmenge [mm]\IL_{n}[/mm] dieses Systems.
> Habe jetzt doch noch eine Frage. Muss ich diese Aufgabe
> genauso wie die vorherige Aufgabe lösen, d. h. erst ein n
> bestimmen und in Abhängigkeit davon dann x, y und z lösen?
>
> Danke schonmal,
>
> Grüße, Maren
moudi hat zwar Recht mit seinem Hinweis, die Spezialfälle n=2,3,5,7 (Koeffizienten des Glg. Systems, die bei Umformung eine Rolle spielen, kann
man extra behandeln:
Denn für n=2 lautet das System
y-z=0
x-y=0
x-z=0
und daraus x=y=z sodass (0,0,0) und (1,1,1) eine Lösung sind
n=3
-x+y=0
-y-z=0
-x-y-z=0
daraus x=0 y=0 z=0 als einzige Lösung
n=5
2x+y+z=0
-2x-y+2z=0
y-z=0
und daraus wiederum x=y=z=0
n=7
aus der 3. Glg folg wiederm x=y und daraus (0,0,0) als Lösung
P.S.: mit den 16 Lösungen hast du natürlich Recht!!!!!!!
|
|
|
| |
|
Hallo Wauwau!
Zu allererst: Danke schonmal! Wenn ich das also richtig verstanden habe, darf ich den Rechenschritt 8(i) - 3(ii) aus deiner ersten Antwort auf meine erste Frage nicht durchführen... Ich habe dann ja
(i) 9a = sN -33
(ii) 20a = sN +40
(iii) 24 = sN - 20
Wie kann ich aber jetzt a eliminieren, wenn ich eine Gleichung nicht multiplizieren darf, sondern nur ein Vielfaches einer anderen Gleichung subtrahieren/addieren darf? Brüche darf ich in Z ja auch nicht benutzen...
Außerdem weiß ich leider immer noch nicht, wie du in deiner ersten Antwort zu meiner zweiten Frage auf [mm] \bruch{3n}{4} [/mm] kommst :-(
Tut mir leid, das ist wahrscheinlich alles nicht schwer, trotzdem komme ich nicht drauf...
Grüße,
Maren
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:01 Mi 21.02.2007 | | Autor: | wauwau |
Man kann durchaus annehmen, dass die Angebot irreduzibel ist, d.h.
Ich habe auch geschrieben, dass mann aufgrund der Koeff N>67 annehmen kann,
denn wäre N<67, dann könnte man die Angabe reduzieren, d.h.
beispielsweise wenn N=65, dann würde der Koeff. nicht mehr 67 sondern reduziert 2 lauten.
D.h. im Prinzip kann man daher alle Umformungen gefahrlos durchführen, solange dies keine Mult. mit großen Zahlen als 67 bedeutet.
Willst du jedoch ganz genau sein, müsstest du bei der Umformung
8(i)-3(iii) den Fall N=8 ausschließen und getrennt als Spezialfall gesondert betrachten..
Falls N durch 4 teilbar ist, dann sind nur die Zahlen
0, n/4, n/2 und 3n/4 kongruent 0 modulo N/4
daher komme ich auf 3n/4
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:40 Mi 21.02.2007 | | Autor: | unknown |
Hallo Maren,
auch wenn diese Frage ja beantwortet ist, wollte ich doch eben kurz auf einen kleinen "Trick" hinweisen, der bei Gleichungssystemen über [mm] $\IZ$ [/mm] (oder anderen Euklidischen Ringen) immer sehr praktisch ist. Vielleicht kommen ja nochmal ähnliche Aufgaben.
Man kann nämlich Koeffizienten einer Variablen mittels Addition von Zeilen in allen Zeilen bis auf einer eliminieren, wo dann der ggT der Koeffizienten stehen bleibt. Besonders praktisch ist das natürlich, wenn die Koeffizienten teilerfremd sind, weil man dann eine $1$ erzeugen kann. Das funktioniert einfach mit dem Euklidischen Algorithmus.
Bei Deinen Gleichungen sind $20$ und $9$ teilerfremde Koeffizienten von $a$. Der Quotient bei Division von $20$ durch $9$ ist $2$, und es gilt $20 - [mm] 2\cdot9 [/mm] = 2$. Der Quotient von $9$ durch $2$ ist $4$, als Rest bleibt $1$. Wenn Du nun [mm] $\hbox{(ii)} [/mm] - [mm] 2\hbox{(i)}$, $\hbox{(i)} [/mm] - [mm] 4\hbox{(ii)}$ [/mm] und dann [mm] $\hbox{(ii)} [/mm] - [mm] 2\hbox{(i)}$ [/mm] rechnest, erhälst Du (mit immer gültigen Umformungen)
(i)' $a = 5sN - 457$
(ii)' $0 = -11sN + 1020$
(An dieser Stelle sehe ich allerdings, dass die Zahlen aus Deinem Post irgendwie nicht stimmen können, denn $11$ ist kein Teiler von $1020$, womit das System unlösbar wird...).
Vielleicht hilft's.
|
|
|
|
