Induktionsbeweis teilbar p < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:22 So 05.10.2008 | | Autor: | Giorda_N |
| Aufgabe | | Füe eine beliebige Primzahl p gilt: p teilt [mm] (n^p [/mm] -1) mit n [mm] \ge [/mm] 1 beliebig. |
Ich komme einfach nicht weiter hat jemand einen tipp?
also induktionsschritt:
[mm] (n^p [/mm] -n) = p * k mit k [mm] \in \IN
[/mm]
[mm] ((n+1)^p [/mm] - (n+1)) = p * m mit m [mm] \in \IN
[/mm]
also
[mm] ((n+1)^p [/mm] - (n+1))
= [mm] \summe_{i=0}^{p}\vektor{p \\ i} n^i [/mm] - (n+1)
= [mm] n^p \summe_{i=0}^{p-1}\vektor{p \\ i} n^i [/mm] - n - 1
= [mm] n^p [/mm] - n + [mm] \summe_{i=0}^{p-1}\vektor{p \\ i} n^i [/mm] - 1
= p * k + [mm] \summe_{i=0}^{p-1}\vektor{p \\ i} n^i [/mm] - 1
jetzt wäre noch zu zeigen wie [mm] \summe_{i=0}^{p-1}\vektor{p \\ i} n^i [/mm] - 1 durch p teilbar wäre.
Jemand eine idee?
Danke
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:33 So 05.10.2008 | | Autor: | pelzig |
Die Behauptung ist falsch für $p=3$ und $n=2$.
Gruß, Robert
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:36 So 05.10.2008 | | Autor: | Giorda_N |
mhm und was soll ich jetzt damit anfangen? :-(
muss das bis dienstag per induktion beweisen ![[keineahnung]](/images/smileys/keineahnung.gif "[keineahnung]")
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:40 So 05.10.2008 | | Autor: | pelzig |
> mhm und was soll ich jetzt damit anfangen? :-(
> muss das bis dienstag per induktion beweisen
Du kannst eine falsche Aussage nicht beweisen. Wahrscheinlich hast du die Aufgabe falsch abgeschrieben.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:44 So 05.10.2008 | | Autor: | Disap |
> > mhm und was soll ich jetzt damit anfangen? :-(
> > muss das bis dienstag per induktion beweisen
> Du kannst eine falsche Aussage nicht beweisen.
> Wahrscheinlich hast du die Aufgabe falsch abgeschrieben.
Auf welche Aussage hast du dich eigentlich bezogen, auf ihr
p teilt $ [mm] (n^p [/mm] $ -1)
oder auf
p teilt $ [mm] (n^p [/mm] $ -n)
(was sie wohl mit $ [mm] (n^p [/mm] $ -n) = p*k versucht hat darzustellen )
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:44 So 05.10.2008 | | Autor: | Giorda_N |
Bei der Aufgabenstellung sollte es natürlich heissen:
p teilt [mm] (n^p [/mm] - n)
sorry pelzig 
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:48 So 05.10.2008 | | Autor: | pelzig |
... oder so. ^^
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:47 So 05.10.2008 | | Autor: | pelzig |
Probier es doch mal mit
| Aufgabe | | Für eine beliebige Primzahl $p$ und [mm] $n\in\IN$ [/mm] gilt: $p$ teilt [mm] $(n^{p-1}-1)$ [/mm] |
Diese Behauptung ist zumindest wahr 
Gruß, Robert
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:02 So 05.10.2008 | | Autor: | Giorda_N |
möchte eigentlich lieber meine aufgabe zu ende machen....:-(
kann mir niemand helfen wo ich stecken geblieben bin?
danke euch
|
|
|
| |
|
Hallo Nadine,
> möchte eigentlich lieber meine aufgabe zu ende
> machen....:-(
>
> kann mir niemand helfen wo ich stecken geblieben bin?
Ja, das ist schon ganz gut soweit, allerdings hast du einen kleinen Schreibfehler, den du aber in der nächsten Zeile direkt wieder ausgebügelt hast, ich kopiere mal:
[mm] $\left(\summe_{i=0}^{p}\vektor{p \\ i} n^i\right)-(n+1)$
[/mm]
[mm] $=n^p\red{+}\left(\summe_{i=0}^{p-1}\vektor{p \\ i} n^i\right)-n-1$
[/mm]
[mm] $=(n^p-n)+\left(\summe_{i=0}^{p-1}\vektor{p \\ i} n^i\right)-1$
[/mm]
soweit stimmt's wieder, und du hast recht, dass zu zeigen ist, dass $p$ teilt [mm] $\left(\summe_{i=0}^{p-1}\vektor{p \\ i} n^i\right)-1$ [/mm] gilt
Aber schreibe dir einfach mal die Summe da aus:
[mm] $\summe_{i=0}^{p-1}\vektor{p \\ i} n^i\right=\vektor{p\\0}\cdot{}n^0+\vektor{p\\1}\cdot{}n^1+\vektor{p\\2}\cdot{}n^2+\vektor{p\\3}\cdot{}n^3+...+\vektor{p\\p-1}\cdot{}n^{p-1}$
[/mm]
[mm] $=1+p\cdot{}n+\vektor{p\\2}\cdot{}n^2+\vektor{p\\3}\cdot{}n^3+...+\vektor{p\\p-1}\cdot{}n^{p-1}$
[/mm]
Du siehst, die 1 aus dieser Summe hebt sich gegen die -1 am Ende weg, es bleiben lauter Summanden übrig, die alle den Faktor p enthalten, also ist
[mm] $\left(\summe_{i=0}^{p-1}\vektor{p \\ i} n^i\right)-1$ [/mm] durch p teilbar
Und damit schließlich [mm] $(n^p-n)$ [/mm] durch p teilbar nach IV und [mm] $\left(\summe_{i=0}^{p-1}\vektor{p \\ i} n^i\right)-1$ [/mm] durch p teilbar, also
[mm] $(n^p-n) [/mm] \ + \ [mm] \left(\summe_{i=0}^{p-1}\vektor{p \\ i} n^i\right)-1$ [/mm] durch p teilbar
>
> danke euch
LG
schachuzipus
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:02 So 05.10.2008 | | Autor: | pelzig |
So nachdem jetzt das mit der Aufgabenstellung geklärt ist, kommt jetzt die ultimative Antwort ![[happy]](/images/smileys/happy.gif "[happy]")
> (...)
> jetzt wäre noch zu zeigen wie [mm]\summe_{i=0}^{p-1}\vektor{p \\ i} n^i[/mm]
> - 1 durch p teilbar wäre.
[mm]\left(\summe_{i=0}^{p-1}\vektor{p \\ i} n^i\right)-1 = \sum_{i=1}^{p-1}\binom{p}{i}n^i[/mm]
Und jetzt schau mal hier, Aufgabe c)...
Gruß, Robert
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:24 So 05.10.2008 | | Autor: | Giorda_N |
mhm ich steige nicht ganz bei der aufgabe c) wo du mich hinverwiesen hast.....:-(
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:04 So 05.10.2008 | | Autor: | pelzig |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
> mhm ich steige nicht ganz bei der aufgabe c) wo du mich
> hinverwiesen hast.....:-(
Ja da steht halt genau (m=1), dass, falls $p$ prim ist, gilt: $p$ teilt $\binom{p}{k}$, für alle $0<k<p$.
Die Beweisidee steht auch in dem Thread:
$\binom{p}{k}=\frac{p(p-1)\cdot...\cdot(p-k+1)}{1\cdot 2\cdot...\cdot k\$
Offensichtlich teilt $p$ den Zähler. Wenn man nun noch wüsste, dass $p$ den Nenner nicht teilt, wäre alles gezeigt
Gruß, Robert
|
|
|
|
