Primzahlpotenzen in n! < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | a) Für eine reelle Zahl x bezeichne [x] die größte ganze Zahl kleiner gleich x. Sei p eine Primzahl und n eine natürliche Zahl und [mm] p^{k}, k\ge [/mm] 0 sei die höchste p-Potenz, die in n! aufgeht. Dann ist
k = [mm] [n/p]+[n/p^{2}]+[n/p^{3}]+...
[/mm]
b) Mit wie vielen Nullen hört die Zahl 2007! in der Dezimaldarstellung auf?
c) Man bestimme die letzten zwei Ziffern von [mm] 2^{1000} [/mm] und [mm] 3^{1000} [/mm] (wieder in Dezimaldarstellung). |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Also, ich hab Zahlentheorie neu begonnen und war bisher ein Jahr im Ausland und hatte während der Zeit nicht wirklich viel mit Mathe zu tun , gehabt, weshalb das vielleicht gar keine so schwere Aufgabe ist, mir nur etwas der Einstieg fehlt.
Kurzum: Mir ist klar, was dieser Zusammenhang aus a) bedeuten soll, nur fehlt mir irgendwie etwas der Zugang dazu. Was ich versucht habe ist,
mir das ganze Mal anhand von ein paar konkreten Beispielen hinzuschreiben, jedoch führte mich das irgendwie nicht wirklich weiter.
Da wir bisher nicht viel in der VL gemacht haben und mir noch ein wenig die Denkweise hier zu fehlen scheint, versuchte ich mein Glück mit Restklassen, aber auch da, fehlte mir wohl die zündende Idee(?)
Ich stehe hier etwas auf dem Schlauch schätze ich und ein kleiner Hinweis, um mich vom Denken her in die richtige Richtung laufen zu lassen, wäre wahrscheinlich total hilfreich.
Will die Aufgabe natürlich verstehen und so weit es geht auch selbst bearbeiten, sonst hätte ich das Ding abgeschrieben und nicht hier gepostet.
Also, wenn mir einer einen Hinweis geben kann, wäre ich dankbar. Ich schätze, dass das bestimmt nicht so schwer ist, ich nur gerade ein Brett vor dem Kopf habe.
b) und c) sind dann wohl Anwendungen von a). Was natürlich voraussetzt, dass man a) versteht, was ich bisher noch nicht so ganz tue 
Bin für jede Hilfe dankbar und freue mich über jede Antwort.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:58 Fr 27.04.2007 | | Autor: | DirkG |
a) Rechne aus mit deiner gegebenen Formel, wie oft (d.h. in welcher maximalen Potenz) der Primfaktor 5 in 2007! enthalten ist. Und dann überlege dir mal, was das mit der Anzahl der Endnullen von 2007! zu tun hat...
b) Da gibt es unzählige Möglichkeiten, diese beiden Werte [mm] $2^{1000} \mod [/mm] 100$ und [mm] $3^{1000} \mod [/mm] 100$ zu berechnen, z.B. iterativ
[mm] $$\left( \left( 2^{10} \mod 100 \right)^{10} \mod 100 \right)^{10} \mod [/mm] 100 ,$$
oder irgendwie anders unter Nutzung der Potenzgesetze. Mit etwas Geschick kann man auch Fermat-Euler [mm] $a^{\varphi(m)} \equiv [/mm] 1 [mm] \mod [/mm] m$ für teilerfremde $a,m$ vorteilhaft einsetzen, um die Rechnung zu verkürzen. Alles in allem führen hier sehr, sehr viele Wege nach Rom.
|
|
|
| |
|
Ok, danke. Das ist schon sehr hilfreich. Aber wie ich a) beweise ist mir noch nicht ganz klar. Wie zeige ich, dass die Formel allgemein gilt? Da hapert's noch etwas... Mit dem Rest dürfte ich dank deinem Tipp klarkommen.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:47 So 29.04.2007 | | Autor: | felixf |
Hallo!
> Ok, danke. Das ist schon sehr hilfreich. Aber wie ich a)
> beweise ist mir noch nicht ganz klar. Wie zeige ich, dass
> die Formel allgemein gilt? Da hapert's noch etwas... Mit
> dem Rest dürfte ich dank deinem Tipp klarkommen.
Sei zu einer Zahl [mm] $\ell \in \IZ \setminus \{ 0 \}$ [/mm] die Zahl [mm] $\nu_p(\ell) [/mm] = [mm] \max\{ k \in \IN : p^k \mid \ell \}$ [/mm] (also groesste Exponent $k$, so dass [mm] $p^k$ [/mm] die Zahl [mm] $\ell$ [/mm] teilt).
Damit ist [mm] $\nu_p(n!) [/mm] = [mm] \sum_{\ell=1}^n \nu_p(\ell) [/mm] = [mm] \sum_{\ell=1}^n \sum_{k=1}^\infty \mathbf{1}_{[k,\infty)}(\nu_p(\ell))$. [/mm] Hierbei ist [mm] $\mathbf{1}_{[k,\infty)}(x)$ [/mm] die Indikatorfunktion zur Menge [mm] $[k,\infty)$, [/mm] also [mm] $\mathbf{1}_{[k,\infty)}(x) [/mm] = [mm] \begin{cases} 1 & \text{wenn } x \in [k,\infty) \\ 0 & \text{sonst} \end{cases}$. [/mm] Ueberleg dir mal warum das so ist.
So. Nun kannst du die Summen vertauschen und die innere Summe [mm] $\sum_{\ell=1}^n \mathbf{1}_{[k,\infty)}(x)$ [/mm] weiter betrachten. Diese ist gleich der Anzahl der Elemente in [mm] $\{ \ell \in \{ 1, \dots, n \} : p^k \mid \ell \}$ [/mm] (ueberleg dir warum das so ist). Schliesslich musst du dir noch ueberlegen, dass diese Anzahl gerade [mm] $[n/p^\ell]$ [/mm] ist, dann bist du fertig.
LG Felix
|
|
|
|
