Kleine Inkuktionsaufgabe

Nur der Vollständigkeit halber: Würde man auf die Anforderung "mit Induktion" verzichten, wäre die Aufgabe noch trivialer. Vorausgesetzt man weiß, dass 'mod' mit Addition und Multiplikation (bzw. Exponentiation) vertauscht.

Columbo

5 ist kongruent zu 1 modulo 4, also geht es mit Kongruenzen deutlich trivialer:
5^n + 3 \equiv a \pmod 4
1^n + 3 \equiv a \pmod 4
0 \equiv a \pmod 4

Arcoth schrieb:

5 ist kongruent zu 1 modulo 4, also geht es mit Kongruenzen deutlich trivialer:

Du benutzt hier, dass a^b mod m=(a mod m)^b mod m. mod heisst im Allgäumeinen nicht, dass man alle Terme modulo rechnen darf.

Columbo

allgauator schrieb:

Arcoth schrieb:

5 ist kongruent zu 1 modulo 4, also geht es mit Kongruenzen deutlich trivialer:

Du benutzt hier, dass a^b mod m=(a mod m)^b mod m. mod heisst im Allgäumeinen nicht, dass man alle Terme modulo rechnen darf.

Das war mir klar. Und trivial nannte ich es, weil die von dir genannte Gesetzmäßigkeit trivial aufzuzeigen ist. Schreiben wir das nämlich etwas um:
a^b \pmod m = ((a \mod m) + km)^b \pmod m
Nutzen wir nun die binomial series identity bekommen wir ein Vielfaches von $m$ und (a \mod m)^b als Summe. Vielfache des Moduls können direkt gekillt werden.

Der Modulo-Kram ist natürlich toll, aber zu zeigen, dass die Differenz aus zwei Folgegliedern direkt 4 als Teiler hat, ist doch viel super trivialer?

SG1

Kommt drauf an. Ab einem gewissen Vorwissen ist der "Modulo-Kram" trivial. Man guckt drauf, sagt "passt", fertig. Die Termumformungen für den Induktionsschluss muss man trotzdem machen.

(Wenn die Aufgabenstellung aber "mit Induktion" beinhaltet ist das natürlich nicht relevant - und wenn einem so eine Aufgabe gestellt wird, ist man vermutlich auch noch nicht auf dem Level, dass man für den "Modulo-Kram" einfach "passt" sagen kann.)

Columbo

Kommt drauf an. Ab einem gewissen Vorwissen ist der "Modulo-Kram" trivial. Man guckt drauf, sagt "passt", fertig. Die Termumformungen für den Induktionsschluss muss man trotzdem machen.

Ack.

Wenn die Aufgabenstellung aber "mit Induktion" beinhaltet ist das natürlich nicht relevant

Huch, das habe ich irgendwie übersehen. Dachte der TE hätte es mit Induktion probiert weil er es als passend erachtet hatte.

Aber eben erst ab einem gewissen Vorwissen. Arbeit erleichtert es nicht und einfacher ist's auch nicht. Also ist es ein unangemessenes Werkzeug. So hab ich das zumindest mit den Werkzeugen gelernt
Aber nun gut, es hilft manchmal, sich hinter der Barrikade des Wissens zu verstecken und ein Trivial-Schild davorzustellen Und vielleicht noch ein Ack daneben

Je mehr verschiedene Beweise, desto besser:

Sei 5ⁿ+3=4k. Dann 5ⁿ⁺¹+3=5(5ⁿ+3-3)+3=5(4k-3)+3=20k+12=4(5k+3)=4k'

5^n+3=(1+4)^n+3=3+\sum\limits_{k=0}^n{n \choose k}1^{n-k}4^k=3+1+4(\dots)=4(1+\dots)

Columbo

Aber eben erst ab einem gewissen Vorwissen.

Ja, stimmt. Dafür lernt man Zeugs ja.

decimad schrieb:

Arbeit erleichtert es nicht und einfacher ist's auch nicht.

Doch. Ich kann nämlich auf meine Umformungen schauen und binnen weniger Sekunden deren Richtigkeit bestätigen, weil ich die Gesetze kenne und nicht viel nachzudenken brauche. Das ist bei einem Induktionsbeweis zwar auch nicht so schwer, aber es dauert ggf. etwas länger.

volkard

Arcoth schrieb:

5 ist kongruent zu 1 modulo 4, also geht es mit Kongruenzen deutlich trivialer:
5^n + 3 \equiv a \pmod 4
1^n + 3 \equiv a \pmod 4
0 \equiv a \pmod 4

Gefällt mir sehr gut.

Arcoth schrieb:

decimad schrieb:

Arbeit erleichtert es nicht und einfacher ist's auch nicht.

Doch. Ich kann nämlich auf meine Umformungen schauen und binnen weniger Sekunden deren Richtigkeit bestätigen, weil ich die Gesetze kenne und nicht viel nachzudenken brauche. Das ist bei einem Induktionsbeweis zwar auch nicht so schwer, aber es dauert ggf. etwas länger.

Die Einfachheit des Modulo-Krams hat nochwas mehr.
Auf einmal sehe ich daß (m+1)^n mod m und (2m+1)^n mod m genauso zerfallen wollen. Es ist also nicht nur "cool" oder spart Sekunden, sondern verleiht auch irgendwie Flügel.

Vielleicht ist das auch der Grund, warum manche hier sagen, als Progger solle man mal die Nase in ein Buch über Algos und Datenstrukturen stecken.

kromulodram schrieb:

Je mehr verschiedene Beweise, desto besser:

Noch einer? (Mal wieder mit Induktion)

Anfang: 5+3=8 teilbar durch 4.
Indunktionsannahme: $5^n+3 = 4k$ mit k natürliche Zahl
Induktionsschritt: $5^{n+1} + 3 = 5(5^n+3) - 4\cdot 3 = 4(5k-3)$

Induktionsschritt:
5^{n+1}+3 = 5\cdot 5^n+3 = \underbrace{4\cdot 5^n}_{\in 4\mathbb{N}}+\underbrace{5^n+3}_{\in 4\mathbb{N} \text{ laut Annahme}}