0 Daumen
554 Aufrufe

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.

 …

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

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

Avatar von 477 k 🚀

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.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community