beweis ... evtl vollst. induktion

Neue Frage »

Untier Auf diesen Beitrag antworten »
beweis ... evtl vollst. induktion
wie haben in mathe eine übungsaufgabe bekommen , in der wir beweisen sollen , dass

n^p - n = m * p ist wobei n jede natürliche zahl die grösser als 1 ist
p eine beliebige primzahl
und m wieder eine natürliche zahl ist

in worten also
Nehme man eine natürliche zahl (grösser als 1) nehme sie mit einer beliebigen primzahl hoch ... und ziehe dann die natürliche zahl wieder ab , so erhält man ein ergebniss das wieder rum durch die vorher genutze primzahl dividiert eine ganze natürliche zahl ist.

Das problem ist nun .. wie beweise ich das ...
Wir haben es mit mehreren leute mit der vollst. induktion versucht .. die verankurung ist natürlich kein problem , aber mit n+1 bekommen wir da sehr grosse probleme.

ich weiss eswäre sehr viel verlangt eine erklärung zu geben , aber falls jemand einen guten ansatz für mich hat wäre ich schon sehr dankbar

gruss untier
Leopold Auf diesen Beitrag antworten »

Wenn du Ahnung hast von zyklischen Gruppen, dann geht es ganz einfach. Ansonsten mußt du zahlentheoretische Argumente verwenden. Und im übrigen lohnt es sich, unter "Kleiner Satz von Fermat" zu googeln.
Untier Auf diesen Beitrag antworten »

zum satz von fermat hab ich tatsächlich sehr schöne beweise gewfunden die ich mal versuche auf mein problem das ja sehr änhlich (evtl ists das gleiche nur etwas anders geschrieben muss ich nochal genau hinsehen) anwenden kann

miltiplizieren mit rest muss ich dazu wohl noch mal nachhohlen , danke für den hinweis =)
WebFritzi Auf diesen Beitrag antworten »

Ich finde deinen Nick cool... Rock
Untier Auf diesen Beitrag antworten »

danke , damit renne ich shcon seit nunmehr fast 7 jahren im netz rum =)

ok , nochmal zum problem , ich hoffe mit hilft nochmal jemand

ich hab nurn mit hilfe des satzes von fermat meine aufgabe für mich gut verständlich umformuliert

wenn ich eine zahl n hoch p nehme und wieder durch p teile ( p = primzahl)

dann erhalte ich eine ganze zahl + einen rest (welcher auch 0 sein kann ,w as immer dann passiert wenn n ein vielfaches von p ist)
ausserdem ist der rest immer n / p

den rest eleminiert er in der aufgabe indem er alles * p nimmt dnan steht da halt
n^p = m * p +n m soll meine ganze zahl sein und wenn ich wieder -n nehme habe ich meine ursprungsaufgabe die meinen rest eleminiert.

aber ich verstehe noch nicht wieso mein rest immer n / p ist ich sehe da keinen zusammenhang .. und solange ich den nicht sehe , habe ich gorsse probleme zu beweisen das ser satz stimmt =(

ich will jetzt auch nicht einfach die formal nachf ermat umstellen (geht ja ohne probleme hab ich eben egsheen) und dann deren beweis 1-1 abschrieben , verstehen wäre mir lieber , also wenn noch jemand 1-2 helfende worte finded die mir helfen könnten wäre ich nochmals sehr dankbar

greetings Untier


--- ich schau mal noch bisls weiter hier =)
WebFritzi Auf diesen Beitrag antworten »

Gib doch mal den Satz von Fermat hier an. Ich kenne den nämlich nicht...
 
 
Untier Auf diesen Beitrag antworten »

Satz des Fermat
(n ^p-1) -1 ist teilbar durch p

im endeffekt is das das delbe
das schreibe ich als

n^p * 1/n - 1 = m*p

und ehrm jetzt komme ich grade gar nicht mehr auf meine form .. ich bin atm voll dabei raus zu bekommen wieso mein rest immer n/p ist ...

z.B. damit wir mal ne zahl sehen hier
n=2
p=5

2*2*2*2*2 / 5 = 30/5 + 2/5

es kommt auch immer so wunderbar hin .. nur wieso ... ich blicks nich =)
WebFritzi Auf diesen Beitrag antworten »

Was ist daran so schwer zu verstehen? Wenn du



hast, dann ist doch

WebFritzi Auf diesen Beitrag antworten »

Ach ja... Kann mir jemand zeigen, wie das ganze mit zyklischen Gruppen zusammenhängt? Interessiert mich nämlich.
Untier Auf diesen Beitrag antworten »

das problem ist , das ich beweisen soll das
n^p -n = m * p ist

was du geschrieben hast ist eine schön umformung dir mir ca . 40 minuten der letzen stunde gespart hätte ^^ aber als beweiss hilft mir das wohl nicht viel weiter ?!

ich hatte mit beweisen bisher noch nicht so viel zu tun , aber nur umstellen bewiesst glaube ich nicht sehr viel ^^


btw , dein pic rockt derbe =)
Untier Auf diesen Beitrag antworten »

aber .. ich glaube ich hab nen ansatz mit dem ich was beweisen kann


ALSO

m * n * p + n = n^p wenn n kein vielfaches von p ist
sonst
m * n * p + 0 = n^p

daran lässt dich erkennen das n * p mit n ^p nur durch ein +n (welches ich ja in meiner formel kille ) und den faktor m (m E N ) unterschidlich sind

wenn ich das auf die form meiner ursprungsformel bringe sollte das als beweis ausreichen oder ? ...

ich mach mich mal ans umformen ... wenn jemand nen kommantar dazu hat wäre das nett .. marke guter ansatz klappt .. oder so geht nich =)
WebFritzi Auf diesen Beitrag antworten »

Du machst aus ner Mücke nene Elefanten. Der Satz von Fermat sagt doch: Zu n und p gibt es M, so dass



Jetzt multipliziere die Gleichung mit n. Dann steht da



Setze nun noch m = Mn, und du bist fertig.
Untier Auf diesen Beitrag antworten »

ja

unser prof sagt dann

wenn du den satz von fermat benutzt ... must du erstmal dne satz von fermat beweisen (und das is kein scherz .. er hat uns mit erweiterung von büchen beweisen lassen das man so dividieren kann befor wir schriftlich dividieren durften) ...

und dnen satz von fermat zu beweisen wird ja nicht einfacher

aber es ist interresant das du meine lang erarbeiteten ergebnisse immer so locke rmit einer umformung zeigen kannst ... irgentwie komme ich mir nun recht dumm vor =(
WebFritzi Auf diesen Beitrag antworten »

Das ist die Erfahrung, die ich mehr habe als du. Aber da hättest du wirklich selber drauf kommen können.
Wenn ihr den Satz von Fermat noch nicht gehabt habt, kann es sein, dass du ihn noch beweisen musst. Andernfalls wäre dies Blödsinn.
Schläfer Auf diesen Beitrag antworten »

Ich hab schon wieder vergessen, wie man den kleinen Fermat beweist, aber dafür kann ich einen Beweis der Behauptung
"p | n^p - n"
anbieten.

Ich arbeite mit der binomischen Formel

Wer sie nicht kennt: Hand heben. *g*

Der Binomialkoeffizient

hat die nette Eigenschaft, dass er eine ganze Zahl ist, die für 1 < k < p durch p teilbar ist. (Begründe das!)

Wir beweisen durch vollständige Induktion nach n die Aussage: Es gibt eine ganze Zahl m, so dass n^p - n = m*p.

Für n=0 und n=1 gilt die Gleichung mit m=0.

Gelte sie für n. Dann berechnen wir:

In der großen Summe sind die "mittleren" Summanden für 1 < k < n alle durch p teilbar (wegen dem Binomialkoeffizienten), die können wir also alle zusammen als "t*p" schreiben mit einer ganzen Zahl t, wir erhalten damit

Forme das weiter um und wende die Induktionsvoraussetzung an, um die Induktionsbehauptung für n+1 zu erhalten.

Aus dieser Aussage kann man übrigens den kleinen Fermat herleiten, indem man (für zu p teilerfremde n) die Gleichung n^p - n = mp mit dem modulo p inversen von n multipliziert.
WebFritzi Auf diesen Beitrag antworten »

Zitat:
Original von Schläfer

Der Binomialkoeffizient

hat die nette Eigenschaft, dass er eine ganze Zahl ist, die für 1 < k < p durch p teilbar ist. (Begründe das!)


Ja, begründe das bitte. Würde mich nämlich interessieren. Und ich bitte auch um den Nachweis, dass er eine ganze Zahl ist. Den Beweis habe ich nämlich noch nie gesehen. Danke.
Calculator Auf diesen Beitrag antworten »

Ich habe mir dazu folgendes überlegt:

Binomialkoeffizient ist ganze Zahl:

Ich versuche an einem Beispiel meine Idee zu erläutern. Ein exakter Beweis könnte darauf aufbauen, würde aber ziemlich undurchsichtig werden, und um die Idee aufzuzeigen, genügt ein Beispiel.

Sei z.B. k=9, p > 9 beliebig
Für 9 aufeinanderfolgende, natürlichen Zahlen gilt:
- Es treten mind. Zahlen auf, die durch 2 teilbar sind.
- Es treten mind. Zahlen auf, die durch 3 teilbar sind.
- Es treten mind. Zahlen auf, die durch 4 teilbar sind.
- Es treten mind. Zahlen auf, die durch 5 teilbar sind.
- Es treten mind. Zahlen auf, die durch 6 teilbar sind.
- Es treten mind. Zahlen auf, die durch 7 teilbar sind.
- Es treten mind. Zahlen auf, die durch 8 teilbar sind.
- Es treten mind. Zahlen auf, die durch 9 teilbar sind.


Also gilt wobei den Zähler des Binomialkoeffizienten beschreibt.
Weiterhin gilt:
, was ja gerade den Nenner des Binomialkoeffizienten darstellt. Damit ergibt sich die Behauptung.
Im allgemeinen Fall muss man dann eben sämtliche Primfaktoren bis k mit entsprechenden Exponenten betrachten.


Binomialkoeffizient ist für 0 < k < p durch p (p Primzahl) teilbar
Das ergibt sich unmittelbar aus den obigen Überlegungen, denn für k<p taucht die Primzahl p im rechten Produkt(also im Nenner) als Faktor nicht auf. Deswegen kürzt sie sich im Zähler nicht weg und der ganze Binomialkoeffizient ist noch ein Vielfaches von p.
WebFritzi Auf diesen Beitrag antworten »

Mir ist grade aufgefallen, dass sich die erste Behauptung ganz einfach durch vollst. Induktion zeigen lässt.



WebFritzi Auf diesen Beitrag antworten »

Für den Beweis der zweiten Behauptung zitiere ich Calculator. Es ist doch für für 0 < k < p:



Die Primzahl p taucht im Nenner als Faktor nicht auf. Deswegen kürzt sie sich im Zähler nicht weg, und der ganze Binomialkoeffizient ist noch ein Vielfaches von p.
Calculator Auf diesen Beitrag antworten »

Zitat:
Original von WebFritzi
Mir ist grade aufgefallen, dass sich die erste Behauptung ganz einfach durch vollst. Induktion zeigen lässt.


Freude So ist es natürlich viel eleganter und schöner. Freude
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »