Arithmetikbeweis Nr. 3 < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:12 Mi 21.10.2009 | | Autor: | durden88 |
| Aufgabe | a) Seien n [mm] \ge [/mm] 1 eine natürliche Zahl und [mm] a_{1},....,a_{n} [/mm] beliebige natürliche Zahlen. Beweisen sie das eine dieser Zahlen durch n teilbar ist, oder dass Zahlen [mm] a_{i},a_{j} [/mm] existieren, deren Differenz [mm] a_{i}-a_{j} [/mm] durch n teilbar ist.
b) Seien [mm] n\ge [/mm] 1 eine natürliche Zahl und [mm] a_{1},....,a_{n} [/mm] beliebige natürliche Zahlen. Beweisen Sie,dass eine dieser Zahlen durch n teilbar ist oder dass eine Summe irgendwelcher dieser Zahlen existiert, die durch n teilbar ist. (Tipp: Führen sie den beweis dieser Aussage auf Aussage (a) zurück) |
Also, ich weiss nicht wirklich wie ich rangehen soll und worauf es hinausziehlt, wäre super nett wenn da einer mir starthilfe geben könnte.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:39 Mi 21.10.2009 | | Autor: | felixf |
Hallo!
> a) Seien n [mm]\ge[/mm] 1 eine natürliche Zahl und [mm]a_{1},....,a_{n}[/mm]
> beliebige natürliche Zahlen. Beweisen sie das eine dieser
> Zahlen durch n teilbar ist, oder dass Zahlen [mm]a_{i},a_{j}[/mm]
> existieren, deren Differenz [mm]a_{i}-a_{j}[/mm] durch n teilbar
> ist.
Schreibe [mm] $a_i [/mm] = [mm] q_i [/mm] n + [mm] r_i$ [/mm] mit [mm] $q_i, r_i \in \IZ$, [/mm] $0 [mm] \le r_i [/mm] < n$.
Jetzt unterscheide:
a) alle [mm] $r_i$ [/mm] sind verschieden (dann ist eins davon 0);
b) [mm] $r_i [/mm] = [mm] r_j$ [/mm] mit $i [mm] \neq [/mm] j$.
> b) Seien [mm]n\ge[/mm] 1 eine natürliche Zahl und [mm]a_{1},....,a_{n}[/mm]
> beliebige natürliche Zahlen. Beweisen Sie,dass eine dieser
> Zahlen durch n teilbar ist oder dass eine Summe
> irgendwelcher dieser Zahlen existiert, die durch n teilbar
> ist. (Tipp: Führen sie den beweis dieser Aussage auf
> Aussage (a) zurück)
(Es wuerden uebrigens [mm] $\lfloor\log_2 n\rfloor [/mm] + 1$ natuerliche Zahlen ausreichen, damit irgendeine Summe davon durch $n$ teilbar ist.)
Setze [mm] $b_i [/mm] := [mm] \sum_{j=1}^i a_j$. [/mm] Dann wende a) auf [mm] $b_1, \dots, b_n$ [/mm] an.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:49 Do 22.10.2009 | | Autor: | durden88 |
Also kann ich das dann so sagen, wenn ich a=gn+r habe muss ein r= o sein und damit ist auch der wert der division 0? bitte ein paar mehr tipps :)
mit dem zweiten kann ich garnichts anfangen, bitte um mehr tipps für dummies. Danke!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:14 Do 22.10.2009 | | Autor: | leduart |
Hallo
lies doch nochmal genau den beweis von felix durch. Da steht was von 2 moeglichen Faellen!
Wirklich post ganz langsam und sorgfaeltig lesen, sicher machen, dass du jeden satz verstanden hat. Hast du einen nicht verstanden zitier in, und sag, woran du hakst.
Zu 1. wieviel verschidene Reste sind bei Division durch 13 moeglich? wieviel bei Division durch n?
zu2.
wenn ich 2 verschieden Zahlen habe, die beide Rest r lassen und die 2 Zahlen subtrahiere, welchen rest laesst dann die Differenz 44 laesst bei division durch 7 den Rest 2 149 laesst auch den Rest 2
welchen Rest laesst 149-44 ? (ohne die differenz auszurechnen?)
Wenn du die 2 Fragen beantworten kannst solltest du felix post nochmal langsam lesen.
gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:49 Do 22.10.2009 | | Autor: | durden88 |
> Zu 1. wieviel verschidene Reste sind bei Division durch 13
> moeglich? wieviel bei Division durch n?
> zu2.
> wenn ich 2 verschieden Zahlen habe, die beide Rest r lassen
> und die 2 Zahlen subtrahiere, welchen rest laesst dann die
> Differenz 44 laesst bei division durch 7 den Rest 2 149
> laesst auch den Rest 2
> welchen Rest laesst 149-44 ? (ohne die differenz
> auszurechnen?)
> Wenn du die 2 Fragen beantworten kannst solltest du felix
> post nochmal langsam lesen.
> gruss leduart
zu 1: 13 Reste und n reste?
zu2) Also 2 oder?
|
|
|
| |
|
Hallo!
> > Zu 1. wieviel verschidene Reste sind bei Division durch 13
> > moeglich? wieviel bei Division durch n?
> > zu2.
> > wenn ich 2 verschieden Zahlen habe, die beide Rest r lassen
> > und die 2 Zahlen subtrahiere, welchen rest laesst dann die
> > Differenz 44 laesst bei division durch 7 den Rest 2 149
> > laesst auch den Rest 2
> > welchen Rest laesst 149-44 ? (ohne die differenz
> > auszurechnen?)
> > Wenn du die 2 Fragen beantworten kannst solltest du
> felix
> > post nochmal langsam lesen.
> > gruss leduart
>
>
> zu 1: 13 Reste und n reste?
Ja.
> zu2) Also 2 oder?
Nein - was Du leicht hättest selbst herausfinden können, wenn Du im Anschluß an die Überlegung doch gerechnet hättest.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:22 Fr 23.10.2009 | | Autor: | durden88 |
Hallo,
also ich versuche jetzt nochmal mein verständnis auszudrücken und hoffe es ist richtig.
Ich habe verschiedene endliche natürliche Zahlen von [mm] a_{1}...a_{n}. [/mm] Teile ich jetzt mal jedes einzelne durch n habe ich immer einen Rest bis ich [mm] a_{n} [/mm] teile, denn da teile ich sozusagen n/n und das ist 1 oder?
Da ne natürliche Zahl auch 0 sein kann, und wenn 0 der Subtrahend ist kann man den auch durch n teilen?
Das gleiche gilt für die Aufgabe b) mit der Summe.
Ich hab so den Anschein das viele ein bischen genervt sind hier in dem Beweis, bei mir ist aber leider der Funken noch nicht übergesprungen. Deswegen bedanke ich mich schonmal im Vorraus! Danke
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:57 Fr 23.10.2009 | | Autor: | leduart |
Hallo
Nein du hast das falsch verstanden:
du hast n Zahlen, a1 bis aN
jetzt gibts 2 Moeglichkeiten:
a) alle lassen bie division durch n VERSCHIEDENE Reste, da es aber nur n-1 Reste [mm] \ne0 [/mm] gibt laesst eine davon den Rest 0. (das muss natuerlich nicht grad die nte sein, sondern irgendeine.
dann ist man fertig
b) nicht alle Reste sind verschieden, d.h. es gibt mindestens 2 Zahlen mit gleichem Rest r nenn sie [mm] a_i [/mm] und [mm] a_k
[/mm]
dann ist [mm] a_i=n*b+r [/mm] ak=n*c+r, [mm] a,b\in \IN
[/mm]
dann ist ihre Differenz [mm] a_i-a_k=nb-na=n(b-a) [/mm] durch n teilbar.
jetzt klar.
probiers aus: n=4 und die [mm] a_n= [/mm] 2,5,13,7
Reste: 2,1,1,3 also [mm] a_2 [/mm] und [mm] a_3 [/mm] lassen denselben Rest, a2-a3=-8 durch 4 teilbar.
oder [mm] a_n=2,12,13,7 a_2 [/mm] ist durch 4 Teilbar
ums wiklich einzusehen nimm n=7 schreib irgendwelche 7 Zahlen hin und sieh selbst.
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:59 Fr 23.10.2009 | | Autor: | durden88 |
Sehr Sehr gut, vielen dank!
Darf ich fragen unter welcher Kategorie diese Art von Aufgabe fällt?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:51 Fr 23.10.2009 | | Autor: | leduart |
Hallo
Eigenschaften natuerlicher Zahlen.
am ehesten Zahlentheorie, aber darin ganz unten.
Gruss leduart
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:48 Sa 24.10.2009 | | Autor: | durden88 |
> da es aber nur n-1 Reste [mm]\ne0[/mm] gibt laesst eine davon den
> Rest 0. (das muss natuerlich nicht grad die nte sein,
> sondern irgendeine.
Das hab ich nicht ganz verstanden, die b) aber perfekt! danke
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:51 Sa 24.10.2009 | | Autor: | felixf |
Hallo!
> > da es aber nur n-1 Reste [mm]\ne0[/mm] gibt laesst eine davon den
> > Rest 0. (das muss natuerlich nicht grad die nte sein,
> > sondern irgendeine.
>
> Das hab ich nicht ganz verstanden, die b) aber perfekt!
Nochmal in kleinen Schritten:
1) du hast $n$ Reste zwischen 0 und $n - 1$.
2) keine zwei davon sind gleich.
3) du hast also von $n$ verschiedenen Moeglichkeiten alle $n$ vorhanden, insbesondere auch 0.
Wenn dir das nicht hilft: versuche 10 Reste zwischen 0 und 9 aufzuschreiben, die paarweise verschieden sind und von denen keiner 0 ist.
LG Felix
|
|
|
|
