(n-1)² ≡ 1 mod n – Beweis ausreichend?

07/10/2013 - 20:43 von Carsten Alexander | Report spam
Bei der systematischen Betrachtung der zyklischen Gruppen ist
offenkundig, dass wohl für n>1 die Form gilt:

2² » 4 - 1·3 = 1
3² » 9 - 2·4 = 1
4² » 16 - 3·5 = 1
5² » 25 - 4·6 = 1
6² » 36 - 5·7 = 1

(n-1)² - n(n-2) = 1

Da ich ungeübt mit mathematischen Formalismen bin, frage ich mich, ob das
einfache Ausmultiplizieren

(n² - 2n + 1) - (n² - 2n) = 1
1 = 1

ausreicht, oder ob ich das noch per „Induktion“ belegen muss.
 

Lesen sie die antworten

#1 Helmut Richter
07/10/2013 - 23:04 | Warnen spam
On Mon, 7 Oct 2013, Carsten Alexander wrote:

Bei der systematischen Betrachtung der zyklischen Gruppen ist
offenkundig, dass wohl für n>1 die Form gilt:

2² » 4 - 1·3 = 1
3² » 9 - 2·4 = 1
4² » 16 - 3·5 = 1
5² » 25 - 4·6 = 1
6² » 36 - 5·7 = 1

(n-1)² - n(n-2) = 1

Da ich ungeübt mit mathematischen Formalismen bin, frage ich mich, ob das
einfache Ausmultiplizieren

(n² - 2n + 1) - (n² - 2n) = 1
1 = 1

ausreicht, oder ob ich das noch per „Induktion“ belegen muss.



Es reicht aus.

Die Induktion wird dann gebraucht, wenn man beim schlichten Ausrechnen *nicht*
aufs gewünschte Ergebnis kommt wie hier, sondern auf etwas, das das Ergebnis
wàre, wenn man nur wüsste, ob die Formel wenigstens für n-1 schon gegolten
hat.

Beispiel: Zu zeigen: a^p = a (mod p), falls p Primzahl.

a^p = ((a-1)+1)^p = (a-1)^p + ... + 1 (nach dem binomischen Satz)

Die ... enthalten nur solche Binominalkoeffizienten, die p im Zàhler, aber
nicht im Nenner stehen haben, diese tragen also zum Ergebnis mod p nichts bei.

Also: a^p = (a-1)^p + 1 (mod p)

Das ist nicht das gewünschte Ergebnis. Wüssten wir aber, dass es für (a-1)
auch schon gilt, wàre es das gewünschte Ergebnis. Also lohnt sich eine
Induktion nach a. Den Induktionsanfang nicht vergessen!

Helmut Richter

Ähnliche fragen