44. IMO - (c) < Internationale MO < Wettbewerbe < Schule < Mathe < Vorhilfe
|
| Status: |
(Übungsaufgabe) Übungsaufgabe  | | Datum: | 11:31 So 29.08.2004 | | Autor: | Hanno |
Es sei $p$ eine Primzahl. Man beweise, dass eine Primzahl $q$ existiert, so dass für jede ganze Zahl $n$ der Ausdruck [mm] $n^p-p$ [/mm] nicht durch $q$ teilbar ist!
Gruß,
Hanno
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:26 Do 02.09.2004 | | Autor: | Hanno |
Hiho.
[mm] $n^p-p=n\cdot n^{p-1}-p\equiv n-p\equiv n\pmod [/mm] {p}$
(Dabei habe ich Fermats kleinen Satz [mm] $n^{p-1}\equiv 1\pmod{p}$ [/mm] angewandt (mit "primem" $p$)).
Dann darf es doch keine Lösung für die Gleichung
[mm] $x\cdot p+n\not= y\cdot [/mm] q$
geben?!
Aber wie kann das sein? Schließlich kann ich doch das $n$ so wählen, dass die linke Seite auf jeden Fall durch $q$ zu teilen ist?!
EDIT:
Hm, ich habe meinen Denkfehler gefunden - x selber ist ja eine Funktion von n und nicht konstant.
Dennoch: vielleicht hilft es ja jemandem weiter. *Anfeuer* Los stefan 
Gruß,
Hanno
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:58 Fr 03.09.2004 | | Autor: | Stefan |
Lieber Hanno!
Danke, dass du mich anfeuerst, das ist nett von dir ,aber ich habe ein Problem:
Ich bin leider zu dumm für diese IMO-Aufgaben. ![[wein]](/images/smileys/wein.gif "[wein]")
Ehrlich, bei euch besteht ja noch Hoffnung, dass ihr dieses Niveau eines Tages erreicht, bei mir ist das völlig aussichtslos. Ich werde mathematisch im Laufe der Zeit, spätestens seit dem Ende meines Studiums, ja eher schlechter als besser... Klar, den Höhepunkt der mathematischen Fähigkeit erlangt man bekanntlich mit Anfang, Mitte 20. Danach baut man kontinuierlich ab und zehrt nur noch von der Erfahrung.
Ich habe die Aufgaben versucht, bekomme sie aber nicht hin. Ich denke, die Bundesrunde würde ich mir noch zutrauen (die Aufgaben bekomme ich ja meistens dann doch noch hin, von den Geometrie-Aufgaben mal abgesehen  ), aber dann ist Feierabend bei mir. :-(
Was ich dir anbieten kann: Ich habe Zugriff auf die Lösungen. Wenn du möchtest, lese ich sie mir durch, versuche sie zu verstehen (was schwierig genug sein wird) und gebe euch Tipps. Was hältst du davon?
Liebe Grüße
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:25 Fr 03.09.2004 | | Autor: | Hanno |
Hi Stefan!
Die Idee mit den LÖsungen wäre klasse, dann ginge das hier mal voran und du könntest bald wieder deine schaffbaren Aufgaben stellebn
Ich muss zugeben, dass das nicht so toll war von mir, hier solche Kracher zu posten.
Gruß,
Hanno
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:32 Mi 08.09.2004 | | Autor: | Stefan |
Lieber Hanno, lieber Paul, liebe Jan, liebe sonstige Interessierte!
Wie versprochen, hier ein kleiner Tipp. Natürlich bin ich selbst darauf gekommen. Nein, Quatsch, ich habe es bei den Musterlösungen nachgeschaut.
Es gilt:
[mm] [center]$\frac{p^p-1}{p-1} [/mm] = 1 + p + [mm] p^2 [/mm] + [mm] \ldots [/mm] + [mm] p^{p-1} \equiv [/mm] p+1 [mm] \pmod{p^2}$.[/center]
[/mm]
Daraus folgt: Es gibt mindestens einen Primteiler $q$ von [mm] $\frac{p^p-1}{p-1}$, [/mm] der nicht kongruent zu $1$ modulo [mm] $p^2$ [/mm] ist (klar, denn sonst wäre ja auch [mm] $\frac{p^p-1}{p-1}$ [/mm] kongruent zu $1$ modulo [mm] $p^2$).
[/mm]
Wir wollen nun zeigen, dass dieses $q$ die gewünschte Eigenschaft hat.
Nehmen wir also an es gäbe ein $n [mm] \in \IZ$ [/mm] mit
[mm] [center]$n^p \equiv [/mm] p [mm] \pmod{q}$.[/center]
[/mm]
Dann wäre
(1) [mm] $n^{p^2} \equiv p^p \equiv [/mm] 1 [mm] \pmod{q}$,
[/mm]
gemäß der Definition von $q$.
Andererseits gilt nach dem "kleinen Fermat":
(2) [mm] $n^{q-1} \equiv [/mm] 1 [mm] \pmod{q}$.
[/mm]
Wegen [mm] $p^2 \not\vert [/mm] (q-1)$ gilt:
[mm] [center]$\ggT(p^2,q-1)=p$,[/center]
[/mm]
also (aus (1) und (2)):
[mm] [center]$n^p \equiv [/mm] 1 [mm] \pmod{q}$.[/center]
[/mm]
Wegen [mm] $n^p \equiv [/mm] p [mm] \pmod{q}$ [/mm] folgt also:
$p [mm] \equiv [/mm] 1 [mm] \pmod{q}$.
[/mm]
Frage an euch (ab jetzt kann man es hinkriegen, sogar jemand wie ich ):
Wer schafft es jetzt den Beweis zu Ende zu führen?
Liebe Grüße
Stefan
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:49 Mi 08.09.2004 | | Autor: | Hanno |
Hi Stefan.
Ich habe eine kleine Idee:
Nehmen wir an, p sei eine Primzahl größer als 2. Dann ist der Ausdruck
[mm]\frac{p^{p}-1}{p-1}[/mm] ungerade (das sieht man an der Reihendarstellung recht gut - $1+p$ ist gerade, alle anderen Glieder nicht). Dennoch müsste ja, wenn es ein $n$ mit [mm] $n^p\equiv p\pmod [/mm] {q}$ gäbe, [mm] $p\equiv 1\pmod [/mm] {q}$ gelten. Daraus folgt jedoch, dass $q$ gerade und somit die Zwei sein muss. Das widerspricht allerdings der Annahme, dass $q$ ein Primteiler von [mm] $\frac{p^{p}-1}{p-1}$ [/mm] ist.
D.h. also, dass für [mm] $p\geq [/mm] 2$ kein $n$ mit der geforderten Eigenschaft existiert - es gibt also auf jeden Fall ein $q$, welches nicht als [mm] $(n^p)-p$ [/mm] dargestellt werden kann.
Bleibt der Fall $p=2$ zu prüfen. Folglich müsste $q$ ein Primteiler von [mm] $\frac{2^{2}-1}{2-1}=3$ [/mm] sein. Dafür kommen nur die Zwei und die Drei in Frage, wobei die Zwei wegen [mm] $p\equiv 1\pmod{q}$ [/mm] nicht in Frage kommt.
Schauen wir uns nun [mm] $n^2-2=3\cdot [/mm] k$ genauer an. Wenn $n$ den Dreierrest 1 hat, dann auch [mm] $n^2$. [/mm] Folglich ist [mm] $n^2-2\equiv 2\pmod [/mm] {3}$. Ein solches $n$ erfüllt die Gleichung also keinesfalls. Gilt [mm] $n\equiv 0\pmod{3}$ [/mm] so gilt [mm] $n^2-2\equiv 1\pmod [/mm] {3}$ was ebenfalls bedeutet, dass keine Lösung existiert. Für [mm] $n\equiv 2\pmod [/mm] {3}$ gilt allerdings wieder [mm] $n^2\equiv 1\pmod [/mm] {3}$ und daher abermals [mm] $n^2-2\equiv 2\pmod{3}$. [/mm] Es gibt also kein $n$, welches die Gleichung erfüllt.
Damit wäre die Aufgabe meiner Meinung nach gelöst. Ich hoffe, dass es so stimmt, bin ein wenig müde ..
Gruß,
Hanno
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:54 Mi 08.09.2004 | | Autor: | Stefan |
Lieber Hanno!
Ich konnte an deinem Beweis keinen Fehler entdecken, aber er ist ein wenig umständlich.
Einfacher geht es so:
Nach Konstruktion von $q$ ist einerseits:
[mm] $\frac{p^p-1}{p-1} \equiv [/mm] 0 [mm] \pmod{q}$,
[/mm]
andererseits aber wegen $p [mm] \equiv [/mm] 1 [mm] \pmod{q}$:
[/mm]
[mm] $\frac{p^p-1}{p-1} \equiv 1+p+\ldots [/mm] + [mm] p^{p-1} \equiv [/mm] p [mm] \pmod{q}$.
[/mm]
Demzufolge müsste
$p [mm] \equiv [/mm] 0 [mm] \pmod{q}$
[/mm]
sein, im Widerspruch zu $p [mm] \equiv [/mm] 1 [mm] \pmod{q}$.
[/mm]
Damit ist diese Aufgabe gelöst. Wie fandest du den Schwierigkeitsgrad, Hanno?
Für mich ist das mindestens eine Liga zu hoch...
Liebe Grüße
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:57 Mi 08.09.2004 | | Autor: | Hanno |
Hi Stefan.
Hm ja ;) Also der Schwierigkeitsgrad war eindeutig zu hoch.
Allein schon auf die Idee zu kommen, dass mit der geometrischen Reihe in Verbindung zu bringen, ist eine Kunst.
Ich bleibe vorerst bei meinen Landes- und Bundesrundenaufgaben - oder niedriger.
Gruß,
Hanno
|
|
|
|
