Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Beweis für Reflexivität

Beweis für Reflexivität

Universität / Fachhochschule

Teilbarkeit

Tags: Teilbarkeit

Blaub33r3 aktiv_icon

12:16 Uhr, 28.11.2009

Hallo Leute,

Also ich habe eine Relation nRm

\Leftrightarrow

ggT(n,m)>1
Ich soll zeigen, dass diese Relation reflexiv ist.

Man soll also beweisen, dass ggT(n,n)>1 gilt. Aber wie mach ich das?

Grüße Daniel

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

hagman aktiv_icon

12:19 Uhr, 28.11.2009

Für

n

aus welcher Menge? Da fehlt noch eine wichtige Einschränkung!

Und ggT(n,n) sollte doch auszurechnen sein

. .

Blaub33r3 aktiv_icon

12:25 Uhr, 28.11.2009

n, m

sind Elemente aus den Natürlichen Zahlen außer

0,1

. Sorry das hab ich jetzt ganz vergessen mit anzugeben!! Also

n, m \geq 2

aus IN

Auszurechnen

. .

. ggT(4,4)>1 aber das soll man ja jetzt beweisen.

Soll man hier vllt einen Beweis durch Wiederspruch anführen?

ggT(n,n)=1

1 \cdot x = n 1 \cdot y = n \Rightarrow x - y = 0

Eine andere Idee bekomm ich irgendwie nicht.

Grüße

hagman aktiv_icon

12:28 Uhr, 28.11.2009

Nenn mir mal spontan zwei verschiedene Teiler von

98123746192561931

arrow30

12:51 Uhr, 28.11.2009

ich glaube hagman versuchte dir zu zeigen das

98123746192561931

ein teiler von

98123746192561931

(ohne 2 mal nachzudenken )
nun mal eine Frage was ist die Definition von ggt ?

Blaub33r3 aktiv_icon

13:11 Uhr, 28.11.2009

Der größte gemeinsame Teiler zweier ganzer Zahlen

m

und

n

ist die größte natürliche Zahl, durch die sowohl

m

als auch

n

ohne Rest teilbar sind.

ggT(n,m)=s*n+t*m

Ja eine Zahl

\times \times \times

ist nur durch 1 und

\times \times \times

teilbar.
Hm...soll ich vllt einen Beweis durch den Euklidschen Algorithmus vollführen?

arrow30

13:13 Uhr, 28.11.2009

Genau das wollte Hagman von dir hören ich zitiere dich "Der größte gemeinsame Teiler zweier ganzer Zahlen

m

und

n

ist die größte natürliche Zahl, durch die sowohl

m

als auch

n

ohne Rest teilbar sind." und jetzt überlege es dir noch mal was ist der ggt(n,n)

Blaub33r3 aktiv_icon

13:17 Uhr, 28.11.2009

wenn

n = m

gilt und der ggT von

n, n

ist. Dann ist ggT(n,n)=n Aber das is doch nicht mathematisch formal genug..Müsste ich mir jetzt überlegen, wieso der ggT(n)=n ist?

arrow30

13:27 Uhr, 28.11.2009

nicht mathematisch formal genug ? du kannst ja ggt(n,n) mit Euk. Alg gewinnen :

n = n \cdot 1 + 0

fertig :-)
du kannst auch sagen angenommen ggt(n,n)

= d

mit

d > n

das führ dich zu einem Widerspruch ! (wenn

d > n)

dann darf

d n

nicht teilen .aber die Def. reicht schon

n

teilt

n

und größeren Teiler foindest du nicht !

HP7289 aktiv_icon

13:27 Uhr, 28.11.2009

ggT(n,n)=n, weil

n | n

und

\neg (n + k | n) \forall k \in ℕ

Blaub33r3 aktiv_icon

13:52 Uhr, 28.11.2009

Danke für die schnellen und guten Antworten :-)

¬(n+k|n)∀k∈ℕ Wie kommst du darauf? Ist das ein Negations-Zeichen, das hab ich noch nirgends gesehn!?

Grüße

arrow30

13:55 Uhr, 28.11.2009

weil

(n + k) > n

gilt

! (n + k) | n

er wollte es für dich mathematisch ausdrücken

Blaub33r3 aktiv_icon

14:41 Uhr, 28.11.2009

Alles klar, besten Dank!

Ich hätte noch eine kleine Zusatzfrage, und zwar gibt es einen Beweis für Transitivität?

für nRm

\Leftrightarrow

ggT(n,m)>1 mit

n > 2

aus IN

hab ich mir überlegt:

8 R 4, 4 R 2

und

8 R 2

oder stimmt das so nicht weil als Ergebnis

4, 2, 2

rauskäme?

oder Moment

6 R 4,4 R 2

und

6 R 2 \Leftrightarrow 2,2

und 2 also gibt es doch ein "bisschen" Transitivität :-)?

Reicht das als Beweis?

Grüße

arrow30

15:03 Uhr, 28.11.2009

hier reicht es nicht nur ein paar Zahlen zu geben musst du schon allgemein zeigen für

n, m \geq 2

ggt(n,m)>1

\Leftrightarrow

es gibt ein

d > 1

mit

d | n

und

d | m \Leftrightarrow n = d \cdot k_{1}

und

m = d \cdot k_{2}

mit

k_{1}, k_{2} \in ℕ

ggt(m,x)>1

\Leftrightarrow

es gibt ein

d_{1} > 1

mit

d_{1} | m

und

d_{1} | x \Leftrightarrow m = d_{1} \cdot k_{3}

und

x = d_{1} \cdot k_{4}

daraus musst du einiges folgern

Blaub33r3 aktiv_icon

15:42 Uhr, 28.11.2009

Also ich verstehe das was du geschrieben hast. Und damit soll ich zeigen das ggT(n,m)=ggT(m,x)=ggT(n,x) gilt..Hm wie fang ich denn jetzt an :/ ?

Ich habe also 4 Gleichungen

(1) n=d*k1 (2) m=d*k2 (3) m=d1*k3 (4) x=d1*k4

Ich hab (1),(2) nach d aufgelöst ,gleichgesetzt und nach m umgestellt

=> m=(k2*n)/k1

Ebenso (3), (4) nach d1 aufgelöst, gleichgesetzt und nach m umgestellt

=> m=(k3*x)/k4

=> m=m <=> (k2*n)/k1=(k3*x)/k4 Jetzt hab ich eine "schwache" Verbindung zwischen n und x. (k2*n)/k1=(k3*x)/k4 <=> n*(k2/k1)=x*(k3/k4)

Bin ich aufm richtigen Weg, oder was folgere ich nun daraus?

arrow30

15:44 Uhr, 28.11.2009

das habe ich nicht gesagt :-)
die Gleichheit hat mir überhaupt nicht gut gefallen du sollst folgern, dass
ggt(n,m)

> 1

und ggt(m,x)

> 1

dann auch ggt(n,x)

> 1

Blaub33r3 aktiv_icon

15:58 Uhr, 28.11.2009

Noch eine Frage zum Verständnis, wäre dann

8 R 4, 4 R 2

und

8 R 2

auch transitiv, weil ggT(8,4)>1 ggT(4,2)>1 und ggT(8,2)>1 gilt?

Zeig mir mal bitte den Anfang, ich bin mehr am Rätseln als am Nachdenken

\frac{:}{}

ggT(n,m)>1 da

n, m

Elemente aus IN ohne

0,1

sind! Ebenso gilt es für die Variable

x

.

Grüße

hagman aktiv_icon

16:07 Uhr, 28.11.2009

Transitivität ist keien Eigenschaft nur von drei Zahlenbeispielen, sondern der gesamten Menge. (Allerdings kann man Transitivität durch ein einziges Gegenbsiepiel falsifizieren).

Zum Nachweis der Transitivität müsstest du (Konjunktivus irrealis!) also zeigen, dass wenn

m

und

n

einen Teiler

> 1

gemeinsam haben und

n

und

k

einen Teiler

> 1

gemeinsam haben, automatisch auch

m

und

k

eine Teiler

> 1

gemeinsam haben.
Hinweis: Es *gibt* ein kleines Gegenbeispiel.

Blaub33r3 aktiv_icon

17:01 Uhr, 28.11.2009

8 R 4,4 R 2

und

8 R 2

wäre das Transitiv oder nicht, ich weiß immer noch, Ob das Ergebnis dieser 3 verschieden Relation, gleich sein muss oder nicht!? Das verwirrt mich unheimlich.

Für mich wäre

8 R 4, 4 R 2, 8 R 2

nicht transitiv weil ggT(8,4)=4, ggT(4,2)=2, ggT(8,2)=2 nicht gleiche Ergebnisse liefert.
Anders wär es für mich transitiv für ein anderes Zahlenbsp.

6 R 4, 4 R 2, 6 R 2

Auch wenn es vereinzelte transitive Verbindungen in der Menge existieren, heisst das nicht das die gesamte Menge transitiv ist, durch ein Gegenbsp. definitiert man eine Menge also als NICHT-Transitiv. Hab ich das richtig verstanden?

hagman aktiv_icon

17:34 Uhr, 28.11.2009

Transitiv heisst: Aus

a R b

und

b R c

folgt

a R c

.
Es gilt

8 R 4

und es gilt

4 R 2

und es gilt

8 R 2

. Insofern wäre das ein Beispiel, für welches die vom Begriff der Transitivität beschreibene Folgerung zutrifft. Aber: Für Transitivität müsste dies für *alle*

a, b, c

gelten.
Umgekehrt reicht in der Tat ein einziges Gegenbeispiel,

d . h

. die Angabe von drei Zahlen

a, b, c

mit

a R b

und

b R c,

aber nicht

a R c

arrow30

17:36 Uhr, 28.11.2009

so wie ggt(5,10)

> 1

ggt(10,2)> 1 ggt(5,2) ???

Blaub33r3 aktiv_icon

02:05 Uhr, 29.11.2009

Achso, okay.. das Beispiel leuchtet mir ein :-)
Aber wie beginne ich jetzt einen allgemeinen Beweis um die Nicht-Transitivtät meiner Relation aufzuzeigen?

Beweis durch Wiederspruch? ggT(a,b)>1 und ggT(b,c)>1 folgt ggT(a,c)>1 ? Irgendwie find ich, auf dieser Grundlage einen Beweis zu konstruieren, ziemlich schwierig..
Oder würdet ihr das aus dem Ärmel schütteln :-)?

Guten Abend noch!

hagman aktiv_icon

10:34 Uhr, 29.11.2009

"Behauptung:

R

ist nicht transitiv.
Beweis: Es gilt, wie unmittelbar nachzurechnen ist, ggT(2,6)=2, ggT(6,3)=3, ggT(2,3)=1, somit zwar

2 R 6

und

6 R 3,

nicht jedoch

2 R 3

. Wäre

R

transitiv, müsste hingegen auch

2 R 3

gelten.

□

Blaub33r3 aktiv_icon

11:51 Uhr, 29.11.2009

Danke schön, was meinst du mit unmittelbar nachrechnen? Soll man das nicht allgemein zeigen oder reicht ein einfaches Zahlenbeispiel wie deines?

Grüße

arrow30

11:56 Uhr, 29.11.2009

um eine Behauptung zu widersprechen widerlegen reicht dir ein kleines Gegenbeispiel , du schreibst einfach hin : die Relation

R

ist nicht Trans. da sonst ggt(5,10

) = 5 > 1

und ggT(10,2)=

2 > 1

aber ggT(5,2)=1

Blaub33r3 aktiv_icon

12:48 Uhr, 29.11.2009

Ihr seit echt Helden :-) Danke Schön.

Aber wieso meintest du letzte mal:

"
hier reicht es nicht nur ein paar Zahlen zu geben musst du schon allgemein zeigen für

n

,m≥2
ggt(n,m)>1 ⇔ es gibt ein

d > 1

mit

d | n

und d|m⇔n=d⋅k1 und m=d⋅k2 mit k1,k2∈ℕ
ggt(m,x)>1 ⇔ es gibt ein

d 1 > 1

mit

d 1 | m

und d1|x⇔m=d1⋅k3 und x=d1⋅k4
daraus musst du einiges folgern.
"

Hast du das ernst gemeint?

Grüße :-)

arrow30

19:42 Uhr, 29.11.2009

ach ich dachte am Anfang die wäre doch transitiv :-)

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

687668

686518

	Status: nicht eingeloggt	Noch nicht registriert?