Teilbarkeit zeigen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:53 So 04.07.2010 | | Autor: | itse |
| Aufgabe | Zeigen Sie für alle n [mm] \in \IN:
[/mm]
37 | [mm] 1000^n [/mm] -1 |
Hallo,
ich habe mir das ganze nun so gedacht:
37 | [mm] 1000^n [/mm] - 1
kann man auch so schreiben
[mm] 1000^n [/mm] - 1 = 0 mod 37
[mm] 1000^n [/mm] = 1 mod 37
Da 37 eine Primzahl ist gilt für alle x [mm] \in \IN: [/mm] ggT(37, x) = 1
In unserem Fall ist x = [mm] 1000^n: [/mm] ggT(37, [mm] 1000^n) [/mm] = 1.
Die einzige Einschränkung die noch bleibt ist, das x aus den natürlichen Zahlen sein muss, da
jedoch 1000 [mm] \in \IN [/mm] ist auch jede Potenz von 1000 in [mm] \IN.
[/mm]
Wäre dies so in Ordnung?
Gruß
itse
|
|
| |
|
Hiho,
> Da 37 eine Primzahl ist gilt für alle x [mm]\in \IN:[/mm] ggT(37,x) = 1
Wie kommst du darauf? Versuchs mal mit $x = 37, x = 74, [mm] \ldots$
[/mm]
Insofern ist die Aussage falsch.
Versuchs mal mit Vollständiger Induktion.
Und als Tip: Nicht vergessen, dass $1000 - 1000 = 0$ ist 
MFG,
Gono.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:43 So 04.07.2010 | | Autor: | itse |
Hallo,
danke für die Antwort.
Okay, ich hab die Vielfachen von 37 vergessen.
Somit müsste ich nur noch zeigen, das [mm] 1000^n \ne [/mm] 37d für n, d [mm] \in \IN [/mm] ist?
zeige: [mm] 1000^n \ne [/mm] 37d für n, d [mm] \in \IN
[/mm]
Dies ist war da 1000 gerade ist und jede Pozenz davon auch. 37 ist eine Primzahl und ungerade, jedes Vielfache davon ist auch wieder ungerade.
Es gibt keine Zahl die gleichermaßen gerade und ungerade ist -> gerade [mm] \ne [/mm] ungerade
Deswegen kann [mm] 1000^n [/mm] niemals gleich 37d für n, d [mm] \in \IN [/mm] sein.
-> Für alle n [mm] \in \IN [/mm] gilt: ggT(37, [mm] 1000^n) [/mm] = 1
Wäre es nun so richtig begründet?
Wie kann ich dies per vollständiger Induktion zeigen?
Gruß
itse
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:55 So 04.07.2010 | | Autor: | M.Rex |
Hallo
> Hallo,
>
> danke für die Antwort.
>
> Okay, ich hab die Vielfachen von 37 vergessen.
>
> Somit müsste ich nur noch zeigen, das [mm]1000^n \ne[/mm] 37d für
> n, d [mm]\in \IN[/mm] ist?
>
> zeige: [mm]1000^n \ne[/mm] 37d für n, d [mm]\in \IN[/mm]
>
> Dies ist wahr da 1000 gerade ist und jede Pozenz davon auch.
> 37 ist eine Primzahl und ungerade, jedes Vielfache davon
> ist auch wieder ungerade.
Nein 2*37=74 ist Gerade.
>
> Es gibt keine Zahl die gleichermaßen gerade und ungerade
> ist -> gerade [mm]\ne[/mm] ungerade
>
> Deswegen kann [mm]1000^n[/mm] niemals gleich 37d für n, d [mm]\in \IN[/mm]
> sein.
>
> -> Für alle n [mm]\in \IN[/mm] gilt: ggT(37, [mm]1000^n)[/mm] = 1
>
> Wäre es nun so richtig begründet?
Nein
>
> Wie kann ich dies per vollständiger Induktion zeigen?
1. Induktionsanfang:
Weise nach, dass [mm] 37|1000^{\red{1}}-1
[/mm]
2. Zeige, unter Annahme der Ind.-voraussetzung (37 ist ein Teiler von [mm] 1000^{n}-1), [/mm] dass 37 dann auch ein teiler von [mm] 1000^{\red{n+1}}-1 [/mm] ist.
Ein Tipp hat dir Gonozal ja schon gegeben.
Das ganze ist ein klassischer Fall eines  Induktionsbeweises. Beispiel 2 des Links ist ein Induktionsbeweis über die Teilbarkeitsaussagen.
>
> Gruß
> itse
Marius
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:45 So 04.07.2010 | | Autor: | itse |
Hallo,
dann per Induktion 37 | [mm] 1000^n [/mm] - 1:
für n = 1: [mm] 1000^1 [/mm] - 1 = 999 dies ist durch 37 teilbar
Nun der Induktionsschritt:
n -> n+1 : 37 | [mm] 1000^{n+1} [/mm] - 1
[mm] 1000^{n+1} [/mm] - 1 = 1000 [mm] \cdot{} 1000^n [/mm] -1
Für den hinteren gilt nach Induktionsvoraussetzung, das 37 | [mm] 1000^n [/mm] -1. Und ein Vielfaches davon ist auch durch 37 teilbar.
Fertig ? Ich hab allerdings nicht gesehen, wo ich den Tip verwenden kann (1000 - 1000) = 0.
Gruß
itse
|
|
|
| |
|
Huhu,
> [mm]1000^{n+1}[/mm] - 1 = 1000 [mm]\cdot{} 1000^n[/mm] -1
>
> Für den hinteren gilt nach Induktionsvoraussetzung, das 37
> | [mm]1000^n[/mm] -1.
Stimmt, [mm] $1000^n [/mm] - 1 $ ist nach IV durch 37 teilbar.
Da steht aber [mm] $1000*1000^n [/mm] - 1$ was eine ganz andere Zahl ist als [mm] $1000^n [/mm] - 1$, insofern kannst du deine IV noch gar nicht anwenden!
Gegenbeispiel: $23 = 24-1$ ist offensichtlich durch 23 Teilbar, aber $23999 = 1000*24 - 1$ ist es nicht!
Denn: Wann teilt eine Zahl eine Differenz bzw Summe?
Um so begründen zu können wie du es willst, müsste da [mm] $1000(1000^n [/mm] - 1)$ stehen, tut es aber noch nicht. Warum müsste das da stehen? Wann teilt eine Zahl ein Produkt?
Um eine 1000 ausklammern zu können, wirst du wohl den Tip verwenden müssen.
MFG,
Gono.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:25 So 04.07.2010 | | Autor: | itse |
Hallo,
> Huhu,
>
> > [mm]1000^{n+1}[/mm] - 1 = 1000 [mm]\cdot{} 1000^n[/mm] -1
> >
> > Für den hinteren gilt nach Induktionsvoraussetzung, das 37
> > | [mm]1000^n[/mm] -1.
>
> Stimmt, [mm]1000^n - 1[/mm] ist nach IV durch 37 teilbar.
> Da steht aber [mm]1000*1000^n - 1[/mm] was eine ganz andere Zahl ist
> als [mm]1000^n - 1[/mm], insofern kannst du deine IV noch gar nicht
> anwenden!
>
> Gegenbeispiel: [mm]23 = 24-1[/mm] ist offensichtlich durch 23
> Teilbar, aber [mm]23999 = 1000*24 - 1[/mm] ist es nicht!
>
> Denn: Wann teilt eine Zahl eine Differenz bzw Summe?
Zahl teilt eine Differnenz bzw. Summe, wenn Sie ein Vielfaches davon ist.
> Um so begründen zu können wie du es willst, müsste da
> [mm]1000(1000^n - 1)[/mm] stehen, tut es aber noch nicht. Warum
> müsste das da stehen? Wann teilt eine Zahl ein Produkt?
Wenn die Zahl ein Vielfaches, einer der beiden Faktoren ist.
> Um eine 1000 ausklammern zu können, wirst du wohl den Tip
> verwenden müssen.
Leider sehe ich es aber nicht, wie es umformen muss.
Bisher steht folgendes da: 1000 [mm] \cdot{} 1000^n [/mm] -1 = 1000 [mm] \cdot{} 1000^n [/mm] -1 + 1000 - 1000 ?
Gruß
itse
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:32 So 04.07.2010 | | Autor: | Loddar |
Hallo itse!
> > Denn: Wann teilt eine Zahl eine Differenz bzw Summe?
>
> Zahl teilt eine Differnenz bzw. Summe, wenn Sie ein
> Vielfaches davon ist.
Genau, und as ist hier nicht der Fall, da [mm] $1000*1000^n-1 [/mm] \ [mm] \not= [/mm] \ [mm] 1000*\left(1000^n-1\right)$ [/mm] .
> Leider sehe ich es aber nicht, wie es umformen muss.
>
> Bisher steht folgendes da:
> 1000 [mm]\cdot{} 1000^n[/mm] -1 = 1000 [mm]\cdot{} 1000^n[/mm] -1 + 1000 - 1000 ?
Es gilt:
[mm] $$1000*1000^n-1 [/mm] \ = \ [mm] 1000*1000^n-1000+1000-1 [/mm] \ = \ [mm] 1000*(1000^n-1)+999$$
[/mm]
Und nun untersuche beide Summanden separat. Sind diese jeweils durch 37 teilbar?
Gruß
Loddar
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:03 So 04.07.2010 | | Autor: | abakus |
> Hallo,
>
> dann per Induktion 37 | [mm]1000^n[/mm] - 1:
Hallo,
Induktion ist nicht erforderlich. Es genügt die Kenntnis des Satzes
[mm] a\equiv [/mm] b mod m [mm] \Rightarrow a^n\equiv b^n [/mm] mod m
Aus [mm] 1000\equiv [/mm] 1 mod 37 folgt somit [mm] 1000^n\equiv 1^n \equiv [/mm] 1 mod 37.
Gruß Abakus
>
> für n = 1: [mm]1000^1[/mm] - 1 = 999 dies ist durch 37 teilbar
>
> Nun der Induktionsschritt:
>
> n -> n+1 : 37 | [mm]1000^{n+1}[/mm] - 1
>
> [mm]1000^{n+1}[/mm] - 1 = 1000 [mm]\cdot{} 1000^n[/mm] -1
>
> Für den hinteren gilt nach Induktionsvoraussetzung, das 37
> | [mm]1000^n[/mm] -1. Und ein Vielfaches davon ist auch durch 37
> teilbar.
>
> Fertig ? Ich hab allerdings nicht gesehen, wo ich den Tip
> verwenden kann (1000 - 1000) = 0.
>
> Gruß
> itse
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:37 So 04.07.2010 | | Autor: | Marcel |
Hallo,
> Zeigen Sie für alle n [mm]\in \IN:[/mm]
>
> 37 | [mm]1000^n[/mm] -1
wegen [mm] $$\frac{1000^n-1}{37}=\frac{(\underbrace{999}_{=27*37}+1)^n-1}{37}=\frac{\big(\sum_{k=0}^n {n \choose k}*\overbrace{999^k}^{=27^k*37^k}\big)-1}{37}=\sum_{k=1}^n\underbrace{{n \choose k}27^k*37^{k-1}}_{\in \IN}$$
[/mm]
ist das unmittelbar klar.
Beste Grüße,
Marcel
|
|
|
|
