Sei p eine Primzahl, beweise x^p=x in Z/pZ

Question

Sei p eine Primzahl, p ungleich 2. Beweisen Sie, dass x^p = x: für alle x element von

Z/pZ.  Beweisen Sie dies mit vollständiger Induktion über x

Comments

studierst du an der uni basel? :)

p | x^p - x

p | (x+1)^p - (x+1)

binom lehrsatz und p | binom koeffizient wenn 0<k<p

---

wieso teilt p x^p -x

Answer 1

verwende bspw. im Induktionssschritt den binomischen Lehrsatz.

Gruß

Comments

Kommt man so zum Induktionsschritt?

Zu zeigen:

x^p - x = 0 in Z/pZ <==>

x^p = x     | n.V. ist p ungerade Primzahl

x^{2n+1} = x

x* x^{2n} - x = 0

x*(x^{2n} - 1) = 0

x(x^{n} +1)(x^{n}-1) = 0

(x^n +1) (x^{n+1} - x ) = 0

Nun ist aber der blaue Teil nur dann nach Induktionsvoraussetzung  0, wenn n+1 eine Primzahl ist.

---

Möglicherweise hilft auch, dass \(\large\binom pk\in p\mathbb Z\) für alle \(k\in\mathbb N\) mit \(0<k<p\) ist.

---

Und sogar immer dasselbe Element ist.

---

Dann hätte ich im IS (x+1)^p

also kann man den binomischen Lehrsatz anwenden, aber wie weiter verstehe ich trotz den Bemerkungen nicht.

---

Fast alle binomialkoeffizienten in der Entwicklung haben p als Teiler. (Das musst du aber dann auch zeigen, da es nicht klar ist für dich/euch).

---

@Yakyu: Mit fast alle Binomialkoeffizientenhaben p als Teiler meinst du eigentlich alle Binomialkoeffizienten ausser (p über 0) = 1 und (p über k) = x^p. Der ganze mittlere Teil ist deshalb Teiler von p, weil sie element von pZ sind, stimmt's? Somit bleibt nur noch zu zeigen, dass 1 + x^p auch durch p teilbar sind.

---

Das erste ist ungefähr so richtig, wobei die eine Gleichung natürlich falsch ist.

Und nein es ist nicht zu zeigen, dass x^p+1 durch p teilbar ist, sondern dass es dem Element x+1 entspricht (also bzgl. mod p kongruent ist). Hier grüßt die Induktionsvoraussetzung.

---

Beim zweiten Teil, wobei es um das "zu zeigen" geht, bin ich verwirrt. Bevor man überhaupt den binom. Lehrsatz anwendet, hat man ja die Gleichung: (x + 1)^p - (x + 1) = 0. Aufgrund dem, was man mit den Binomialkoeffizienten zeigt, bleibt vom ersten Term noch 1 + x^p, das heisst, man hat noch (1 + x^p) -(x + 1) = x^p - x. Somit erhalten wir die Gleichung aus der Behauptung. Da wir beim Induktionsschritt die Behauptung als wahr angenommen haben, ist der Beweis somit beendet.

---

Ja ist er, warum also die Verwirrung :D?

---

Also, also stimmt es, was ich geschrieben habe??? o.O. Und ist es richtig so, dass der mittlere Teil deshalb Teiler von p ist, weil es element von pZ ist?? :O

---

Ja klar ist doch in sich schlüssig.

Ja schon, aber das ist nur eine andere Formulierung. Du solltest vielleicht noch explizit zeigen warum der Binomialkoeffizient in diesen Fällen Element von pZ ist.

---

Wow, danke dir! Fehlt also nur noch der letzte Teil: Vom Pascalschen Dreieck wissen wir, dass (n über k) immer eine natürliche Zahl ist, d.h. (n über k) ∈ ℕ. Da eine Primzahl auch eine natürliche Zahl ist, ist p ∈ ℕ. Da die Ausdrücke im mittleren Teil von Binomialkoeffizienten jeweils das Produkt von (p über k) und der Variabeln x^{1...p}, wobei ∀x∈ ℤ/pℤ (also Z modulo prim) ist, muss gelten, dass sie durch p teilbar sind, denn in der Behauptung wurde angenommen, p | x^p = x wobei ∀x∈ ℤ/pℤ gilt.

Reicht dies als Erläuterung?

---

Nein das ist ja keine echte Begründung dafür, dass \(\binom {p}{k}\) von p geteilt wird, falls 0 <k <p. Insbesondere besagt die Behauptung die zu beweisen ist nicht, dass x^p durch p teilbar ist, da scheinst du etwas falsch zu interpretieren.

Im Grunde ist es ganz simpel. Schreib dir doch mal aug wie \(\binom {p}{k}\)  aussieht und begründe warum es ein Vielfaches von p ist.

---

Sei p = n. Aus der Gleichung folgt, dass p sowohl im Nenner wie auch im Zähler ist. Dieser Bruch ergibt immer eine ganze Zahl (Vgl. Pascalsches Dreieck). Da p in diesem Bruch enthalten ist, ist sie Teiler von (n über k).

---

Aha wo ist denn p im Nenner? Nur weil p als Faktor im Zähler vorkommt heißt es nicht, dass es ein Teiler ist. Das würde nur gelten wenn p eine bestimmte Eigenschaft erfüllt (die es auch tut). Und vor allem warum.....

Und dieses vgl Pascalsches Dreieck ist auch nicht sonderlich sinnvoll.

---

Langsam bin ich am verzweifeln :-( p hat die Eigenschaft, dass es nur durch 1 und sich selber teilbar ist. Zusätzlich, um die Beziehung zwischen k und p zu erläutern, gilt, dass 1 ≤ k < p ist.

---

Du hast mir bisher keine Begründung geliefert nur die Eigenschaften aufgezählt die relevant sind. Ohne Assoziation kommen wir nie zu einem schlüssigen Beweis (was mich verwirrt da du oben ja schon eine gute Verbindung gemacht hast was den kompletten Beeweis betrifft).

Um dich mal aus deiner Qual zu befreien. Sei \(0 <k <p \):

$$ \binom {p}{k} = \frac{p \cdot (p-1)!}{k!(p-k)!} $$

Da \(p\) prim und \(\binom {p}{k} \in \mathbb{N} \) ist gilt \(k!(p-k)! | (p-1)!\) und daraus folgt unmittelbar, dass \(p|\binom {p}{k}\).

---

Das war genau auch der Punkt, von der aus ich nicht weiter konnte. Es gibt ja manchmal, dass man fast ein Puzzlebild beendet hat, jedoch ein Puzzlestück sich irgendwo versteckt hat, man es nicht finden kann und deshalb das Bild unvollständig ist... Nur noch eine letzte Frage: Weshalb ist bei dir im Zähler p*(p - 1)! und nicht nur p! ? Der Rest macht ansonsten Sinn :)

---

Eigentlich wäre es in diesem Fall eher so, dass du alle Puzzlestücke hast aber nicht weißt wie sie zusammen passen. Wir sind hier ja nicht in der Deutschlounge also kein grund sich weiter in Metaphern zu vertiefen :D.

Zu deiner letzten Frage: Das ist doch das gleiche, falls es nicht klar ist schau dir bitte an was eine Fakultät ist.

---

Tut mir leid, war nicht so gemeint... Bin wohl langsam müde, daher die bildlichen Vorstellungen... :DAch, stimmt ja! Ich glaube, so langsam muss ich ins Bett :DIch danke dir vom ganzen Herzen für die Hilfe, Geduld und Zeit, die du dir genommen hast! Es ist erfreulich, dass es noch Mitglieder auf Forums gibt, die die Lösung nicht einfach dahin schreiben, sondern eben einem Ideen geben, um auf die Lösung möglichst alleine zu kommen! In meinem Fall hat es ja nicht ganz so geklappt, aber immerhin :) Wünsche dir einen schönen Abend noch!

---

Kein Thema gerne. Genau so sehr schätze ich es, wenn Leute es probieren möglichst selbst auf die Lösung zu kommen. Manchmal kann es zwar eher suboptimal laufen, aber wenn du wenigstens mitnehmen konntest wo genau deine Probleme lagen, so ist ja doch was positives bei rum gekommen :). Wünsche ich dir auch.