Aussage für teilerfremde a,b < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:26 So 17.03.2013 | | Autor: | Marcel |
| Aufgabe | Aussage: Sind $a < b$ natürliche Zahlen, die teilerfremd sind, so gilt:
Für $k [mm] \in \{1,...,a-1\}$ [/mm] gilt $a [mm] \not| [/mm] (k [mm] \cdot [/mm] b).$ |
Hallo zusammen,
weil ich mir selbst elementar beweisen will, dass [mm] $\IZ$ [/mm] ein Hauptidealring
ist, wollte ich mir zunächst beweisen, dass für natürliche Zahlen $a < [mm] b\,,$
[/mm]
die zudem teilerfremd sind, gilt, dass
[mm] $$a\IZ+b\IZ=\IZ$$
[/mm]
gilt.
Bei dem Versuch, dies zu beweisen, kam ich zu der Idee, die obige Aussage
zu beweisen - mithilfe dieser Aussage würde ich einsehen, dass die Zahlen
[mm] $b_j:=j*b$ [/mm] für $j=0,1,...,a-1$ bei Division durch [mm] $a\,$ [/mm] Reste lassen, die die
Zahlen $0,...,a-1$ alle erfassen. Daraus kann ich dann folgern, dass
[mm] $a\IZ+b\IZ \subseteq \IZ$ [/mm] gilt.
Ich wollte nun die obige Aussage beweisen, und das möglichst elementar.
Ich sehe aber gerade nicht, wie's weitergeht, weil ich auch nicht sehe, wo
ich die Teilerfremdheit nun benutzen kann:
Seien also $a,b [mm] \in \IN$ [/mm] mit $0 < a < b$ teilerfremd. Insbesondere gilt also
$a [mm] \not| [/mm] b.$ Es existiert also ein $q [mm] \in \IN$ [/mm] und ein $r [mm] \in \{1,...,a-1\}$ [/mm] so,
dass
[mm] $$b=qa+r\,.$$
[/mm]
Für $k [mm] \in \{1,...,a-1\}$ [/mm] folgt
[mm] $$kb=kqa+kr\,.$$
[/mm]
Angenommen, das [mm] $k\,$ [/mm] wäre doch so, dass $a | [mm] (kb)\,.$ [/mm] Dann muss auch
$a | (kr)$ gelten. Es gibt also ein $c [mm] \in \IN_0$ [/mm] mit
[mm] $$kr=ca\,.$$
[/mm]
Kann man das irgendwie (elementar) zu Ende denken? Ich sehe vor allem
jetzt nicht mehr, wie da noch die Teilerfremdheit von [mm] $a,b\,$ [/mm] mit ins Spiel
kommt...
Gruß,
Marcel
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:47 So 17.03.2013 | | Autor: | hippias |
Das ist schwierig zu beantworten: etwas hilfreich waere zu wissen, was Du als elementar voraussetzt.
Ich persoehnlich finde es ganz elementar zu zeigen, dass [mm] $\IZ$ [/mm] ein Hauptidealring ist, indem von der kleinste natuerliche Zahl in einen Ideal [mm] $\neq [/mm] 0$ gezeigt wird, dass es alle Elemente des Ideals teilt.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:56 So 17.03.2013 | | Autor: | Marcel |
Hallo,
> Das ist schwierig zu beantworten: etwas hilfreich waere zu
> wissen, was Du als elementar voraussetzt.
elementar bedeutet, dass ich erstmal rein per Definitionem, die man
sogar in der Schule benutzen würde, vorgehen will. Ich habe gerade
etwa nachgelesen, dass ich meine Behauptung recht schnell mit dem
Lemma von Bézout beweisen könnte. Das ist aber nicht mehr elementar,
da da schon der erweiterte euklidische Algorithmus verwendet wird.
Anders könnte man auch sagen: Ich habe das Buch "Elementare und
algebraische Zahlentheorie" von Müller-Stach und Piontkowski - auf Seite
9 steht einfach die Behauptung, dass [mm] $\IZ$ [/mm] ein Hauptidealring ist. Und ich
möchte dies an dieser Stelle beweisen, nur mit dem bis dahin im Buch
zur Verfügung gestellten Wissen.
> Ich persoehnlich finde es ganz elementar zu zeigen, dass
> [mm]\IZ[/mm] ein Hauptidealring ist, indem von der kleinste
> natuerliche Zahl in einen Ideal [mm]\neq 0[/mm] gezeigt wird, dass
> es alle Elemente des Ideals teilt.
Mir geht's momentan tatsächlich mehr um die Aussage, die ich in der Frage
formuliert habe. D.h.:
Sind $a,b$ teilerfremde natürliche Zahlen mit $a < [mm] b\,,$ [/mm] so folgt
$$a [mm] \not| [/mm] (k*b)$$
für jedes $k [mm] \in \{1,...,a-1\}\,.$ [/mm] Die Aussage erscheint mir plausibel und mit
dem Lemma von Bézout scheint sie auch schnell zu folgen. Aber kann man
sie auch ohne das Lemma beweisen? Denn das Lemma finde ich nun nicht
gerade elementar, zumal es auch im Buch an der Stelle nicht zur Verfügung
steht...
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:09 So 17.03.2013 | | Autor: | hippias |
Sei [mm] $a\in \IN$, [/mm] $a>1$. Ist [mm] $b\in \IN$ [/mm] teilerfremd zu $a$, dann gilt fuer alle [mm] $k\in \IN$: [/mm] Wenn [mm] $1\leq [/mm] k< a$, so ist [mm] $a\not \vert [/mm] kb$.
Beweis (mittels Induktion und Division mit Rest): Sei $a$ minimales Gegenbeispiel und [mm] seien$b\in \IN$ [/mm] teilerfremd zu $a$ und [mm] $1\leq [/mm] k< a$ so, dass [mm] $a\vert [/mm] kb$. Sei $b= qa+r$, [mm] $0\leq [/mm] r< a$. Dann ist $r$ teilerfremd zu $a$ und wegen [mm] $a\vert [/mm] kb$ ist auch [mm] $a\vert [/mm] kr$. Wegen $k<a$ ist $r>1$.
Sei nun [mm] $l\in \IN$ [/mm] mit $la= kr$. Wegen $a>k$ ist $l<r$, sodass das Tripel $(r,a,l)$ die Voraussetzung erfuellt, d.h. $r>1$, $a$ teilerfremd zu $r$ und [mm] $1\leq [/mm] l<r$. Wegen der Minimalitaet von $a$ ist dann aber [mm] $r\not \vert [/mm] la$, im Widerspruch zu obiger Gleichung $la= kr$.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:25 So 17.03.2013 | | Autor: | Marcel |
Hallo Hippias,
> Sei [mm]a\in \IN[/mm], [mm]a>1[/mm]. Ist [mm]b\in \IN[/mm] teilerfremd zu [mm]a[/mm], dann gilt
> fuer alle [mm]k\in \IN[/mm]: Wenn [mm]1\leq k< a[/mm], so ist [mm]a\not \vert kb[/mm].
>
> Beweis (mittels Induktion und Division mit Rest): Sei [mm]a[/mm]
> minimales Gegenbeispiel und seien[mm]b\in \IN[/mm] teilerfremd zu [mm]a[/mm]
> und [mm]1\leq k< a[/mm] so, dass [mm]a\vert kb[/mm]. Sei [mm]b= qa+r[/mm], [mm]0\leq r< a[/mm].
> Dann ist [mm]r[/mm] teilerfremd zu [mm]a[/mm] und wegen [mm]a\vert kb[/mm] ist auch
> [mm]a\vert kr[/mm]. Wegen [mm]k1[/mm].
> Sei nun [mm]l\in \IN[/mm] mit [mm]la= kr[/mm]. Wegen [mm]a>k[/mm] ist [mm]l
> Tripel [mm](r,a,l)[/mm] die Voraussetzung erfuellt, d.h. [mm]r>1[/mm], [mm]a[/mm]
> teilerfremd zu [mm]r[/mm] und [mm]1\leq l
> [mm]a[/mm] ist dann aber [mm]r\not \vert la[/mm], im Widerspruch zu obiger
> Gleichung [mm]la= kr[/mm].
Danke, ich gebe aber zu, dass ich das noch nicht so ganz verstanden habe.
Ich druck'mir das mal aus und gehe es nochmal durch. Aber nebenbei:
Benutzt Du auch $a < [mm] b\,$? [/mm]
Edit:
Und was ich gerade nicht verstehe, ist, wieso
eigentlich [mm] $a\,$ [/mm] teilerfremd zu [mm] $r\,$ [/mm] sein muss...
Ich glaube, dass ich mir das fettgedruckte nun doch selbst erklärt habe:
Hätten [mm] $r\,$ [/mm] und [mm] $a\,$ [/mm] einen gemeinsamen Teiler, so zeigt die Darstellung
$$b=qa+r$$
sofort, dass dieser gemeinsame Teiler auch ein Teilfer von [mm] $b\,$ [/mm] sein
müsste, im Widerspruch zur Teilerfremdheit von [mm] $a\,$ [/mm] und [mm] $b\,.$
[/mm]
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:37 So 17.03.2013 | | Autor: | Marcel |
Hi Hippias,
ich denke, ich habe den Beweis nun so komplett verstanden. Ich sehe zwar
nicht wirklich, dass das ein Induktionsbeweis ist, aber der Widerspruch ist
mir klar. 
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:47 So 17.03.2013 | | Autor: | hippias |
Nein, $a<b$ benutze ich nicht. Die Induktion sollte in der Bemerkung "sei $a$ minimales Gegenbeispiel" angedeutet werden: Angenommen die Behauptung ist falsch; dann ist die Menge der Gegenbeispiele nicht leer und besitzt nach dem Induktionsaxiom ein minimales Element. Aber der Beweis muesste auch ohne groessere Schwierigkeiten direkt zu fuehren sein.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:20 So 17.03.2013 | | Autor: | Marcel |
Hi Hippias,
> Nein, [mm]a
ich hab's mir jetzt zusammengeschrieben, wobei ich diese Voraussetzung
mit reingeschrieben habe. Aber anscheinend kann auf sie verzichtet
werden.
> Die Induktion sollte in der
> Bemerkung "sei [mm]a[/mm] minimales Gegenbeispiel" angedeutet
> werden: Angenommen die Behauptung ist falsch; dann ist die
> Menge der Gegenbeispiele nicht leer und besitzt nach dem
> Induktionsaxiom ein minimales Element.
Achso: Das ganze kenne ich unter dem Namen Wohlordnungsprinzip,
vgl. ![[]](/images/popup.gif) Satz 3.20.
Ich kenne das nicht als Induktionsaxiom. Aber mir war schon klar, dass Du
das benutzt hast - es ist nur so elementar (in der Analysis), dass ich es
nicht wirklich für erwähnenswert hielt. So, wie man dort ja auch nicht
ständig die Dreiecksgleichung erwähnt. Aber Du hast schon recht: Ich
wollte den Beweis ja möglichst elementar, von daher hat das auch nicht
geschadet, sowas zu erwähnen. In meinem eigenen Aufschrieb hab' ich mir
das aber erspart. 
> Aber der Beweis
> muesste auch ohne groessere Schwierigkeiten direkt zu
> fuehren sein.
Das weiß ich jetzt nicht. In Deinem Beweis benutzt Du ja eben die
Minimalitätseigenschaft, um einen Widerspruch zu erzeugen. Ich sehe
gerade nicht, wie man daraus einen direkten Beweis basteln kann. Ich
glaube, der Knackpunkt war aber vor allem, auch zu sehen, dass aus der
Teilerfremdheit von [mm] $a\,$ [/mm] und [mm] $b\,$ [/mm] auch die Teilerfremdheit des Restes zu
[mm] $a\,$ [/mm] folgt. Die Teilerfremdheit geht hier also ein, und mich hätte es auch
gewundert, wäre dem nicht so. Denn die Aussage ist für nicht teilerfremde
[mm] $a,b\,$ [/mm] falsch, wie man sich leicht mit einem Beispiel klarmachen kann.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:17 So 17.03.2013 | | Autor: | Marcel |
Hi nochmal,
> Das ist schwierig zu beantworten: etwas hilfreich waere zu
> wissen, was Du als elementar voraussetzt.
>
> Ich persoehnlich finde es ganz elementar zu zeigen, dass
> [mm]\IZ[/mm] ein Hauptidealring ist, indem von der kleinste
> natuerliche Zahl in einen Ideal [mm]\neq 0[/mm] gezeigt wird, dass
> es alle Elemente des Ideals teilt.
übrigens dennoch Danke für die Alternative Beweismethode. Mir ist nämlich
dadurch eingefallen, dass in dem Buch ja der Satz, dass jeder euklidische
Ring auch Hauptidealring ist, bewiesen wird. Dein Hinweis hat mich einfach
an den Beweis dieses Satzes erinnert. Damit ist an der Stelle im Buch dann
wenigstens dennoch direkt klar, dass [mm] $\IZ$ [/mm] Hauptidealring ist, denn mit
$N(z):=|z|$ ist [mm] $\IZ$ [/mm] ein euklidischer Ring!
Hat mir also sehr weitergeholfen. ![[ok]](/images/smileys/ok.gif "[ok]")
Dennoch frage ich mich, ob ich meine obigen Überlegungen nicht
elementar zu Ende führen kann?
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:14 So 17.03.2013 | | Autor: | Marcel |
Hallo Sax,
danke, aber:
> Hi,
>
> es handelt sich um das
> Euklidische Lemma
das ist für mich an der Stelle des Buches nicht elementar - außerdem
kommen wir ja wieder zum erweiterten euklidischen Algorithmus bzw.
dem Lemma von Bézout. Kann man meine Gedanken nicht irgendwie noch
zu Ende denken? Oder wird man "zwangsläufig" nicht um solche Hilfsmittel
herumkommen?
Gruß,
Marcel
|
|
|
|
