Mit Kongruenzarithmetik 1!+2!+3!+...+100! (mod 25).bestimmen

Question

Hallo, ich komme bei einer Aufgabe nicht weiter.

Und zwar soll ich mithilfe der Kongruenzarithmetik folgendes bestimmen: 1!+2!+3!+...+100! (mod 25).

Problem/Ansatz:

Ein naives und wirklich sehr langwieriges Vorgehen wäre natürlich die stumpfe Berechnung der Summe mit den ganzen Fakultäten und dann die Berechnung des Ergebnisses (mod 25). Also durch DIvision mit Rest.

Da dieser Lösungsweg sehr lange dauern würde ist er hier mit Sicherheit nicht gefragt. Leider habe ich für diese Aufgabenstellung wirklich keinen anderen Ansatz. Die Kongruenzarithmetik besagt z. B., dass a+b kongruent c+d (mod 25), wenn a kongruent c (mod m) und b kongruent d (mod m). Aber ich weiß wirklich nicht, wie es mir hier helfen soll.

Man wird die Fakultäten hier auf jeden Fall irgendwie zerlegen müssen, so dass (mod 25) einfach zu berechnen ist. Aber ich komme nicht drauf wie.

 …

Answer 1

10! = 1·2·3·4·5·6·7·8·9·10 = 1·2·3·4·5·6·7·8·9·2·5 = 25·1·2·3·4·6·7·8·9·2

Also alles ab 10! mod 25 ist einfach 0, weil der Faktor 25 enthalten ist.

∑ (x = 1 bis 9) (x!) = 409113

409113 mod 25 = 13

Comments

Okay, vielen Dank, das hat mir wirklich die Augen geöffnet... :)

---

Bedenke das man den Rest ja auch vereinfachen kann.

1! mod 25 = 1

2! mod 25 = 2 * 1 mod 25 = 2

3! mod 25 = 3 * 2 mod 25 = 6

4! mod 25 = 4 * 6 mod 25 = 24 (-1)

5! mod 25 = 5 * (-1) mod 25 = -5 (20)

6! mod 25 = 6 * 20 mod 25 = 20 (-5)

7! mod 25 = 7 * 20 mod 25 = 15 

8! mod 25 = 8 * 15 mod 25 = 20 (-5)

9! mod 25 = 9 * 20 mod 25 = 5

Ich habe mal in Klammern ein altrenativen Modulowert notiert. Das hilft beim Rechnen.