Größter gemeinsamer Teiler ggT < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Status: |
(Frage) beantwortet | Datum: | 09:40 Fr 13.05.2016 | Autor: | HageLie |
Aufgabe | Für alle a, b ∈ N gilt:
ggT(1,a)=1
a|b -> ggT(a,b)=a
Wie lautet der Beweis unter Berücksichtigung Beweisstruktur? |
Meine Voraussetzung wäre also:
Voraussetzung: Für alle a, b ∈ N gilt: ggT(1,a)=1
Behauptung: a|b -> ggT(a,b)=a
Beweis: ..
Ist das von der Struktur so korrekt?
Ich habe eine Beweisidee, mir fällt es allerdings schwer diese mathematisch korrekt aufzuschreiben.
Beweisidee:
ggT(1,a)=1, weil T(1)={1} und T(1)∩T(a)={1}
1 ist in jeder Teilmenge von irgendeinen a. 1 teilt alle Zahlen somit auch in der Schnittmenge beider Mengen. Da in T(1) nur die 1 ist, ist 1 größtes Element der Schnittmenge.
Wie sieht dann der zugehörige Beweis aus?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 10:05 Fr 13.05.2016 | Autor: | fred97 |
> Für alle a, b ∈ N gilt:
> ggT(1,a)=1
> a|b -> ggT(a,b)=a
> Wie lautet der Beweis unter Berücksichtigung
> Beweisstruktur?
> Meine Voraussetzung wäre also:
> Voraussetzung: Für alle a, b ∈ N gilt: ggT(1,a)=1
> Behauptung: a|b -> ggT(a,b)=a
> Beweis: ..
>
> Ist das von der Struktur so korrekt?
Nein. Du sollst zwei Dinge zeigen:
1. für a [mm] \in \IN [/mm] gilt: ggT(1,a)=1
und
2. für a,b [mm] \in \IN [/mm] gilt: a|b -> ggT(a,b)=a.
>
> Ich habe eine Beweisidee, mir fällt es allerdings schwer
> diese mathematisch korrekt aufzuschreiben.
> Beweisidee:
> ggT(1,a)=1, weil T(1)={1} und T(1)∩T(a)={1}
Mit T(1) meinst Du wohl die Menge der Teiler von 1 und mit T(a) die Menge der Teiler von a.
> 1 ist in jeder Teilmenge von irgendeinen a.
damit meinst Du wohl: 1 [mm] \in [/mm] T(a) für jedes a [mm] \in \IN.
[/mm]
> 1 teilt alle
> Zahlen somit auch in der Schnittmenge beider Mengen.
D.h.: $1 [mm] \in [/mm] T(1) [mm] \cap [/mm] T(a)$
Da in
> T(1) nur die 1 ist, ist 1 größtes Element der
> Schnittmenge.
Also: [mm] $\{1\} [/mm] = T(1)=T(1) [mm] \cap [/mm] T(a)$,
und somit ggT(1,a)=1.
>
> Wie sieht dann der zugehörige Beweis aus?
Siehe oben !
FRED
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
|
|
|
|
|
Status: |
(Frage) beantwortet | Datum: | 10:36 Fr 13.05.2016 | Autor: | HageLie |
Dann sieht mein Beweis wie folgt aus:
Voraussetzung: Für alle a, b [mm] \in \IN.
[/mm]
Behauptung: (1) ggT(1,a)=1
(2) a|b [mm] \Rightarrow [/mm] ggT(a,b)=a
Beweis: (1) ggT(1,a)=1
T(1)={1}, T(a)={1}, für jedes a [mm] \in \IN.
[/mm]
[mm] \Rightarrow [/mm] T(1) [mm] \cap [/mm] T(a)={1}
[mm] \Rightarrow [/mm] T(1) [mm] \cap [/mm] T(a)=T(1)={1}
[mm] \Rightarrow [/mm] ggT(1,a)=1 [mm] \Box
[/mm]
(2) ggT(a,b)=a
T(a)={a}, T(b)={a}, für alle a, b [mm] \in \IN.
[/mm]
[mm] \Rightarrow [/mm] T(a) [mm] \cap [/mm] T(b)={a}
[mm] \Rightarrow [/mm] T(a) [mm] \cap [/mm] T(b)=T(a)={a}
[mm] \Rightarrow [/mm] ggT(a,b)=1 [mm] \Box
[/mm]
Wie mache ich aus Beweis (2) eine Folgerung aus a|b?
Sind die Beweise so korrekt aufgeschrieben? Auch mit den Folgerungspfeilen?
|
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 11:02 Fr 13.05.2016 | Autor: | fred97 |
> Dann sieht mein Beweis wie folgt aus:
>
> Voraussetzung: Für alle a, b [mm]\in \IN.[/mm]
Nein. Die Voraussetzung lautet: seien $a,b [mm] \in \IN$
[/mm]
>
> Behauptung: (1) ggT(1,a)=1
> (2) a|b [mm]\Rightarrow[/mm] ggT(a,b)=a
>
> Beweis: (1) ggT(1,a)=1
Warum schreibst Du die Behauptung nochmal hin ????
> T(1)={1},
O.K.
> T(a)={1}, für jedes a [mm]\in \IN.[/mm]
Unsinn ! Es lautet: 1 [mm] \in [/mm] T(a) für jedes a [mm]\in \IN.[/mm]
>
> [mm]\Rightarrow[/mm] T(1) [mm]\cap[/mm] T(a)={1}
> [mm]\Rightarrow[/mm] T(1) [mm]\cap[/mm] T(a)=T(1)={1}
> [mm]\Rightarrow[/mm] ggT(1,a)=1 [mm]\Box[/mm]
O.K.
>
> (2) ggT(a,b)=a
Auch hier schreibst Du die Behauptung nochmal hin !! Warum ???
> T(a)={a}, T(b)={a}, für alle a, b [mm]\in \IN.[/mm]
Das ist doch Unfug ! Im allgemeinen hat a nicht nur den Teiler a. T(a) enthält auf jeden Fall 1 und a.
Statt [mm] T(b)=\{a\} [/mm] muss es lauten: a [mm] \in [/mm] T(b), also a|b (das ist die Voraussetzung in (2) !
>
> [mm]\Rightarrow[/mm] T(a) [mm]\cap[/mm] T(b)={a}
> [mm]\Rightarrow[/mm] T(a) [mm]\cap[/mm] T(b)=T(a)={a}
> [mm]\Rightarrow[/mm] ggT(a,b)=1 [mm]\Box[/mm]
Auch das ist Murks !
Wenn a|b, so ist doch a [mm] \in [/mm] T(a) und a [mm] \in [/mm] T(b). Zu zeigen ist: ggT(a,b)=a.
a ist schon mal ein Teiler von a und b. Zu zeigen ist: es gibt keinen Teiler von a und b , der größer als a ist.
FRED
>
> Wie mache ich aus Beweis (2) eine Folgerung aus a|b?
> Sind die Beweise so korrekt aufgeschrieben? Auch mit den
> Folgerungspfeilen?
>
|
|
|
|
|
Status: |
(Frage) beantwortet | Datum: | 12:13 Fr 13.05.2016 | Autor: | HageLie |
Und noch einmal:
Voraussetzung: Seien a, b [mm] \in \IN.
[/mm]
Behauptung:
(1) ggT(1,a)=1
(2) a|b [mm] \Rightarrow [/mm] ggT(a,b)=a
Beweis:
(1) T(1)={1}, 1 [mm] \in [/mm] T(a) für jedes a [mm] \in \IN
[/mm]
[mm] \Rightarrow [/mm] T(1) [mm] \cap [/mm] T(a)={1}
[mm] \Rightarrow [/mm] T(1) [mm] \cap [/mm] T(a)=T(1)={1}
[mm] \Rightarrow [/mm] ggT(1,a)=1 [mm] \Box
[/mm]
(2) Voraussetzung: a|b indirekter Beweis durch Widerspruch?
a [mm] \in [/mm] T(a), a [mm] \in [/mm] T(b)
Sei a [mm] \in [/mm] T(a) [mm] \cap [/mm] T(b) und a > ggT(a,b)
[mm] \Rightarrow [/mm] a|a [mm] \wedge [/mm] a|b
[mm] \Rightarrow [/mm] a|a+b [mm] \gdw [/mm] a|a (Widerspruch, es gibt keinen gemeinsamen Teiler, der größer als der größte gemeinsame Teiler ist. Da a nicht nur b teilt, sondern auch a, kann a nicht größer als ggT(a,b) sein.
|
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 13:15 Fr 13.05.2016 | Autor: | fred97 |
> Und noch einmal:
>
> Voraussetzung: Seien a, b [mm]\in \IN.[/mm]
>
> Behauptung:
> (1) ggT(1,a)=1
> (2) a|b [mm]\Rightarrow[/mm] ggT(a,b)=a
>
> Beweis:
> (1) T(1)={1}, 1 [mm]\in[/mm] T(a) für jedes a [mm]\in \IN[/mm]
> [mm]\Rightarrow[/mm]
> T(1) [mm]\cap[/mm] T(a)={1}
> [mm]\Rightarrow[/mm] T(1) [mm]\cap[/mm] T(a)=T(1)={1}
> [mm]\Rightarrow[/mm] ggT(1,a)=1 [mm]\Box[/mm]
Das ist O.K.
>
> (2) Voraussetzung: a|b indirekter Beweis durch
> Widerspruch?
???? "indirekter Beweis durch Widerspruch?" gehört doch nicht zur Voraussetzung !!!
> a [mm]\in[/mm] T(a), a [mm]\in[/mm] T(b)
> Sei a [mm]\in[/mm] T(a) [mm]\cap[/mm] T(b)
Was soll das mit "sei ... "
Es ist(!) a [mm]\in[/mm] T(a) [mm]\cap[/mm] T(b), denn a ist trivialerweise Teiler von a und a ist Teiler von b nach Vor.
> und a > ggT(a,b)
Puuuh ! Du bist beratungsresisten !
a > ggT(a,b) hab ich Dir nicht gesagt !
Ich hab Dir gesagt, dass Du Dir überlegen sollst, dass a und b keinen Teiler haben können, der größer als a ist.
> [mm]\Rightarrow[/mm] a|a [mm]\wedge[/mm] a|b
Dieser Implikationspfeil ist völlig daneben ! Dass a ein Teiler von a ist, ist immer so. Dass a ein Teiler von b ist, ist gerade die Vor. !
> [mm]\Rightarrow[/mm] a|a+b [mm]\gdw[/mm] a|a (Widerspruch, es gibt keinen
> gemeinsamen Teiler, der größer als der größte
> gemeinsame Teiler ist. Da a nicht nur b teilt, sondern auch
> a, kann a nicht größer als ggT(a,b) sein.
Nee, nee, da musst Du nochmal ran.
FRED
|
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 15:55 Fr 13.05.2016 | Autor: | M.Rex |
Hallo und
Da dir scheinbar noch nicht klar ist, was genau du zeigen willst, hier mal das ganze in Worten
zu Zuegen ist einerseits:
Für alle natürlichen Zahlen a ist der ggT von a und 1 die 1.
und zm zweiten.
Ist a ein Teiler von b, so ist der ggT von a und b dann a.
Beide Beweise kannst du recht schnell über die Betrachtung der Teilermengen der beteiligten Zahlen a und b sowie der Schnittmenge dieser Teilermengen führen.
Marius
|
|
|
|
|
Status: |
(Frage) beantwortet | Datum: | 10:36 Mi 18.05.2016 | Autor: | HageLie |
Ich komme mit Beweis (2) leider immer noch nicht weiter. Und habe es jetzt so verstanden, das der Beweis ein indirekter Beweis durch Widerspruch ist?
Also nochmal:
Voraussetzung: Seien a, b [mm] \in \IN [/mm] und a|b
Behauptung: a|b [mm] \Rightarrow [/mm] ggT(a,b)=a
Beweis: a [mm] \in [/mm] T(a), a [mm] \in [/mm] T(b)
[mm] \Rightarrow [/mm] a [mm] \in [/mm] T(a) [mm] \cap [/mm] T(b)
Vielleicht mag mir ja nochmal jemand helfen.
|
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 10:55 Mi 18.05.2016 | Autor: | fred97 |
> Ich komme mit Beweis (2) leider immer noch nicht weiter.
> Und habe es jetzt so verstanden, das der Beweis ein
> indirekter Beweis durch Widerspruch ist?
>
> Also nochmal:
> Voraussetzung: Seien a, b [mm]\in \IN[/mm] und a|b
> Behauptung: a|b [mm]\Rightarrow[/mm] ggT(a,b)=a
> Beweis: a [mm]\in[/mm] T(a), a [mm]\in[/mm] T(b)
> [mm]\Rightarrow[/mm] a [mm]\in[/mm] T(a) [mm]\cap[/mm] T(b)
>
> Vielleicht mag mir ja nochmal jemand helfen.
Eigentlich ist ja schon alles gesagt ....., aber ich mag dennoch.
1. da a|b, ist a Teiler von b.
2. trivial ist: a ist ein Teiler von a
Damit haben wir: a ist Teiler von a und b.
3. ggT(a,b) ist ebenfalls ein Teiler von a und b , und zwar der größte unter allen gemeinsamen Teilern von a und b.
Damit gilt:
(1) a [mm] \le [/mm] ggT(a,b).
4. Jetzt kommt die Preisfrage (zu gewinnen gibts nix): kann ein Teiler von a echt größer als a sein ?
Wenn ja, .... , nun schaun wir mal ....
Wenn nein, so muss
(2) ggT(a,b) [mm] \le [/mm] a
gelten.
In diesem Fall folgt dann aus (1) und (2): ggT(a,b)=a.
Es geht jetzt also nur noch darum, wie die richtige Antwort auf die obige Preisfrage lautet.
Nimm mal an, c [mm] \in \IN [/mm] wäre ein Teiler von a und es gelte c>a.
Da c Teiler von a ist, gibt es ein n [mm] \in \IN [/mm] mit $a=n*c$. Nun zeige Du, dass das mit der Annahme c>a nun überhaupt nicht zusammenpasst.
FRED
|
|
|
|