5|n^5-n ohne Induktion beweisen

Question

Aufgabe:

Ich will zeigen dass n^5-n durch 5 teilbar ist. (ohne Induktion)

Problem/Ansatz

Google meint man kann mit Restklassen arbeiten. Ich weiß was Restklassen sind, aber mein Wissen reicht leider nicht aus um damit zu argumentieren.

Answer 1

Es ist n^5 - n = n*(n^2-1)*(n^2+1)

Jetzt brauchst du nur die 5 Fälle durchzugehen, die die Zahl n in Bezug

auf die Vielfachen von 5 haben kann. (Das sind die Restklassen.)

1. Fall :  Rest 0 Modulo 5, also n ist selber durch 5 teilbar, dann natürlich

auch jedes Vielfache von n, insbesondere eben n*(n^2-1)*(n^2+1) .

2. Fall Rest 1 Modulo 5, also ist n von der Art  n=5k+1.

==>  n^2 = 25k^2 + 10k + 1 also ist n^2-1 durch 5 teilbar und damit auch

das Produkt n*(n^2-1)*(n^2+1) .

3. Fall: Rest 2 Modulo 5, also  n=5k+2 .

==>  n^2 = 25k^2 + 20k + 4 , also  n^2 + 1 durch 5 teilbar und damit auch

das Produkt n*(n^2-1)*(n^2+1) .

4. Fall:  Rest 3 Modulo 5, also n^=5k+3 ==> n^2 = 25k^2 + 30k + 9 ,

also n^2 + 1 durch 5 teilbar und damit auch

das Produkt n*(n^2-1)*(n^2+1) .

5. Fall (letzter) Rest 4 Modulo 5 also n=5k+4

==>  n^2 = 25k^2 + 40k + 16 also n^2 -1 durch 5 teilbar und damit ...

Comments

Wenn du die Faktorisierung konsequenter durchziehst, sind drei der fünf Fälle sofort erledigt.

---

Danke, gute Idee !

Answer 2

Aloha :)

$$n^5-n=n(n^4-1)=n(n^2-1)(n^2+1)=n(n-1)(n+1)(n^2+1)$$$$\phantom{n^5-n}=n(n-1)(n+1)(n^2-4+5)$$$$\phantom{n^5-n}=n(n-1)(n+1)(n^2-4)+n(n-1)(n+1)\cdot5$$$$\phantom{n^5-n}=n(n-1)(n+1)(n-2)(n+2)+n(n-1)(n+1)\cdot5$$Der erste Summand besteht aus 5 aufeinander folgenden Faktoren und muss daher durch 5 teilbar sein. Der zweite Summand ist wegen des Faktors 5 natürlich durch 5 teilbar. Damit ist \(n^5-n\) durch 5 teilbar.

Comments

Geniale Idee, vollkommen ohne Fallunterscheidung !

---

Was geht hier ab  :D cool

n(n−1)(n+1)(n²−4+5) =

n(n−1)(n+1)(n²−4)+n(n−1)(n+1)⋅5

Answer 3

Es gibt 5 mögliche Fälle:

n lässt bei Teilung durch 5 den Rest 0

n lässt bei Teilung durch 5 den Rest 1

n lässt bei Teilung durch 5 den Rest 2

n lässt bei Teilung durch 5 den Rest 3 (bzw. -2)

n lässt bei Teilung durch 5 den Rest 4 (bzw. -1).

Berechne für jeden der 5 Fälle den Rest von n⁵-n bei Teilung durch 5.

PS: Den Rechenaufwand für diese Fälle kannst du mit der Faktorisierung

n⁵-n=n(n⁴-1)=n(n²-1)(n²+1)=(n-1)*n*(n+1)*(n²+1) etwas reduzieren.

Comments

Danke abakus

Answer 4

Hallo bahamas,

Es ist zu zeigen dass \(n^5-n \equiv 0 \mod 5\). Nach dem Satz von Euler und Fermat gilt$$n^{\varphi(k)} \equiv 1 \mod k$$wobei \(\varphi(k)\) die Eulersche Phi-Funktion ist. Für Primzahlen \(p \in \mathbb{P}\) gilt: \(\varphi(p)=p-1\). Demnach ist $$n^{p-1} \equiv 1 \mod p, \quad p \in \mathbb{P}$$Also gilt auch$$\begin{aligned} n^{p-1} - 1 &\equiv 0 \mod p, \quad p \in \mathbb{P}\\ n \left( n^{p-1} - 1 \right)&\equiv 0\mod p \\ n^p - n &\equiv 0 \mod p \end{aligned}$$und da die 5 eine Primzahl ist, ist auch \(n^5-n \equiv 0 \mod 5\) bzw. \(5\mid n^5-n\).

Answer 5

n^{5} - n =

n*(n^{2}-1)*(n^{2}+1) ≡

n*(n^{2}-1)*(n^{2}-4) =

(n-2)*(n-1)*n*(n+1)*(n+2)

= 0 mod 5

ist vermutlich am einfachsten.

Comments

Man kann auch von "hinten" vorgehen, insbesondere dann, wenn man sonst keine Ideen hat. Sicher ist $$(1) \quad 5 \:\vert\: (n-2)\cdot(n-1)\cdot n\cdot(n+1)\cdot(n+2)$$und damit nach Ausmultiplizieren auch$$(2) \quad 5 \:\vert\: n^5-5n^3+4n.$$Sicher ist auch $$(3) \quad 5 \:\vert\: 5n^3-5n.$$ Dann muss aber auch $$(4) \quad 5 \:\vert\: \left(n^5-5n^3+4n\right)+\left(5n^3-5n\right)$$ als Summe von (2) und (3) und damit schließlich $$(5) \quad 5 \:\vert\: n^5-n$$ gelten, was zu zeigen war. Wie zu sehen ist, kommt man auch ohne Ausklammern aus.