Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Wenn Ungerade, dann Gerade - Beweis

Wenn Ungerade, dann Gerade - Beweis

Universität / Fachhochschule

Algebraische Zahlentheorie

Teilbarkeit

Tags: Teilbarkeit

Tester1a aktiv_icon

14:23 Uhr, 02.06.2020

Hallo,

ich beschäftige mich seit einigen Tagen mit der Beweisführung, da ich damit noch große Schwierigkeiten habe.

Ich habe eine Aufgabe aus einer Übung gefunden, welche ich nach mehreren Stunden immer noch nicht lösen konnte:
Beweisen Sie: Sei

x \in ℤ

. Ist

x^{2} - 6 x + 3

gerade, dann ist

x

ungerade.

Mein Lösungansatz:
z.Z:

2 ∣ x^{2} - 6 x + 3 \Rightarrow 2

teilt nicht

x

Also:

\exists x \in ℤ : x^{2} - 6 x + 3 = 2 k_{1} \Rightarrow x = 2 k_{2} - 1

Wenn ich das Beweise führen richtig verstanden habe, so muss ich doch zeigen, wie man von

x^{2} - 6 x + 3 = 2 k_{1}

auf

x = 2 k_{2} - 1

schliessen kann.

Jetzt bin ich meistens ratlos, wie ich weiter vorgehe. Eine Idee war es,

x = 2 k_{2} - 1

in die Prämisse einzusetzen und zu prüfen, dass diese durch 2 teilbar ist. Aber so weit ich weiß, kann ich dies nicht tun, da dies eine Äquivalenz wäre (Ich würde dann ja zußätzlich zu der Implikation annehmen: wenn

x = 2 k_{2} - 1

, dann

2 ∣ x^{2} - 6 x + 3

.

Mehr Einfälle habe ich aktuell nicht. Leidlgich die Tatsache, dass sich die Prämisse auf den ersten Blick mithilfe einer quadratischen Ergänzung umformulieren lässt, sticht mir ins Auge:

(x - 3)^{2} - 6 = 2 k_{1}

.

Ich vermute aber, dass ich meinen Lösungsansatz bereits von vorne rein falsch formuliert habe. Mir fehlen offensichtlich noch die logischen Zusammenhänge.

Könnte mir jemand weiterhelfen? Wo mache ich die Fehler? Vermutlich ist der Beweis relativ einfach, aber für mich gestaltet er sich noch sehr schwer.

Vielen Dank.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

DrBoogie aktiv_icon

14:43 Uhr, 02.06.2020

Am einfachsten wäre hier der Widerspruchsbeweis:
Angenommen,

x

ist gerade. Dann ist auch

x^{2}

gerade,

6 x

ist auch gerade,

3

aber ungerade, damit ist

x^{2} - 6 x + 3

ungerade. Das widerspricht der Angaben. Damit kann

x

nicht gerade sein.

Tester1a aktiv_icon

15:37 Uhr, 02.06.2020

Danke Dr. Boogi. Das erscheint mir logisch. Wenn ich dies nun mathematisch darstellen wollen würde, dann gilt doch:

x^{2} - 6 x + 3 = 2 k_{1}

und

x = 2 k_{2}

Oder? Wie könnte ich das in dieser Form nun darstellen?

anonymous

17:41 Uhr, 02.06.2020

Hallo,

mit

k \in ℤ

gilt für

x := 2 k - 1 \in Z_{U}

Du sollst zeigen dass:

\forall x \in Z_{U} : \forall x^{2} - 6 x + 3 \in Z_{G}

Nimmst du nun einfach

(2 k - 1)^{2} - 6 (2 k - 1) + 3 : \in Z_{G}

brauchst du nur noch ausklammern und erhältst die Aussage:

2 (2 k^{2} - 8 k + 5) : \in Z_{G}

, welche zweifelsfrei wahr ist, da jede ganze Zahl multipliziert mit zwei eine gerade Zahl ergibt und jedes

x := 2 k - 1

eine ungerade ganze Zahl ist.

ermanus aktiv_icon

18:28 Uhr, 02.06.2020

Ja, so wie P-R-O-O-F kann man es direkt
zeigen. Nur einen formalen Mangel möchte ich anmerken:
"

\forall x \in ℤ_{U} : \forall x^{2} - 6 x + 3 \in ℤ_{G}

" gibt keinen Sinn.
Es hätte wohl eher so heißen müssen:
"

\forall x \in ℤ_{U} : x^{2} - 6 x + 3 \in ℤ_{G}

anonymous

20:08 Uhr, 02.06.2020

Darf ich noch als Lösungsvorschlag die quadratische Ergänzung vorschlagen.

x^{2} - 6 \cdot x + 3 = {(x - 3)}^{2} - 6

Für mein Hirn ist dann leichter erkennbar:

a)

Immer wenn

x

gerade ist,
dann ist

(x - 3)

ungerade,
dann bleibt

{(x - 3)}^{2}

ungerade,
dann bleibt

{(x - 3)}^{2} - 6

ungerade.

b)

Immer wenn

x

ungerade ist,
dann ist

(x - 3)

gerade,
dann bleibt

{(x - 3)}^{2}

gerade,
dann bleibt

{(x - 3)}^{2} - 6

gerade.

Tester1a aktiv_icon

20:10 Uhr, 02.06.2020

Vielen Dank. Im Grunde also doch relativ simpel (sagte er, nachdem er stundenlang keine Losung gefunden hat...). Ich hatte dies tatsächlich auch schon selbst versucht, aber ich habe nicht erkannt, dass ich nach dem Einsetzen die binomische Formel zur Auflösung verwenden kann!

Ich beschäftige mich jetzt seit ca. 1 Woche intensiver mit der Beweisführung und es fällt mir (nach wie vor) schwer. Wird das mit der Zeit besser? Wenn ich Lösungen sehe, sind diese einleuchtend und nachvollziehbar, aber selbst auf die Lösung zu kommen ist für mich noch oft relativ schwierig. Wird das mit der Zeit besser?

Schlussendlich noch eine Frage hinsichtlich meinem Verständnis: gibt es in diesem Zusammenhang einen Unterschied zwischen der Aussageform

x := 2 k - 1 \in ℤ

und

x = 2 k - 1 \in ℤ

(also zwischen "ist definiert als" und zwischen "ist gleich")?

@11englich Genau dies habe ich durch die quad. Ergänzung bereits auch vorgeführt (s. Eingangsbeitrag), aber ich habe nicht gesehen, was du beschreibst. Danke dafür.

abakus

20:27 Uhr, 02.06.2020

Ich möchte in Erinnerung rufen, dass

p \to q

äquivalent ist zur Kontraposition

\neg q \to \neg p

.
Der Satz ist also bewiesen, wenn man nachweist, dass aus
"x ist gerade" folgt, dass x²-6x+3 ungerade ist.

ermanus aktiv_icon

22:33 Uhr, 02.06.2020

Hallo,
vielen Dank an abakus:
ich habe es mir geradezu zum Sport gemacht, Widerspruchsbweweise
zu vermeiden, da ich sie für unnötig halte.
Ein Widerspruchsbeweis für eine Implikation

p \to q

funktioniert in
der Regel so, dass man

p \land \neg q \to \neg p

,
also insgesamt durch Wiederholung der ersten Prämisse

p \land \neg q \to p \land \neg p

beweist. Da etwas Falsches nur
aus etwas Falschem folgen kann, muss daher

\neg (p \land \neg q)

gelten,
was nach DeMorgan äquivalent zu

\neg p \lor q

, also zu

p \to q

ist.
Da für die Erfüllung der rechten Seite von

p \land \neg q \to \neg p

die Voraussetzung

p

garnichts beiträgt, kann man
zwecks Entschlackung doch gleich

\neg q \to \neg p

,
also die Kontraposition beweisen.
Ich bitte wegen dieser Weitschweifigkeit um Entschuldigung.
Das Ziel sollte es sein zu zeigen, dass ein Widerspruchsbeweis
nur eine komplizierte undurchsichtigere Art darstellt, eine
Kontraposition zu beweisen.
Für Studierende heißt das, dass es in vielen Fällen, in denen einem
nichts in Richtung

p \to q

einfällt, es einen Versuch wert ist,
die kontrapositive Aussage zu beweisen. Von den bei manchen
Studierenden als besonders trickreich verehrten Widerspruchsbeweisen
würde ich eher abraten.

Gruß ermanus

P.S.: Das ist natürlich alles Geschmackssache ;-)

anonymous

23:03 Uhr, 02.06.2020

Hier noch eine Überlegung,

\forall y = x^{2} - 6 x + 3 \in Z_{G} : x \in Z_{U}

Mit

x = 3 \pm \sqrt{y + 6} \Rightarrow y \in Z_{G}

Tester1a aktiv_icon

11:30 Uhr, 03.06.2020

Nachtrag: komischerweise scheint mein Latex nicht richtig übernommen zu werden. In der Vorschau sieht es richtig aus...

Danke euch. Ich habe einen weiteren Beweis geführt:
Seien

x, y \in ℤ

. Gilt

4 ∣ (x^{2} - 3 y^{2})

, dann ist mindestens eine der Zahlen

x, y

gerade.

Da ich noch Schwierigkeiten habe, das zu Beweisende richtig aufzuschreiben, habe ich mich an P-R-O-O-F orientiert:

k \in ℤ : (x := 2 k \in ℤ_{G}) \lor (y := 2 k \in ℤ_{G})

z.Z.

\exists x \lor \exists y \in ℤ_{G} : 4 ∣ (x^{2} - 3 y^{2}) \in ℤ

Ist dies korrekt? Kann (sollte) man das so schreiben? Ich bin mir an der Stelle sehr oft unsicher, was dann meistens Folgefehler nach sich zieht.

Da ich mit einem direkten Beweis nicht auf eine Lösung gekommen bin, habe ich einen indirekten Beweis (Kontraposition) versucht:

k \in ℤ : (x := 2 k + 1 \in ℤ_{U}) \lor (y := 2 k + 1 \in ℤ_{U})

z.Z.

\forall x \lor \forall y \in ℤ_{U} : \neg (4 ∣ (x^{2} - 3 y^{2})) \in ℤ

Mein Ansatz:

(x^{2} - 3 y^{2}) / 4

(2 k + 1)^{2} - 3 (2 k + 1)^{2} / 4

4 (k)^{2} + 1 - 3 (4 (k)^{2} + 1) / 4

4 (k)^{2} + 1 - 12 - 3 (k)^{2} - 3) / 4

\frac{k^{2} - 14}{4}

Da dies gilt, ist dies ein Widerspruch zu der ersten Beweis-Annahme. Da

k \in ℤ

geht der Termn bspw. für

k = 0

nicht auf in

m a t h b b Z

.
Daraus folgt, dass nicht alle

x, y

ungerade sein dürfen, woraus folgt, dass mindestens

x

oder

y

gerade sein muss und somit gilt die Aussage: Seien

x, y \in ℤ

. Gilt

4 ∣ (x^{2} - 3 y^{2})

, dann ist mindestens eine der Zahlen

x, y

gerade.

Ist meine Beweisführung richtig? Ist diese nachvollziehbar?

ermanus aktiv_icon

12:40 Uhr, 03.06.2020

Hallo,
ich verstehe nicht, wieso du bei

x

und

y

von demselben

k

ausgehst.
Dann wäre ja

x = y

.
Und bei der Kontraposition willst du

x

ungerade UND

y

ungerade

\Rightarrow \neg 4 ∣ (x^{2} - 3 y^{2})

zeigen.
Da hast du aus Versehen ein oder-Zeichen verwendet.
Und da ist noch ein Fehler; es ist

{(2 k + 1)}^{2} = 4 k^{2} + 4 k + 1

Tester1a aktiv_icon

14:40 Uhr, 03.06.2020

Du hast vollkommen Recht!

Seien

x, y \in ℤ

. Gilt

4 ∣ (x^{2} - 3 y^{2})

, dann ist mindestens eine der Zahlen

x, y

gerade.

Direkter Beweis:

k \in ℤ : (x := 2 k_{1} \in ℤ_{G}) \lor (y := 2 k_{2} \in ℤ_{G})

z.Z.:

\exists x \lor \exists y \in ℤ_{G} : 4 ∣ (x^{2} - 3 y^{2}) \in ℤ

Direkter Beweis:

\frac{x^{2} - 3 y^{2}}{4} =

\frac{(2 k)^{2} - 3 (2 k)^{2}}{4} =

\frac{(2 k)^{2} - (6 k)^{2}}{4}

Gekürzt ergibt das:

\frac{k^{2} - (3 k)^{2}}{2}

.

Da im Zähler stets eine gerade Zahl rauskommt(unter der Voraussetung, dass

k = ℤ

ergibt ein Quadrat immer eine gerade Zahl und eine Multiplikation einer geraden Zahl ergibt auch immer eine gerade Zahl, so dass auch Addition/Subtraktion von zwei geraden Zahlen auch immer eine gerade Zahl ergibt), gilt die Aussage für den Fall, dass mindestens eine der Zahlen

x, y

gerade ist.

Indirekter Beweis durch Kontraposition:

k \in ℤ : (x := 2 k_{1} + 1 \in ℤ_{U}) \lor (y := 2 k_{2} + 1 \in ℤ_{U})

z.Z.:

\forall x \land \forall y \in ℤ_{U} : \neg (4 ∣ (x^{2} - 3 y^{2})) \in ℤ

Direkter Beweis:

\frac{x^{2} - 3 y^{2}}{4}

\frac{(2 k + 1)^{2} - 3 ((2 k + 1)^{2})}{4} =

\frac{(2 k)^{2} + 1^{2} - 3 ((2 k)^{2} + 1^{2}))}{4} =

\frac{(2 k)^{2} + 1 - (6 k)^{2} - 3}{4} =

\frac{(2 k)^{2} - (6 k)^{2} - 2}{4} =

\frac{(2 k)^{2} - (6 k)^{2} - 2 * 1}{4}

Gekürzt ergibt das:

\frac{k^{2} - (3 k)^{2} - 1}{2}

.

Da im Zähler stets eine ungerade Zahl rauskommt(unter der Voraussetung, dass

k = ℤ

ergibt ein Quadrat immer eine gerade Zahl und eine Multiplikation einer geraden Zahl ergibt auch immer eine gerade Zahl, so dass auch Addition/Subtraktion von zwei geraden Zahlen auch immer eine gerade Zahl ergibt, so dass durch das Abziehen von |1| immer eine ungerade Zahl entsteht), gilt die Aussage für den Fall, dass beide Zahlen

x, y

ungerade sind. Somit muss auch

4 ∣ (x^{2} - 3 y^{2})

gelten, wenn mindestens eine der beiden Zahlen

x, y

gerade ist.

Ist dies so in Ordnung? Habe ich Fehler gemacht?

ermanus aktiv_icon

15:01 Uhr, 03.06.2020

Dein direkter Beweis geht in die falsche Richtung und ist zudem
unsinnig, da du doch nicht nur ein

k

, sondern zwei im Allgemeinen
verschiedene

k_{1}, k_{2}

hast.
Wichtiger und richtig herum wäre der "indirekte Beweis",
also der Beweis der kontrapositiven Aussage, aber auch hier
schreibst du wieder ein "

\lor

" statt eines "

\land

".
Ich habe dich doch darauf hingewiesen :(
Und wieder nimmst du nur ein

k

statt der i.A. verschiedenen

k_{1}, k_{2}

...
So ist der Beweis leider nicht zu gebrauchen.

Gruß ermanus

Tester1a aktiv_icon

15:16 Uhr, 03.06.2020

Tut mir leid, ich habe zwischen den beiden

k

differenziert, aber falsch abgeschrieben!
Die beiden Beweise gelten aber fuer den Fall, dass zwischen den

k

differenziert wird!

Dies gilt auch hinsichtlich dem

\lor

und

\land

. Auch an der Stelle falsch abgeschrieben. Klar, so ist das natuerlich nicht richtig...ich kann den post leider nicht mehr bearbeiten :(

Grundsätzlich (abgesehen von den Abschreibfehlern) ist also meine Beweisfuehrung aber richtig gewesen, was den indirekten Beweis angeht. Ich verstehe aber nicht, warum der erste Beweis in die falsche Richtung geht? Meinst du damit, dass ich die Implikation umgedreht habe?

ermanus aktiv_icon

15:27 Uhr, 03.06.2020

Zum direkten Beweis:
Ja, du hast die Implikation umgedreht. Wie hättest du
sonst als Voraussetzung

x = 2 k_{1} \lor y = 2 k_{2}

nehmen können?
Da aber die zu beweisende Richtung so "ungünstig" direkt zu
beweisen ist, ist ja die Kontraposition angesagt.
In dieser kann ich dir aber nicht so recht folgen.
Es ist ganz ungünstig durch 4 zu teilen, vielmehr sollte man
möglichst weitreichend 4 ausklammern, dann wird alles viel
durchsichtiger und du musst nicht hinterher lange
Erklärungen abgeben.

Gruß ermanus

Tester1a aktiv_icon

16:04 Uhr, 03.06.2020

Danke dir! Dann habe ich aber noch eine Rueckfrage hinsichtlich dem Post von P-R-O-O-F. Macht er in seinem Beitrag nicht genau das?

Ich wiederhole noch einmal die erste Aufgabe:
Sei

x \in ℤ

. Ist

x^{2} - 6 x + 3

gerade, dann ist

x

ungerade.

Anders ausgedrueckt:

x^{2} - 6 x + 3 : \in ℤ_{G} \Rightarrow x : \in ℤ_{U}

D.h. doch, dass ich von einer ungeraden Zahl

x

nicht(!) darauf schliessen darf, dass

x^{2} - 6 x + 3

gerade ist.

Tut P-R-O-O-F dies denn nicht genau hiermit:

(2 k - 1) 2 - 6 (2 k - 1) + 3 : \in ℤ_{G}

? Er setzt doch hier voraus, dass

x : \in ℤ_{U}

x^{2} - 6 x + 3 : \in ℤ_{G}

zu zeigen. Oder?

ermanus aktiv_icon

16:25 Uhr, 03.06.2020

Ja, ich bin auch nicht glücklich über die Art, wie
P-R-O-O-F die Sache formuliert, er bietet insofern kein
Angriffsziel, weil beide Seiten der Behauptung äquivalent sind (genau dann, wenn ).
Weil du so fleißig dabei warst, hier eine "durchsichtigere"
Lösung unseres letzten Problems:

Behauptung:

4 ∣ (x^{2} - 3 y^{2}) \Rightarrow x \in 2 ℤ \lor y \in 2 ℤ

.
Beweis: Wir beweisen die Kontraposition

x, y \notin 2 ℤ \Rightarrow \neg 4 ∣ (x^{2} - 3 y^{2})

.

Seien also

x, y

ungerade Zahlen,
dann gibt es

k, m \in ℤ

mit

x = 2 k + 1, y = 2 m + 1

.
Damit ergibt sich

x^{2} - 3 y^{2} = (2 k + 1)^{2} - 3 (2 m + 1)^{2} = 4 k^{2} + 4 k + 1 - 3 (4 m^{2} + 4 m + 1) =

= 4 (k^{2} + k - 3 m^{2} - 3 m) - 2

.
Dies lässt bei Division durch 4 den Rest

∣ - 2 ∣ = 2

, ist also nicht durch 4 teilbar,
q.e.d.

Das war doch überhaupt nicht lang oder kompliziert, oder?

Gruß ermanus

anonymous

16:27 Uhr, 03.06.2020

\forall x, y \in Z_{U} : \neg 4 ∣ (x^{2} - 3 y^{2})

Wenn du es auf diesem Weg versuchen willst so kannst du für

x = 2 k + 1

und für

y = 2 ℓ + 1

annehmen,

k, ℓ \in ℤ

.
Du erhältst mit

(2 k + 1)^{2} - 3 (2 ℓ + 1)^{2}

durch Umformung bereits das Ergebnis

4 (k^{2} + k - 3 ℓ^{2} - ℓ) - 2

. Und da jede ganze Zahl mit vier multipliziert und zwei subtrahiert nicht durch vier teilbar ist, so ist auch der mit vier multiplizierte Klammerinhalt minus zwei nicht durch vier teilbar.

anonymous

16:29 Uhr, 03.06.2020

...da ähnelt sich irgendwie etwas :-)

ermanus aktiv_icon

16:30 Uhr, 03.06.2020

Prima! Wenn dies Gedoppele nicht überzeugend ist ;-)
Gruß ermanus

Tester1a aktiv_icon

16:46 Uhr, 03.06.2020

Danke euch! Ich konnte den (aller ersten) Lösungsweg von P-R-O-O-F daher nicht ganz nachvollziehen und habe diesen durch Kontraposition für mich noch einmal bewiesen.

Hinsichtlich dem neuen Lösungsweg(den neuen Lösungswegen): Ich kann den Lösungsweg nachvollziehen. Dieser ist eleganter als meiner, obwohl beide Lösungswege richtig sind.

Eine Frage hätte ich aber noch: woran erkennt ihr denn, dass ihr bspw. die binomische Formel anwendet bzw. ausmultipliziert? Man kann ja durchaus auch wie ich umstellen. Die Aussage ist am Ende die gleiche.

Kommt das mit der Erfahrung oder woran habt ihr das fest gemacht?

Danke für die bisherige Unterstützung! Wirklich toll!

ermanus aktiv_icon

16:51 Uhr, 03.06.2020

Man hat doch garkeine freie Wahl,
wenn man

(2 k + 1)^{2}

auswerten will, dein

(2 k)^{2} + 1

ist ja grottenfalsch ;-)
Insofern verstehe ich nicht, was du damit meinst, dass dein
Beweis richtig sei ????

Tester1a aktiv_icon

17:13 Uhr, 03.06.2020

Autsch, das tut weh...wohl zu lange vor dem Problem gesessen (oder die Tatsache, dass ich mit Mathe jahrelang nichts mehr am Hut hatte). Danke!

1505061

1504895

	Status: nicht eingeloggt	Noch nicht registriert?