Kongruenzrechnung < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:22 So 08.06.2008 | | Autor: | grenife |
| Aufgabe | Beweisen Sie:
Für alle [mm] $x,y,z\in\mathbb{Z}$ [/mm] gilt:
[mm] $x^2+y^2=z^2\Rightarrow xyz\equiv [/mm] 0\ [mm] \mbox{mod}\ [/mm] 60$ |
Hallo zusammen,
weiß bei dieser Aufgabe leider nicht, wie ich bei der Lösung ansetzen soll. Die Aussage rechts bedeutet ja nichts anderes, als daß $xyz$ durch $60$ teilbar sein soll. Aber wie kann ich das mit der ersten Aussage in Verbindung bringen?
Vielen Dank für Eure Hinweise und viele Grüße
Gregor
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:05 So 08.06.2008 | | Autor: | statler |
> Beweisen Sie:
> Für alle [mm]x,y,z\in\mathbb{Z}[/mm] gilt:
> [mm]x^2+y^2=z^2\Rightarrow xyz\equiv 0\ \mbox{mod}\ 60[/mm]
Hallo,
mal so zum Start:
Kannst du dir verklaren, daß von den 3 Zahlen x, y und z (mind.) eine durch 3, eine durch 4 (oder 2 durch 2) und eine durch 5 teilbar sein muß. Betrachte dazu einfach die linke Gl. als Kongruenz.
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:07 So 08.06.2008 | | Autor: | grenife |
Hi,
vielen Dank für den Hinweis. Mir ist klar, dass wenn mind. eine Zahl durch 3, eine durch vier und eine durch 5 teilbar ist, dann enthält xyz [mm] $3\cdot 4\cdot [/mm] 5$ als Primfaktoren und ist somit durch 60 teilbar. Aber mir ist leider nicht klar, wie man von der ersten Gleichung auf diese Aussage schließen kann.
Viele Grüße
Gregor
> > Beweisen Sie:
> > Für alle [mm]x,y,z\in\mathbb{Z}[/mm] gilt:
> > [mm]x^2+y^2=z^2\Rightarrow xyz\equiv 0\ \mbox{mod}\ 60[/mm]
>
> Hallo,
>
> mal so zum Start:
>
> Kannst du dir verklaren, daß von den 3 Zahlen x, y und z
> (mind.) eine durch 3, eine durch 4 und eine durch 5 teilbar
> sein muß. Betrachte dazu einfach die linke Gl. als
> Kongruenz.
>
> Gruß aus HH-Harburg
> Dieter
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:07 So 08.06.2008 | | Autor: | statler |
> Hi,
>
> vielen Dank für den Hinweis. Mir ist klar, dass wenn mind.
> eine Zahl durch 3, eine durch vier und eine durch 5 teilbar
> ist, dann enthält xyz [mm]3\cdot 4\cdot 5[/mm] als Primfaktoren und
> ist somit durch 60 teilbar. Aber mir ist leider nicht klar,
> wie man von der ersten Gleichung auf diese Aussage
> schließen kann.
>
> Viele Grüße
> Gregor
> > > Beweisen Sie:
> > > Für alle [mm]x,y,z\in\mathbb{Z}[/mm] gilt:
> > > [mm]x^2+y^2=z^2\Rightarrow xyz\equiv 0\ \mbox{mod}\ 60[/mm]
Wenn x nicht durch 3 teilbar ist, welchen Rest läßt [mm] x^{2} [/mm] dann mod 3? Ebenso für y. Kann das sein?
Gruß
Dieter
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:25 Di 10.06.2008 | | Autor: | grenife |
Hi,
vielen Dank erstmal für den Hinweis.
Ich zeige also zunächst, dass minestens eine der Zahlen $x,y,z$ durch drei teilbar ist. Annahme: $x,y,z$ seien nicht durch $3$ teilbar. Dann ist z.B $x$ notwendigerweise von der Form $x=3n+1$ oder $x=3n+2$ für eine ganze Zahl $n$. Für den ersten Fall folgt
[mm] $x^2=(3n+1)^2=9n^2+6z+1=3(3n^2+2n)+1$, [/mm] für den zweiten Fall
[mm] $x^2=(3n+2)^2=9n^2+12n+4=3(3n^2+4n+1)+1$. [/mm] In beiden Fällen gilt also [mm] $x^2\equiv [/mm] 1 mod 3$. Für $y$ und $z$ gilt dies ebenso. Somit gibt es jeweils ganze Zahlen $n'$, $n''$ und $n'''$ mit [mm] $x^2=3n'+1$ [/mm] und [mm] $y^2=3n''+1$. [/mm] Demnach muss gelten [mm] $x^2+y^2=3(n'+n'')+2$. [/mm] Da [mm] $z^2$ [/mm] jedoch von der Form [mm] $z^2=3n'''+1$ [/mm] sein muss, ist die Voraussetzung [mm] $x^2+y^2=z^2$ [/mm] verletzt, demnach muss mind. eine Zahl aus $x,y$ oder $z$ durch drei teilbar sein.
Ähnlich würde ich nun für $4$ und $5$ vorgehen.
Vielen Dank für Eure Anmerkungen und viele Grüße
Gregor
> > Hi,
> >
> > vielen Dank für den Hinweis. Mir ist klar, dass wenn mind.
> > eine Zahl durch 3, eine durch vier und eine durch 5 teilbar
> > ist, dann enthält xyz [mm]3\cdot 4\cdot 5[/mm] als Primfaktoren und
> > ist somit durch 60 teilbar. Aber mir ist leider nicht klar,
> > wie man von der ersten Gleichung auf diese Aussage
> > schließen kann.
> >
> > Viele Grüße
> > Gregor
>
> > > > Beweisen Sie:
> > > > Für alle [mm]x,y,z\in\mathbb{Z}[/mm] gilt:
> > > > [mm]x^2+y^2=z^2\Rightarrow xyz\equiv 0\ \mbox{mod}\ 60[/mm]
>
> Wenn x nicht durch 3 teilbar ist, welchen Rest läßt [mm]x^{2}[/mm]
> dann mod 3? Ebenso für y. Kann das sein?
>
> Gruß
> Dieter
>
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:32 Di 10.06.2008 | | Autor: | statler |
Mahlzeit!
> Hi,
>
> vielen Dank erstmal für den Hinweis.
>
> Ich zeige also zunächst, dass minestens eine der Zahlen
> [mm]x,y,z[/mm] durch drei teilbar ist. Annahme: [mm]x,y,z[/mm] seien nicht
> durch [mm]3[/mm] teilbar. Dann ist z.B [mm]x[/mm] notwendigerweise von der
> Form [mm]x=3n+1[/mm] oder [mm]x=3n+2[/mm] für eine ganze Zahl [mm]n[/mm]. Für den
> ersten Fall folgt
> [mm]x^2=(3n+1)^2=9n^2+6z+1=3(3n^2+2n)+1[/mm], für den zweiten Fall
> [mm]x^2=(3n+2)^2=9n^2+12n+4=3(3n^2+4n+1)+1[/mm]. In beiden Fällen
> gilt also [mm]x^2\equiv 1 mod 3[/mm]. Für [mm]y[/mm] und [mm]z[/mm] gilt dies ebenso.
> Somit gibt es jeweils ganze Zahlen [mm]n'[/mm], [mm]n''[/mm] und [mm]n'''[/mm] mit
> [mm]x^2=3n'+1[/mm] und [mm]y^2=3n''+1[/mm]. Demnach muss gelten
> [mm]x^2+y^2=3(n'+n'')+2[/mm]. Da [mm]z^2[/mm] jedoch von der Form [mm]z^2=3n'''+1[/mm]
> sein muss, ist die Voraussetzung [mm]x^2+y^2=z^2[/mm] verletzt,
> demnach muss mind. eine Zahl aus [mm]x,y[/mm] oder [mm]z[/mm] durch drei
> teilbar sein.
>
> Ähnlich würde ich nun für [mm]4[/mm] und [mm]5[/mm] vorgehen.
Das könnte man mit der modulo-Rechnung noch etwas eleganter aufschreiben, aber der Weg ist völlig richtig.
Gruß aus HH-Harburg
Dieter
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:37 Di 10.06.2008 | | Autor: | grenife |
Hi,
stehe bei dem Beweis für die Existenz einer durch 4 teilbaren Zahl etwas auf dem Schlauch:
Zusätzlich muss ja auch eine Zahl aus $x,y$ oder $z$ durch $4$ teilbar [mm] sein.\\
[/mm]
Annahme: $x,y,z$ seien nicht durch $4$ teilbar. Dann ist z.B $x$ notwendigerweise von der Form $x=4n+1$, $x=4n+2$ oder $x=4n+3$ für eine ganze Zahl $n$. Für den ersten Fall folgt
[mm] $x^2=(4n+1)^2=16n^2+8n+1=4(4n^2+2n)+1$,
[/mm]
für den zweiten Fall
[mm] $x^2=(4n+2)^2=16n^2+16n+4=4(4n^2+4n+1)+0$
[/mm]
und für den dritten Fall
[mm] $x^2=(4n+3)^2=16n^2+24n+9=4(4n^2+8n+2)+1$.
[/mm]
Somit gilt entweder [mm] $x^2\equiv [/mm] 1\ [mm] \mbox{mod}\ [/mm] 4$ oder [mm] $x^2\equiv [/mm] 0\ [mm] \mbox{mod}\ [/mm] 4$.
Nur wie komme ich jetzt zu dem gewünschten Widerspruch?
Viele Grüße
Gregor
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:54 Di 10.06.2008 | | Autor: | felixf |
Hallo
> stehe bei dem Beweis für die Existenz einer durch 4
> teilbaren Zahl etwas auf dem Schlauch:
>
> Zusätzlich muss ja auch eine Zahl aus [mm]x,y[/mm] oder [mm]z[/mm] durch [mm]4[/mm]
> teilbar [mm]sein.\\[/mm]
> Annahme: [mm]x,y,z[/mm] seien nicht durch [mm]4[/mm] teilbar. Dann ist z.B [mm]x[/mm]
> notwendigerweise von der Form [mm]x=4n+1[/mm], [mm]x=4n+2[/mm] oder [mm]x=4n+3[/mm]
> für eine ganze Zahl [mm]n[/mm]. Für den ersten Fall folgt
> [mm]x^2=(4n+1)^2=16n^2+8n+1=4(4n^2+2n)+1[/mm],
> für den zweiten Fall
> [mm]x^2=(4n+2)^2=16n^2+16n+4=4(4n^2+4n+1)+0[/mm]
> und für den dritten Fall
> [mm]x^2=(4n+3)^2=16n^2+24n+9=4(4n^2+8n+2)+1[/mm].
> Somit gilt entweder [mm]x^2\equiv 1\ \mbox{mod}\ 4[/mm] oder
> [mm]x^2\equiv 0\ \mbox{mod}\ 4[/mm].
>
> Nur wie komme ich jetzt zu dem gewünschten Widerspruch?
Schau dir die Gleichung modulo 8 an.
Und verwend doch mal bitte Kongruenzrechnung, du bist schliesslich schon im Hauptstudium :)
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:45 Di 10.06.2008 | | Autor: | grenife |
Hi,
dann versuche ich es mal mit Kongruenzrechnung:
Für [mm] $x\equiv [/mm] 1 (4)$, [mm] $x\equiv [/mm] 2 (4)$ bzw. [mm] $x\equiv [/mm] 3 (4)$ gilt:
[mm] $x^2\equiv 1^2=1 [/mm] (4)$, [mm] $x^2\equiv 2^2=4\equiv [/mm] 0 (4)$ bzw. [mm] $x^2\equiv 3^2=9\equiv [/mm] 1 (4)$, also [mm] $x^2\equiv [/mm] 0 (4)$ oder [mm] $x^2\equiv [/mm] 1 (4)$
Der Hinweis mit modulo 8 hilft mir leider micht wirklich weiter, aber könnte ich nicht auch folgern, dass für [mm] $x^2\equiv [/mm] 1(4)$ und [mm] $y^2\equiv [/mm] 1(4)$ gelten müsste [mm] $x^2+y^2\equiv [/mm] 1+1(4)$ was der Voraussetzung [mm] $z^2\equiv [/mm] 0(4)$ oder [mm] $z^2\equiv [/mm] 1(4)$ widerspricht?
Viele Grüße
Gregor
> Hallo
>
> > stehe bei dem Beweis für die Existenz einer durch 4
> > teilbaren Zahl etwas auf dem Schlauch:
> >
> > Zusätzlich muss ja auch eine Zahl aus [mm]x,y[/mm] oder [mm]z[/mm] durch [mm]4[/mm]
> > teilbar [mm]sein.\\[/mm]
> > Annahme: [mm]x,y,z[/mm] seien nicht durch [mm]4[/mm] teilbar. Dann ist
> z.B [mm]x[/mm]
> > notwendigerweise von der Form [mm]x=4n+1[/mm], [mm]x=4n+2[/mm] oder [mm]x=4n+3[/mm]
> > für eine ganze Zahl [mm]n[/mm]. Für den ersten Fall folgt
> > [mm]x^2=(4n+1)^2=16n^2+8n+1=4(4n^2+2n)+1[/mm],
> > für den zweiten Fall
> > [mm]x^2=(4n+2)^2=16n^2+16n+4=4(4n^2+4n+1)+0[/mm]
> > und für den dritten Fall
> > [mm]x^2=(4n+3)^2=16n^2+24n+9=4(4n^2+8n+2)+1[/mm].
> > Somit gilt entweder [mm]x^2\equiv 1\ \mbox{mod}\ 4[/mm] oder
> > [mm]x^2\equiv 0\ \mbox{mod}\ 4[/mm].
> >
> > Nur wie komme ich jetzt zu dem gewünschten Widerspruch?
>
> Schau dir die Gleichung modulo 8 an.
>
> Und verwend doch mal bitte Kongruenzrechnung, du bist
> schliesslich schon im Hauptstudium :)
>
> LG Felix
>
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:05 Di 10.06.2008 | | Autor: | statler |
Hi, jetzt wieder ich:
> dann versuche ich es mal mit Kongruenzrechnung:
Lobenswert!
>
> Für [mm]x\equiv 1 (4)[/mm], [mm]x\equiv 2 (4)[/mm] bzw. [mm]x\equiv 3 (4)[/mm] gilt:
> [mm]x^2\equiv 1^2=1 (4)[/mm], [mm]x^2\equiv 2^2=4\equiv 0 (4)[/mm] bzw.
> [mm]x^2\equiv 3^2=9\equiv 1 (4)[/mm], also [mm]x^2\equiv 0 (4)[/mm] oder
> [mm]x^2\equiv 1 (4)[/mm]
>
> Der Hinweis mit modulo 8 hilft mir leider micht wirklich
> weiter, aber könnte ich nicht auch folgern, dass für
> [mm]x^2\equiv 1(4)[/mm] und [mm]y^2\equiv 1(4)[/mm] gelten müsste
> [mm]x^2+y^2\equiv 1+1(4)[/mm] was der Voraussetzung [mm]z^2\equiv 0(4)[/mm]
> oder [mm]z^2\equiv 1(4)[/mm] widerspricht?
So kann es eben nicht aussehen! Modulo 4 steht da 0 + 1 = 1 oder 0 + 0 = 0. Im 2. Fall bist du durch, weil dann 2 (sogar alle 3) Quadrate gerade sind, also auch 2 Zahlen, also ist das Produkt durch 4 teilbar.
Bleibt der andere Fall, und für den gehst du über zu den Restklassen mod 8. Welche sind da möglich? Stell dir einfach alle Fälle zusammen, dann müßte es dir wie Schuppen von den Augen fallen.
Es ist echt nicht schwer, und was du mit 4 gekonnt hast, wirst du mit 8 auch hinkriegen.
Gruß
Dieter
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:41 Di 10.06.2008 | | Autor: | grenife |
Hi,
ich versuche das mal zusammen zu fassen:
Annahme: $x,y,z$ sind alle nicht durch 4 teilbar.
Dann gilt für alle drei Zahlen (beispielhaft sei x genannt)
[mm] $x^2\equiv [/mm] 0(4)$ oder [mm] $x^2\equiv [/mm] 1(4)$
Dann folgt für [mm] $x^2+y^2$:
[/mm]
[mm] $x^2+y^2\equiv [/mm] 1+0=1(4)$ oder
[mm] $x^2+y^2\equiv [/mm] 0+0=0(4)$ oder
[mm] $x^2+y^2\equiv [/mm] 1+1=2(4)$.
Im letzten Fall folgt der Widerspruch wegen [mm] $z^2\equiv [/mm] 1(4)$ oder [mm] $z^2\equiv [/mm] 1(4)$.
Im zweiten Fall sind [mm] $x^2$ [/mm] und [mm] $y^2$ [/mm] durch $4$ teilbar, also insb. gerade. Somit müssen auch $x$ und $y$ die $2$ als Primfaktor enthalten und $xyz$ ist durch $4$ teilbar (hier erhalte ich somit gar keinen Widerspruch).
Im ersten Fall [mm] ($x^2+y^2\equiv [/mm] 1(4)$) weiß ich leider immer noch nicht, was mir der Übergang zu den Restklassen mod 8 liefert. Ich kann ja schreiben:
[mm] $x^2+y^2\equiv 1(4)\Rightarrow (x^2+y^2)^2\equiv 1^2(8)$. [/mm] Aber das bringt mich auch nicht wirklich weiter...:-(
Vielen Dank für Eure Geduld und viele Grüße
Gregor
> Hi, jetzt wieder ich:
>
> > dann versuche ich es mal mit Kongruenzrechnung:
> Lobenswert!
> >
> > Für [mm]x\equiv 1 (4)[/mm], [mm]x\equiv 2 (4)[/mm] bzw. [mm]x\equiv 3 (4)[/mm] gilt:
> > [mm]x^2\equiv 1^2=1 (4)[/mm], [mm]x^2\equiv 2^2=4\equiv 0 (4)[/mm] bzw.
> > [mm]x^2\equiv 3^2=9\equiv 1 (4)[/mm], also [mm]x^2\equiv 0 (4)[/mm] oder
> > [mm]x^2\equiv 1 (4)[/mm]
> >
> > Der Hinweis mit modulo 8 hilft mir leider micht wirklich
> > weiter, aber könnte ich nicht auch folgern, dass für
> > [mm]x^2\equiv 1(4)[/mm] und [mm]y^2\equiv 1(4)[/mm] gelten müsste
> > [mm]x^2+y^2\equiv 1+1(4)[/mm] was der Voraussetzung [mm]z^2\equiv 0(4)[/mm]
> > oder [mm]z^2\equiv 1(4)[/mm] widerspricht?
>
> So kann es eben nicht aussehen! Modulo 4 steht da 0 + 1 = 1
> oder 0 + 0 = 0. Im 2. Fall bist du durch, weil dann 2
> (sogar alle 3) Quadrate gerade sind, also auch 2 Zahlen,
> also ist das Produkt durch 4 teilbar.
> Bleibt der andere Fall, und für den gehst du über zu den
> Restklassen mod 8. Welche sind da möglich? Stell dir
> einfach alle Fälle zusammen, dann müßte es dir wie Schuppen
> von den Augen fallen.
>
> Es ist echt nicht schwer, und was du mit 4 gekonnt hast,
> wirst du mit 8 auch hinkriegen.
>
> Gruß
> Dieter
>
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:49 Mi 11.06.2008 | | Autor: | statler |
Guten Morgen junger Mann!
> Im ersten Fall ([mm]x^2+y^2\equiv 1(4)[/mm]) weiß ich leider immer
> noch nicht, was mir der Übergang zu den Restklassen mod 8
> liefert. Ich kann ja schreiben:
> [mm]x^2+y^2\equiv 1(4)\Rightarrow (x^2+y^2)^2\equiv 1^2(8)[/mm].
> Aber das bringt mich auch nicht wirklich weiter...:-(
>
> Vielen Dank für Eure Geduld und viele Grüße
Die Geduld hat natürlich inzwischen ein ganz bißchen abgenommen. Deswegen machen wir jetzt im Anweisungsstil weiter und ändern den Ansatz. Wir arbeiten wie die Experimentalphysiker.
Du mußt noch den Fall 'gerade + ungerade = ungerade' untersuchen. Dazu solltest du dir im ersten Schritt - um Untersuchungsmaterial und ein paar Resultate zu haben - mal die Zahlen von 0 bis 7 hernehmen, sie quadrieren und prüfen, was die Quadrate als Reste mod 8 lassen.
Im 2. Schritt versuchst du dann, die besagte Gleichung 'gerade + ungerade = ungerade' mod 8 zusammenzubauen. Da wirst du eine echte Überraschung erleben.
Und jetzt frisch ans Werk!
Gruß aus HH-Harburg
Dieter
|
|
|
|
