Beweis einer Quadratzahl < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:09 Sa 18.11.2006 | | Autor: | Kari |
| Aufgabe | Man zeige: Jede Teilmenge M [mm] \subset [/mm] {2,3,...,100} aus 26 Elementen enthält eine Teilmenge T [mm] \subset [/mm] M, so dass [mm] \produkt_{t \in T}t [/mm] eine Quadratzahl ist.
(Hinweis: Man verwende: eindeutige Primfaktorzerlegung, Vektorraum über K= Z2) |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo!
Ich habe obige Aufgabe für eine Übung zu lösen. Leider komme ich dabei absolut nicht weiter.
Ich habe mir erstmal alle Primzahlen zwischen 2 und 100 rausgeschrieben. Das sind genau 25. Diese bilden ja quasi die Basis des Vektorraumes, da sich jede Zahl zwischen 2 und 100 eindeutig aus dem 25 Primzahlen bestimmen lässt.
Das heißt dann aber, dass eine Teilmenge mit 26 Zahlen irgendwo linear abhängig sein muss, da ja die Anzahl größer als die Anzahl der Basisglieder ist.
Ja, diese Überlegungen sind alle gut und schön, helfen mir aber leider ganz und gar nicht weiter *seufz*
Hat einer von euch eine Idee, wie ich an diese Aufgabe herangehen kann?
Vielen Dank im Voraus!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:21 Sa 18.11.2006 | | Autor: | DaMenge |
Hi,
was soll den der Körper K=Z2 sein? (etwa [mm] $\IF_2$ [/mm] ??)
und wie stellt sich dann zum Beispiel die zahl 12 als Linearkombination der Primzahlen 2 und 3 da ?
wenn man nämlich aus den 26 Zahlen eine zahl v auswählen kann, so dass v als SUMME der anderen Zahlen darstellbar ist, dann ist die Aufgabe recht leicht zu lösen..
(aber ich sehe nicht ganz wie das hier gehen soll, denn wenn der [mm] $\IF_2$ [/mm] gemeint ist, steht da zwar dann eine Summe, aber die Zahl 12 wäre ja nicht mehr aus 2 und 3 erzeugbar...)
viele grüße
DaMenge
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:01 Sa 18.11.2006 | | Autor: | Kari |
Mhh.. ich weiß nicht genau, was mit [mm] \IF_{2} [/mm] gemeint ist. [mm] \IZ_{2} [/mm] soll, wenn ich das richtig verstanden habe, die Modulofunktion darstellen. *seufz*
Dieser Hinweis hat mich auch noch mal verwirrt, obwohl ich zugebe, dass ich das vorher auch schon war.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:34 Sa 18.11.2006 | | Autor: | piet.t |
Hallo Kari,
ich denke im großen und ganzen bist Du mit Deinen Gedanken schon auf der richtigen Spur, jetzt muss man nur noch den Hinweis entsprechend einbauen.
Erstmal zur Notation: ob man jetzt [mm] \IZ/2\IZ [/mm] oder [mm] \IZ_2 [/mm] oder [mm] \IF_2 [/mm] schreibt - gemeint sind immer die Restklassen modulo 2 und die bilden ja bekanntlich einen Körper mit zwei Elementen (nämlich 0 und 1). Ich werde ab jetzt immer [mm] \IF_2 [/mm] verwenden.
Wie Du schon erkannt hast gibt es 25 Primzahlen von 2 bis 100. Zu jeder Zahl z kann man jetzt ja einen (reellen) Vektor bilden, in dem in der Koordinate zur i-ten Primzahl [mm] p_i [/mm] gleich der Potenz von [mm] p_i [/mm] in der Primfaktorzerlegung von z ist. Also in Symbolen:
[mm]z = \produkt_{i=1}^{25} p_i^{e_i} \mapsto v=\vektor{e_1\\e_2\\ \vdots \\ e_{25}}[/mm]
Frage 1: Was passiert in den zugeordneten Vektoren, wenn man zwei Zahlen [mm] z_1 [/mm] und [mm] z_2 [/mm] multipliziert?
Geht man bei den Vektoren jetzt zu den Restklassen mod 2 über, dann hat man ja nur noch die Einträge 0 und 1. Ein Eintrag ist 0, wenn die Potenz der entsprechenden Primzahl in der Primfaktorzerlegung gerade ist, und er ist 1 wenn die Potenz ungerade ist.
Frage 2: Wie erkennt man in der Vektordarstellung über [mm] \IF_2, [/mm] dass die zugehörige Zahl eine Quadratzahl ist?
So, das zusammen mit Deinen bisherigen Überlegungen sollten jetz eigentlich genügen, um Dich bis ans Ende der Aufgabe zu bringen.
Gruß
piet
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:41 Sa 18.11.2006 | | Autor: | DaMenge |
Hallo !
> Frage 1: Was passiert in den zugeordneten Vektoren, wenn
> man zwei Zahlen [mm]z_1[/mm] und [mm]z_2[/mm] multipliziert?
>
> Geht man bei den Vektoren jetzt zu den Restklassen mod 2
> über, dann hat man ja nur noch die Einträge 0 und 1. Ein
> Eintrag ist 0, wenn die Potenz der entsprechenden Primzahl
> in der Primfaktorzerlegung gerade ist, und er ist 1 wenn
> die Potenz ungerade ist.
war ein k-VR nicht ein Raum, wo die skalare Multiplikation nur über Skalare aus K definiert waren?
also nicht die [mm] e_i [/mm] ändern sich, sondern man darf die Vektoren nur mit 0 und 1 multiplizieren.
aber selbst wenn man die komponenten modulo 2 betrachtet, gibt es danach keinen unterschied mehr zw der darstellung von der zahl 8 und der zahl 2, also ist die angegebene Basis keine
(denn die hat ja gerade die eigenschaft der eindeutigen abbildung)
oder steh ich gerade aufm schlauch?
viele Grüße
DaMenge
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:52 Sa 18.11.2006 | | Autor: | piet.t |
Hallo DaMenge,
die Eindeutigkeit der Zuordnung [mm] z\mapsto [/mm] v geht beim Übergang in den [mm] \IF_2^{25} [/mm] sicher verloren - das macht mir in diesem Fall aber nicht viel aus, viel wichtiger ist, dass das Verhalten bei der Multiplikation der z erhalten bleibt.
Und: ja, bei der Bildung einer Linearkombination dürfen nur die Werte 0 und 1 als Skalare vorkommen - mehr brauche ich in dem Fall auch nicht.
Ich bin jetzt bewußt noch etwas schwammig, weil ich Kari ja noch nicht alles vorkauen will. Nur noch zwei Dinge:
Wie würde man ein Produkt aus 26 Zahlen durch die entsprechenden Vektoren darstellen? Und wie ein Produkt einer Teilmenge dieser 26 Vektoren?
Gruß
piet
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:07 Sa 18.11.2006 | | Autor: | DaMenge |
ahh - ok,
man geht also von der Zahl z erstmal zu der Klasse [z] , die entsprechend überall entweder gerade oder ungerade Potenzen hat - dieser VR hat dann Dimension 25...
die darstellungen der 26 zahlen in diesem VR sind dann 26 vektoren, die deshalb linear abhängig sein müssen ..
(und die wesentliche infos ob die "summe" der Vektoren eien quadratzahl wird bleibt ja erhalten)
Der rest ist dann nett und klar.
danke nochmals !
DaMenge
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:55 So 19.11.2006 | | Autor: | Kari |
Hallo ihr zwei!
Vielen Dank für eure Hilfe. Damit werde ich mich jetzt wieder an die Aufgabe machen. Ich denke, mir ist jetzt klar geworden, wie ich weiter machen muss :)
Schönen Sonntag wünsche ich euch noch!
Grüße Kari
|
|
|
|
