Beste Antwort
Im Ausdruck von 1! bis 200!, alle Zahlen sind bis auf die ersten 6 Terme durch 14 teilbar. Warum?
- 14 = 2 \ mal 7
- Jetzt ist 7 nicht mehr bis zu 6!
Also, R [\ dfrac {1! + 2! + 3! +… .. + 200!} {14}]
= R [\ frac {(1! + 2! +…. + 6!) + (7! + 8! +… .. + 200! )} {14}]
= R [\ frac {(1! + 2! +…. + 6!)} {14}] + R [\ frac {(7! + 8! + … .. + 200!)} {14}]
= R [\ dfrac {(1 + 2 + 6 + 24 + 120 + 720)} {14}] + 0
= R [\ dfrac {873} {14}]
= 5 ( Antwort )
Antwort
Auf Quora gibt es viele Fragen dieser Art. Sie erfordern im Allgemeinen keine tiefen Einsichten, um sie zu beherrschen.
Das Wichtigste ist, dass die Potenzierung unter einem Modul zyklisch ist. Wir müssen nur herausfinden, wie groß dieser Zyklus ist, was durch einfaches Ausprobieren erreicht werden kann.
2 ^ 1 = 2 2 ^ 2 = 4 2 ^ 3 = 8 2 ^ 4 = 16 ( an dieser Stelle konnten wir feststellen, dass 16 = -1 Modulo 17 und aufhören, aber lasst uns weitermachen.) 2 ^ 5 = 32 = 15 2 ^ 6 = 2 * 15 = 30 = 13 2 ^ 7 = 2 * 13 = 26 = 9 2 ^ 8 = 2 * 9 = 18 = 1
Nun ist die andere Tatsache, die wir brauchen, dass x ^ {ab + c} = (x ^ a) ^ bx ^ c. Weil 2017 = 8 * 252 + 1, 2 ^ {2017} = (2 ^ 8) ^ {252} * 2. Unter Verwendung der obigen Berechnung ist 2 ^ 8 = 1 mod 17, also 2 ^ {2017} = 1 ^ {252} * 2 = 2 mod 17.
Dann fügen wir eins hinzu, um das Endergebnis zu erhalten, nämlich 3.
Angenommen, wir möchten nur die Antwort „direkt“ berechnen. Dies ist möglich Tun Sie dies mit wiederholtem Quadrieren – was bei Anwendungen nützlich ist, bei denen der Modul möglicherweise groß genug ist, dass wir nicht einmal einen einzigen Zyklus abschließen. Die Basis dieser Technik ist, dass x ^ {2k} = (x ^ k) ^ 2. Stellen Sie den Exponenten binär dar. Jedes Mal, wenn die am weitesten links stehende Binärziffer eins ist, werden wir mit x multiplizieren. Wenn wir dann zur nächsten Ziffer übergehen, quadrieren Sie den aktuellen Wert.
In diesem Fall 2017 = 11111100001b. Nehmen Sie jede Ziffer nacheinander (und beginnen Sie mit dem Anfangswert „1“):
1: (1 * 2) ^ 2 = 4 1: (4 * 2) ^ 2 = 13 mod 17 1: (13 * 2) ^ 2 = 9 ^ 2 = 13 mod 17 1: (13 * 2) ^ 2 = 13 1: (13 * 2) ^ 2 = 13 0: 13 ^ 2 = 16 0: 16 ^ 2 = 1 0: 1 ^ 2 = 1 0: 1 ^ 2 = 1 1: 1 * 2 = 2
Dies stimmt mit unserer früheren Berechnung überein, dass 2 ^ {2017} = 2 mod 17.