Beweis Teilbarkeit < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:50 Mo 22.10.2012 | | Autor: | MattiJo |
| Aufgabe | Zeige folgende Aussagen für alle n [mm] \in \IN: [/mm]
(a) 24 | [mm] (5^{2n} [/mm] − 1)
(b) Die Zahl [mm] n^4 [/mm] + 4 ist für n > 1 zusammengesetzt. |
Hallo,
ich bin gerade dabei, mich in die Grundlagen der diskreten Mathematik einzuarbeiten. Da ich kein Mathematiker bin, habe ich einmal mehr Probleme mit den Beweisen.
Wie kann ich den Beweis für Aufgabenteil (a) vornehmen? Ist hier vollständige Induktion möglich/erforderlich?
Bei (b) verstehe ich noch nicht einmal, was ich beweisen soll. Was ist damit gemeint, dass die Zahl zusammengesetzt ist?
Vielen Dank schon im Voraus für jede Hilfe!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:26 Mo 22.10.2012 | | Autor: | Marcel |
Hallo,
> Zeige folgende Aussagen für alle n [mm]\in \IN:[/mm]
>
> (a) 24 | [mm](5^{2n}[/mm] − 1)
>
> ich bin gerade dabei, mich in die Grundlagen der diskreten
> Mathematik einzuarbeiten. Da ich kein Mathematiker bin,
> habe ich einmal mehr Probleme mit den Beweisen.
>
> Wie kann ich den Beweis für Aufgabenteil (a) vornehmen?
> Ist hier vollständige Induktion möglich/erforderlich?
möglich, aber nicht notwendig. Es gilt
[mm] $$5^{2n}-1=(5^2)^n-1=25^n-1=(24+1)^n-1\,,$$
[/mm]
und jetzt wende mal die allgemeine binomische Formel
[mm] $$(a+b)^n=\sum_{k=0}^n [/mm] {n [mm] \choose [/mm] k} [mm] a^k b^{n-k}=1+\sum_{\red{k=1}}^n [/mm] {n [mm] \choose [/mm] k} [mm] a^k b^{n-k}$$
[/mm]
an! Beachte dabei, dass hier die Binomialkoeffizienten stets [mm] $\in \IN_0$
[/mm]
liegen!
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 07:51 Di 23.10.2012 | | Autor: | wieschoo |
Eine zusammengesetzte Zahl besitzt mindestens 2 Primfaktoren. Du sollst zeigen, dass [mm] $n^4-4$ [/mm] nicht nur triviale Teiler besitzt.
gruß
wieschoo
|
|
|
| |
|
Hallo MattiJo,
bei b) ist zu zeigen, dass [mm] n^4+4 [/mm] für n>1 keine Primzahl ist.
Schaut man sich mal die Werte für die ersten paar n an, so hat man 5, 20, 85, 260, ...
Bis dahin sieht das ja nett aus, alle sind durch 5 teilbar.
Dann aber kommt 629=17*37.
Wenn man sich noch weitere Werte ansieht, erkennt man schnell, dass [mm] n^4+4 [/mm] immer durch 5 teilbar ist, wenn n nicht durch 5 teilbar ist. Das ist auch leicht zu zeigen.
Wenn n durch 10 teilbar ist, ist [mm] n^4+4 [/mm] immer gerade, also durch 2 teilbar. Auch leicht zu zeigen.
Wenn n aber ein ungerades Vielfaches von 5 ist, also n=5,15,25,35 etc., braucht man offenbar etwas anderes, denn
[mm] 5^4+4=629=17*37
[/mm]
[mm] 15^4+4=50629=197*257
[/mm]
[mm] 25^4+4=390629=577*677
[/mm]
[mm] 35^4+4=1500629=13*89*1297=1157*1297
[/mm]
Tipp: Du kannst [mm] n^4+4 [/mm] allgemein in zwei Faktoren zerlegen, wie die französische Mathematikerin Sophie Germain gezeigt hat, nämlich [mm] n^4+4=(n^2+an+b)(n^2+cn+d).
[/mm]
Finde nun a,b,c,d.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:12 Di 23.10.2012 | | Autor: | reverend |
Hallo nochmal,
wenn Du übrigens die Zerlegung von [mm] n^4+4 [/mm] gefunden hast, brauchst Du die beiden anderen Restklassenbetrachtungen gar nicht mehr. Die Zerlegung ist für alle n gültig, aber für n=1 wird ein Faktor 1.
Du kannst auch gleich für [mm] n^4+4k^4 [/mm] die allgemeine Zerlegung in zwei Faktoren suchen. Dann weißt Du, dass eine solche Zahl für k*n>1 immer eine zusammengesetzte ist.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:04 Do 25.10.2012 | | Autor: | MattiJo |
Gibt es eine algorithmische Vorgehensweise für diese Sophie-Germain-Zerlegung oder geht das nur mit "scharfem Hinsehen"? Mir fällt momentan nichts ein, was mir weiterhilft...
|
|
|
| |
|
Hallo MattiJo,
einfach mal ausrechnen. 
[mm] (n^2+an+b)(n^2+cn+d)=n^4+(a+c)n^3+(ac+b+d)n^2+(ad+bc)n+bd\overset{!}{=}n^4+4
[/mm]
Koeffizientenvergleich:
a+c=0
ac+b+d=0
ad+bc=0
bd=4
Das ist zwar nicht linear, aber lösbar.
Außerdem kommt Dir zugute, dass alle Koeffizienten ganzzahlig sein müssen. Schließlich geht es hier um die Zerlegung einer natürlichen Zahl in ganzzahlige Faktoren, also muss sowohl [mm] (n^2+an+b) [/mm] als auch [mm] (n^2+cn+d) [/mm] für alle n jeweils ganzzahlig sein.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:34 Di 23.10.2012 | | Autor: | fred97 |
Zu a)
Für q [mm] \ne [/mm] 1 ist
[mm] \bruch{q^n-1}{q-1}=1+q+q^2+...+q^{n-1}.
[/mm]
Nun schau Dir das mal mit q=25 an.
FRED
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:22 Di 23.10.2012 | | Autor: | Marcel |
Hallo Fred,
> Zu a)
>
> Für q [mm]\ne[/mm] 1 ist
>
> [mm]\bruch{q^n-1}{q-1}=1+q+q^2+...+q^{n-1}.[/mm]
>
> Nun schau Dir das mal mit q=25 an.
ja stimmt, die geometrische Summenformel. Witzig:
Wegen
[mm] $$\frac{q^n-1}{q-1}=\frac{((q-1)+1)^n-1}{q-1}=\sum_{k=0}^{n-1} [/mm] {n [mm] \choose [/mm] k+1} [mm] (q-1)^k$$
[/mm]
folgt dann auch
[mm] $$\sum_{k=1}^n q^k=\sum_{m=0}^{n-1}{n \choose m+1} (q-1)^m\,.$$
[/mm]
Ich seh's gerade nicht: Hat das Ding' 'nen Namen?
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:47 Do 25.10.2012 | | Autor: | fred97 |
> Hallo Fred,
>
> > Zu a)
> >
> > Für q [mm]\ne[/mm] 1 ist
> >
> > [mm]\bruch{q^n-1}{q-1}=1+q+q^2+...+q^{n-1}.[/mm]
> >
> > Nun schau Dir das mal mit q=25 an.
>
> ja stimmt, die geometrische Summenformel. Witzig:
> Wegen
>
> [mm]\frac{q^n-1}{q-1}=\frac{((q-1)+1)^n-1}{q-1}=\sum_{k=0}^{n-1} {n \choose k+1} (q-1)^k[/mm]
>
> folgt dann auch
> [mm]\sum_{k=1}^n q^k=\sum_{m=0}^{n-1}{n \choose m+1} (q-1)^m\,.[/mm]
>
> Ich seh's gerade nicht: Hat das Ding' 'nen Namen?
Das kannte ich auch noch nicht. Nennen wirs "Marcelsche Gleichung"
FRED
>
> Gruß,
> Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:42 Do 25.10.2012 | | Autor: | MattiJo |
Vielen Dank bisher!
Wenn ich also nun die geometrische Summenformel anwende, komme ich zu
[mm] \bruch{25^n - 1}{25-1} [/mm] = [mm] \bruch{25^n - 1}{24} [/mm] = 1 + 25 + [mm] 25^2 [/mm] + ... + [mm] 25^{n-1} [/mm] = [mm] \summe_{i=0}^{n-1} 25^i
[/mm]
Das würde dann bedeuten, dass für n>1 ein weiterer Teiler neben den trivialen Teilern existieren würde?
Wie könnte ich das mathematisch korrekt formulieren?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:47 Do 25.10.2012 | | Autor: | fred97 |
> Vielen Dank bisher!
>
> Wenn ich also nun die geometrische Summenformel anwende,
> komme ich zu
>
> [mm]\bruch{25^n - 1}{25-1}[/mm] = [mm]\bruch{25^n - 1}{24}[/mm] = 1 + 25 +
> [mm]25^2[/mm] + ... + [mm]25^{n-1}[/mm] = [mm]\summe_{i=0}^{n-1} 25^i[/mm]
>
> Das würde dann bedeuten, dass für n>1 ein weiterer Teiler
> neben den trivialen Teilern existieren würde?
> Wie könnte ich das mathematisch korrekt formulieren?
Hä ? Du sollst doch zeigen, dass [mm] 25^n-1 [/mm] teilbar ist durch 24.
Setzt man [mm] k:=\summe_{i=0}^{n-1} 25^i, [/mm] so ist k [mm] \in \IN [/mm] und
[mm] \bruch{25^n - 1}{24}=k
[/mm]
FRED
>
|
|
|
|
