Fakultät < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:10 Di 20.01.2009 | | Autor: | julmarie |
| Aufgabe |
Wie viele und welche Teiler hat die Fakultät irgendeiner Zahl + 90? Z.B. 79684! |
Hi,
also ich weiß schon das die Zahl aufjedenfall alle Teiler von 90 hat, das sind insgesamt 12, und sich selbst! aber wie finde ich die anderen heraus?
|
|
| |
|
Hallo julmarie,
das ist ja eine nette Aufgabe. Und eine umfangreiche dazu.
Du wirst einen Lösungsalgorithmus entwickeln können, aber keine explizite Lösung für beliebiges n.
Wieviel Zahlentheorie kannst Du? Der Algorithmus ist vielleicht leichter darzustellen, wenn Du die grundlegenden zahlentheoretischen Funktionen kennst. Ich müsste sie ehrlich gesagt nachschlagen, aber die Grundidee kann ich Dir geben.
Du kannst ja erst einmal sicher sagen, dass alle Primzahlen [mm] \le \a{}n [/mm] Teiler von n! sind. Aber wie oft, das heißt, in welcher Potenz kommen sie vor?
Nehmen wir den umfangreichsten Fall, der allerdings eine Sonderrolle spielt: die 2. Wegen der Sonderrolle lasse ich den nächsten Schritt dann erst einmal Dir, nämlich die 3. Wenn Du die auch verstanden hast, hast Du alle weiteren im Prinzip gleich mit erledigt.
Außerdem nehme ich nicht den allgemeinen Fall, sondern ein bestimmtes n als Beispiel. Ich wähle n=101.
101! hat nun nur Teiler, die aus den Primzahlen 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97 und 101 zusammengesetzt sind. Das sind alle Primzahlen, die [mm] \le \a{}101 [/mm] sind.
Welches ist nun die höchste enthaltene Zweierpotenz?
Nun ist [mm] 2^7>101, [/mm] also ist der höchste "Lieferant" die [mm] 64=2^6. [/mm] Dann die [mm] 32=2^5, [/mm] aber auch ihre "ungeraden" Vielfachen (die "geraden" sind ja mindestens durch 64 teilbar und daher schon erfasst), hier also nur 3*32. Dann die [mm] 16=2^4 [/mm] und 3*16, 5*16, weiter [mm] 8=2^3 [/mm] und 24,40,56,72,88. Die [mm] 4=2^2 [/mm] ist dann entsprechend 13mal zu berücksichtigen [mm] ((2*\blue{13}-1)*2^2)<101<(2*14-1)*2^2 [/mm] und schließlich die 2 genau 25mal [mm] ((2*\blue{25}-1)*2<101<(2*26-1)*2).
[/mm]
Insgesamt ist der Exponent der 2 also: [mm] \blue{1}*6+\blue{2}*5+\blue{3}*4+\blue{6}*3+\blue{13}*2+\blue{25}*1=97.
[/mm]
Damit wissen wir: [mm] 2^{97} [/mm] teilt [mm] \a{}101!, 2^{98} [/mm] tut das nicht. Immerhin ein Anfang für die Primfaktorzerlegung.
Das kann man übrigens an der Binärdarstellung von 101 ablesen:
[mm] 1100101_2=101_10=1*2^6+1*2^5+1*2^2+1
[/mm]
Wie oft nun [mm] 2^k [/mm] zum Gesamtexponenten beiträgt, ist an den ersten (7-k) Stellen abzulesen: die ungerade Zahl, die genauso groß ist wie die abgelesene Zahl oder eben um 1 kleiner, wenn die Ablesung eine gerade Zahl ergibt, sei [mm] m_k. [/mm] Dann ist der gesuchte Faktor [mm] x_k=\bruch{1}{2}(m_k+1).
[/mm]
So:
[mm] 1100101_2 [/mm] von links gelesen...
[mm] 2^6: m_6=1, x_6=\blue{1}
[/mm]
[mm] 2^5: 11_2=3_{10}=m_5, x_5=\blue{2}
[/mm]
[mm] 2^4: 110_2=6_{10}\Rightarrow 5=m_4, x_4=\blue{3}
[/mm]
[mm] 2^3: 1100_2=12_{10}\Rightarrow 11=m_3, x_3=\blue{6}
[/mm]
[mm] 2^2: 11001_2=25_{10}=m_2, x_2=\blue{13}
[/mm]
[mm] 2^1: 110010_2=50_{10}\Rightarrow 49=m_1, x_1=\blue{25}
[/mm]
Die blauen Zahlen kennst Du ja schon von oben...
So, jetzt wäre noch das allgemeine System zu ermitteln. Dazu ist eine Überlegung nötig, die erst ab dem Primfaktor 3 greift.
Außerdem musst Du Dich noch fragen, bis zu welcher Primzahl Du hier eigentlich so klein-klein rechnen musst. Aber die Frage ist nach der 3 leichter zu beantworten.
Wenn die Primfaktorenzerlegung von 101! erst einmal klar ist, ist die Zahl der Teiler sehr leicht zu bestimmen.
Jetzt Du.
Viel Erfolg!
Liebe Grüße,
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:47 Do 22.01.2009 | | Autor: | julmarie |
wow danke... ja umfangreich ist sie wirklich!
|
|
|
|
