Kongruenzbeweis

Neue Frage »

Monoid Auf diesen Beitrag antworten »
Kongruenzbeweis
Hallo,
Ich will filgende aussage beweisen:

Sei eine ungerade Primzahl, . dann gilt:


Könntet ihr mir einen tipp geben. Zuerst habe ich die linke seite der gleichung durch binomischen lehrsatz umgeformt, sehe aber keinen nutzen.
tmo Auf diesen Beitrag antworten »

Induktion über d kann hier z.b. nicht schaden.


Wenn du mal genauer untersuchst, wie oft die Primzahl in für auftaucht, kannst du jedoch auch deinen Ansatz mit dem binomischen Lehrsatz weiter verfolgen.

Ich bin mal so nett und sage dir, was du zeigen könntest:

bezeichne den Exponenten der Primzahl p in der Primfaktorzerlegung von n. Also beispielsweise .

Ist , so lässt sich in eindeutiger Weise in der Form schreiben, wobei .

Dann gilt .

Rein technisch gesehen halte ich den Weg über die Induktion für schneller. Was den mathematischen Hintergrund angeht, ist der Weg über die Untersuchung der Binomialkoeffizienten natürlich wertvoller.
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von tmo
Wenn du mal genauer untersuchst, wie oft die Primzahl in für auftaucht, kannst du jedoch auch deinen Ansatz mit dem binomischen Lehrsatz weiter verfolgen.

Hm, ist es nicht eigentlich so, dass dies "overkill" ist und er sich eigentlich nur die ersten 3 Glieder der Entwicklung nach dem binomischen Lehrsatz ansehen muss? verwirrt
HAL 9000 Auf diesen Beitrag antworten »

Wie man's nimmt:

Weit "hinten", also bei , hat man dann aber keine Faktoren mehr in . Das wird zwar durch das zugehörige mehr als abgefangen, nichtsdestotrotz muss das bei diesem Weg seriöserweise diskutiert werden... Ich bin deshalb auch für die Induktionslösung, die enthält einfach weniger solche potentiellen Fallen.
tmo Auf diesen Beitrag antworten »

Gerade für hat man das Problem, dass es sehr lange dauert, bis der Einfluss von im binomischen Lehrsatz groß genug ist, um den Summand vergessen zu können

Daher ist es glaube ich schon zwingend notwendig sich genau anzuschauen, was bei mit dem Primfaktor p passiert.

Intuitiv ist es dann klar, dass mod kein Summand ungleich 0 mehr kommt, aber das haarklein zu diskutieren würde ich der Induktionslösung nicht vorziehen smile
Monoid Auf diesen Beitrag antworten »

Nun komme ich zu einem Widerspruch unglücklich :

(I.A.): Widerspruch!

Was ist der Fehler?
 
 
tmo Auf diesen Beitrag antworten »

Wie kommst du denn auf der rechten Seite auf ?

Da steht doch , für ergibt sich also...
Monoid Auf diesen Beitrag antworten »

Häh!

D ist doch
tmo Auf diesen Beitrag antworten »

Ich kann beim besten Willen nicht erkennen, wie du von via zu kommst verwirrt
Monoid Auf diesen Beitrag antworten »

Und für den Induktionsschritt d+1 nehmen nicht?
tmo Auf diesen Beitrag antworten »

Nunja, du nimmst die Aussagen für ein festes als wahr an und zeigst dann, dass sie auch für gilt.

Dafür solltest du dir vielleicht erstmal generell überlegen, was beim Übergang von zu so passieren kann.

Wenn du also hast. Wie sieht diese Kongruenz dann modulo aus? Also wirst du ja i.A. nicht erwarten können.
Monoid Auf diesen Beitrag antworten »

Ich verstehe die fRage nicht. unglücklich
tmo Auf diesen Beitrag antworten »

Naja dann übergehe sie mal und versuche dich einfach am Induktionsschritt. Du wirst vermutlich auf genau das Problem stoßen, dass ich im Vorhinein abklären wollte. Vielleicht verstehst du die Frage dann besser.
Monoid Auf diesen Beitrag antworten »

Puh! Mein Blatt ist leer! keine Ideen! unglücklich ich weißich muss selbst darauf kommen, aber...
tmo Auf diesen Beitrag antworten »

Also vielleicht doch besser erst meine Fragen versuchen zu verstehen und zu beantworten.

Also wenn gilt, so ist per Definition .

Nun wenden wir noch eine Definition an, nämlich die der Teilbarkeit in .

Was bedeutet also definitionsgemäß?
Monoid Auf diesen Beitrag antworten »

tmo Auf diesen Beitrag antworten »

Hmm ja in kann man das so schreiben, weil man eben schon kennt. Aber man will auch über Teilbarkeit sprechen können, ohne überhaupt die Division zu kennen. Daher ist eher folgende Definition gebräuchlich, die dir sicher schon begegnet ist:

bedeutet, dass es ein gibt, so dass .... gilt.
Monoid Auf diesen Beitrag antworten »

tmo Auf diesen Beitrag antworten »

Genau. Also . Das beudetet für uns:

Ist , so wissen wir mit irgendeinem .

Jetzt versuche das mal auf deine Induktionsvorraussetzung

anzuwenden.
Monoid Auf diesen Beitrag antworten »

Das gilt aber nur für ein bestimmtes b oder?
tmo Auf diesen Beitrag antworten »

Ja.
Monoid Auf diesen Beitrag antworten »

tmo Auf diesen Beitrag antworten »

Du hast dich jetzt aber bei den Exponenten verhaspelt. Mehrere Male.
HAL 9000 Auf diesen Beitrag antworten »

Ich schätze mal, das sollte (ziemlich verunglückt) schon irgendwas in Richtung der zu zeigenden Aussage für bedeuten.
Monoid Auf diesen Beitrag antworten »

Ja es ist für d+1. was genau ist falsch?
Monoid Auf diesen Beitrag antworten »

Monoid Auf diesen Beitrag antworten »

Jetzz habe ich immmerhin ( wenn sie richtig ist Big Laugh ) eine Aussage für mod p^{d+1} bekommen.
tmo Auf diesen Beitrag antworten »

Das ist ja schonmal was. Dann schaue dir nochmal an, wo du hinwillst.
Dann siehst du, was du mit der Kongruenz machen musst.
Monoid Auf diesen Beitrag antworten »

Danke für deine Antwort!

Nun, das muss weg.
tmo Auf diesen Beitrag antworten »

Schreib nochmal auf, was du nachher zeigen willst. Also wie der fertige Induktionsschritt lautet.
Monoid Auf diesen Beitrag antworten »

tmo Auf diesen Beitrag antworten »

Ja.

Nun ist also .


Du musst dich also nur noch davon überzeugen, dass letzteres zu wird.
Monoid Auf diesen Beitrag antworten »

Und wie soll ich mich davon überzeugen?

Ich habe keinen wirklichen Schimmer.
Entschuldigung, wenn meine Threads immer so langwierig sind traurig , aber ich bin halt..... Na ja......
tmo Auf diesen Beitrag antworten »

Du musst dir nur überlegen, welche Summanden nach dem Ausmultiplizieren wegfallen . Das sind nämlich ziemlich viele.
Monoid Auf diesen Beitrag antworten »

Was denn ausmultiplizieren?

unglücklich
Monoid Auf diesen Beitrag antworten »

Meinst du das hoch p?
tmo Auf diesen Beitrag antworten »

Ja, natürlich. Da werden doch p Klammern multipliziert.
Monoid Auf diesen Beitrag antworten »

Achso!

Ich dachte das p ist ein Exponent! Sieht aber auch ein bisschen danach aus.
Monoid Auf diesen Beitrag antworten »

p ist ja auch einer.

Mit dem binomiachen lehrsatz?
tmo Auf diesen Beitrag antworten »

Ja und ein Exponent zeigt an, wie oft die Klammer miteinander multipliziert wird...

Dir fehlen offensichtlich so viele Grundlagen, dass ich es nicht nur als wenig sinnvoll, sondern eher schon als sinnlos bezeichnen würde, versuchen dir die Aufgabe zu erklären. unglücklich
Neue Frage »
Antworten »



Verwandte Themen

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