Aufgabe #65 (IrMO),(ZT) < MO andere Länder < Wettbewerbe < Schule < Mathe < Vorhilfe
|
| Status: |
(Übungsaufgabe) Übungsaufgabe  | | Datum: | 12:43 Mo 18.07.2005 | | Autor: | Hanno |
Hallo an alle!
Für eine positive, ganze Zahl $n$ bezeichne $a(n)$ die Anzahl der Teiler von $n$.
Man finde alle positiven, ganzen Zahlen $n$, für die [mm] $a(n)^4=n$ [/mm] gilt.
Liebe Grüße,
Hanno
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 01:06 Di 19.07.2005 | | Autor: | jbulling |
Hallo Hanno,
ich habe einen Ansatz, aber leider keine Komplette Lösung :o(
Sei
[mm] n:=\produkt_{i=1}^m{p_i^s_i}
[/mm]
Die kanonische Primfaktordarstellung von n mit m [mm] \in \IN
[/mm]
Dann iglt
[mm] a(n):=\produkt_{i=1}^m{s_i+1}
[/mm]
Da [mm] a(n)^4=n [/mm] muss n also für jedes 1<= i <= m gelten:
4 | [mm] s_i
[/mm]
Damit ist a(n) ungerade und es gilt
a(n) [mm] \equiv [/mm] 1 (4)
Damit erhält man als gültige Lösungen die Zahlen 1 (Teiler 1), [mm] 5^4 [/mm] (Teiler 1, 5, [mm] 5^2, 5^3, 5^4) [/mm] und [mm] 9^4 [/mm] (Teiler 1, 3, [mm] 3^2,..., 3^8).
[/mm]
Ich vermute, dass es darüber hinaus keine weiteren Lösungen mehr gibt. Kann das aber im Moment noch nicht beweisen.
Gruß
Jürgen
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:30 Di 19.07.2005 | | Autor: | Hanno |
Hallo Jürgen!
Dein Ansatz ist richtig, doch es gibt noch, wenn ich mich recht entsinne, genau ein weiteres Lösungspaar, welches die Bedingung erfüllt.
Verfolge mal deinen Ansatz weiter, er ist nicht so verkehrt.
Liebe Grüße,
Hanno
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:12 Di 19.07.2005 | | Autor: | jbulling |
Hallo Hanno,
Du hast recht. Es gibt die folgenden Lösungen:
[mm] 1^4, 5^4, 9^4 [/mm] und [mm] 45^4.
[/mm]
Den Beweis kann ich momentan aus Zeitgründen nicht hereinschreiben. Hole ich aber nach :o)
Man kann die Sache sehr vereinfachen, indem man nur die Lösungen sucht, für die n eine Primzahl ist. Für jede Potenz einer zusammengesetzten Zahl, die die Bedingung erfüllt, kann man nämlich für ihre Primfaktoren ebenfalls eine Lösung angeben, da a(n) eine multiplikative zahlentheoretische Funktion ist.
Das heisst, dass für jede Zahl der Form
[mm]n=p_1^{n_1} * p_2^{n_2} * ... * p_m^{n_m}[/mm]
gilt
[mm]a(n)=a(p_1^{n_1}) * a(p_2^{n_2}) * ... * a(p_m^{n_m})[/mm]
wie man durch Induktion nach m beweisen kann.
Gruß
Jürgen
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:00 Di 19.07.2005 | | Autor: | Hanno |
Hallo Jürgen!
Ja, deine Lösungen sind die einzigen!
Liebe Grüße,
Hanno
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:57 So 24.07.2005 | | Autor: | jbulling |
Hallo zusammen,
ich hab versucht das zu vervollständigen, habs leider aber noch nicht geschafft. Ich bin von einer Annahme ausgegangen, die aber leider doch nicht so einfach zu beweisen ist, wie ich dachte.
Ich wollte zeigen, dass für [mm]n:= \prod_{i=1}^m p_i^{a_i}[/mm] gilt
[mm] a(n)^4=n \gdw a(p_i^{a_i})^4=p_i^{a_i} [/mm] für alle i
Das habe ich aber noch nicht hin bekommen :o(
Wenn das nämlich bewiesen ist, dann kann man sich darauf beschränken, zu zeigen, dass es keine weiteren Primzahlen p gibt für die gilt
[mm] a(p^m)^4=p^m [/mm] für ein m [mm] \in \IN
[/mm]
was man dann mit Induktion zeigen kann.
Sei [mm] n=p^m [/mm] und p [mm] \ge [/mm] 3 (p ist ungerade).
Es gilt dann [mm] a(p^m)=m+1 [/mm] denn p ist eine Primzahl.
Wegen [mm] a(p^m)^4=p^m=(m+1)^4 [/mm] muß gelten, dass m durch 4 teilbar ist. Sei k [mm] \in \IN [/mm] so gewählt, dass gilt m=4k, dann kann man die Gleichung umschreiben in:
[mm] a(p^m)^4=p^m [/mm] = [mm] a(p^4k)^4=p^4k=(4k+1)^4
[/mm]
wenn man die vierte Wurzel zieht erhält man:
[mm] a(p^4k)=p^k=(4k+1)
[/mm]
damit kann man mit Induktion nach k zeigen, dass für alle Primzahlen > 5 keine Lösungen exisitieren, denn es gilt dann
[mm] p^1=p [/mm] > 4+1=5
und wenn für k [mm] \ge [/mm] 1 gilt
[mm] p^k>(4k+1)
[/mm]
dann gilt auch
[mm] p^{k+1}=p*p^k [/mm] > p(4k+1) > 4pk + 1 > 4k + 4 +1=4(k+1)+1
Für 3 und 5 kann damit auch beweisen, dass es keine weiteren Exponenten m [mm] \in \iN [/mm] gibt, für die gilt [mm] a(3^m)^4=3^m [/mm] bzw. [mm] a(5^m)^4=5^m
[/mm]
Nur der Teil mit der Äquivalenz der beiden Aussagen oben fehlt noch :(
Es reicht oben natürlich aus zu zeigen, dass die Implikation [mm] \Rightarrow [/mm] gilt. Die andere Richtung ist zwar leicht zu beweisen, aber nicht erforderlich.
Gruß
Jürgen
|
|
|
| |
|
Hallo Hanno.
> Für eine positive, ganze Zahl [mm]n[/mm] bezeichne [mm]a(n)[/mm] die Anzahl
> der Teiler von [mm]n[/mm].
>
> Man finde alle positiven, ganzen Zahlen [mm]n[/mm], für die [mm]a(n)^4=n[/mm]
> gilt.
Sei [mm]p_1^{4k_1}p_2^{4k_2}...p_n^{4k_n}[/mm] die Primfaktordarstellung von n.
Es soll gelten [mm]p_1^{4k_1}p_2^{4k_2}...p_n^{4k_n}=(4k_1+1)^4(4k_2+1)^4...(4k_n+1)^4[/mm]
[mm]\Leftrightarrow p_1^{k_1}p_2^{k_2}...p_n^{k_n}=(4k_1+1)(4k_2+1)...(4k_n+1)[/mm]
Die rechte Seite ist nicht durch 2 teilbar, daher kommt die 2 nicht als Primfaktor von n in Frage.
Links und rechts stehen n Faktoren.
Gibt es ein [mm]i[/mm] mit [mm]p_i^{k_i}>(4k_i+1)[/mm], so muss es auch ein j mit [mm]p_j^{k_j}<(4k_j+1)[/mm] geben (sonst wäre der linke Term größer als der rechte). Ersteres ist für [mm]p_i=3, k_i>2[/mm], [mm]p_i=5, k_i \ge 2[/mm], [mm]p_i>5, k_i\ge 1[/mm] der Fall.
Für eine Primzahl [mm]p_i \ge 5[/mm] mit [mm]k_i \ge 2[/mm] ist [mm]p_i^{k_i} \ge \frac{25}{9}(4k_i+1)[/mm].
[mm]p_j^{k_j}<(4k_j+1)[/mm] ist nur für [mm]p_j=3[/mm] und [mm]k_j=1[/mm] erfüllt, wobei [mm]p_j^{k_j}=\frac{3}{5}(4k_j+1)[/mm]
Es folgt, dass n um mindestens den Faktor [mm]\frac{25}{9}\cdot{}\frac{3}{5}=\frac{5}{3}[/mm] größer wäre als a(n).
Kommt in der Primfaktorzerlegung eine Primzahl größer 5 vor, so auch automatisch ein Faktor [mm](4k_i+1)[/mm], der ein Vielfaches dieser Primzahl ist, woraus folgt, dass [mm]k_i>2[/mm]. Da die entsprechende Primzahl [mm]p_i[/mm] min. 5 sein muss (wäre sie 3, so wäre der linke Term wiederum größer) gelangt man wieder zu obiger Situation.
Es folgt, dass nur die Primfaktoren [mm]p_1=3[/mm] und [mm]p_2=5[/mm] vorkommen dürfen, und dass stets gilt [mm]p_i^{k_i}=(4k_i+1)[/mm].
Es ergeben sich die Lösungen:
[mm]k_1=2,k_2=0[/mm]
[mm]k_1=0,k_2=1[/mm]
[mm]k_1=2,k_2=1[/mm]
Die entsprechenden n sind:
[mm]3^8,5^4,3^8\cdot{}5^4[/mm]
Zugegeben, das ist etwas umständlich.
MfG
Jan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:31 So 14.08.2005 | | Autor: | Stefan |
Hallo Jan!
Die Lösung ist schon ziemlich genial! ![[respekt]](/images/smileys/respekt.gif "[respekt]")
Liebe Grüße
Stefan
|
|
|
|
