Kongruenzrechnung < Wettbewerbe < Schule < Mathe < Vorhilfe
|
| Status: |
(Übungsaufgabe) Übungsaufgabe  | | Datum: | 16:58 Do 12.08.2004 | | Autor: | Stefan |
Lieber Hanno!
Bevor es meine "offiziellen" (d.h. etwas leichteren) Aufgaben zum letzten Thema gibt, hier noch eine Aufgabe für dich zum Knobeln (Bundesrunde):
Es ist zu entscheiden, durch welche der Primzahlen [mm] $\blue{2}$, $\blue{3}$, $\blue{5}$, $\blue{7}$, $\blue{11}$, $\blue{13}$, $\blue{109}$, $\blue{151}$, $\blue{491}$ [/mm] die Zahl
[mm] $\blue{z = 1963^{1965} - 1963}$
[/mm]
teilbar ist.
Liebe Grüße
Stefan
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:46 Do 12.08.2004 | | Autor: | Hanno |
Hiho.
Bevor ich anfange:
Ist es genau eine Primzahl oder sind es mehrere, die durch die genannte Zahl teilbar sind?
Gruß,
Hanno
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:49 Do 12.08.2004 | | Autor: | Stefan |
Lieber Hanno!
Es sind mehrere!
Du musst es für alle entscheiden.
Liebe Grüße
Stefan
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:54 Do 12.08.2004 | | Autor: | Hanno |
Hi Stefan.
Wie sieht das aus, du hast ja die Lösung, ist eine LÖsung mit oder ohne FErmats kleinen Satz gewünscht?
Gruß,
Hanno
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:15 Do 12.08.2004 | | Autor: | Stefan |
Lieber Hanno!
Eigentlich ohne. Du kannst ihn aber gerne verwenden, das ist erlaubt. 
Liebe Grüße
Stefan
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:12 Do 12.08.2004 | | Autor: | Hanno |
Hiho.
Naja, ich versuch's halt mal, scheint machbar:
[mm]1963^{1965}-1963=1963(1963^{1964}-1)[/mm]
Damit ist die Teilbarkeit von 1963 durch die zu prüfende Primzahl schon eine hinreichende Bedingung für die Teilbarkeit durch den gesamten Term.
Daraus können wir
[mm]151\equiv 0\pmod {1963} \gdw 151\equiv 0\pmod {1963^{1965}-1963}[/mm]
[mm]13\equiv 0\pmod {1963} \gdw 13\equiv 0\pmod {1963^{1965}-1963}[/mm]
herleiten, d.h. 13 und 151 sind durch [mm]1963^{1965}-1963[/mm] teilbar.
Nun stellen wir eine Tabelle auf, welche die jeweiligen Modulo für die Primzahlen erhält:
[mm]2\equiv 1\pmod {1963}[/mm]
[mm]3\equiv 1\pmod {1963}[/mm]
[mm]5\equiv 3\pmod {1963}[/mm]
[mm]7\equiv 3\pmod {1963}[/mm]
[mm]11\equiv 5\pmod {1963}[/mm]
[mm]19\equiv 6\pmod {1963}[/mm]
[mm]109\equiv 1\pmod {1963}[/mm]
[mm]491\equiv -1\pmod {1963}[/mm]
Für 2,3 sowie 109 folgt, dass sie Teiler von [mm]1963^{1964}-1[/mm] sind, da ihre Reste 1 sind und sich dieser Wert beim Potenzieren nicht mehr ändert. Durch Subtraktion von 1 ist also [mm]1963^{1964}-1[/mm] und damit auch [mm]1963^{1965}-1963[/mm] ein Vielfaches von ihnen.
Für 491 trifft dies ebenfalls zu, da der Rest nach Potenzieren wegen [mm](-1)^{2n}=1^n=1[/mm] ebenfalls 1 ist und 491 nach obigen Gründen somit ein Teiler von [mm]1963^{1965}-1963[/mm] ist.
Für die 4 verbleibenden Primzahlen entwickeln wir eine Restekette:
Beginnen wir bei 5:
[mm]1963^1\equiv 3\pmod{5}[/mm]
[mm]1963^2\equiv 9\equiv 4\pmod{5}[/mm]
[mm]1963^3\equiv 12\equiv 2\pmod{5}[/mm]
[mm]1963^4\equiv 6\equiv 1\pmod{5}[/mm]
[mm]1963^5\equiv 3\pmod{5}[/mm]
Aus [mm]1965\equiv 1\pmod{4}[/mm] folgt, dass [mm]1963^{1965}\equiv 3\pmod {5}[/mm].
Daraus, und aus der obigen Tabelle, folgt wiederum, dass auch [mm]1963^{1965}-1963[/mm] ein Vielfaches von 5 ist.
Das gleiche führen wir nun für 7 durch:
[mm]1963^1\equiv 3\pmod{7}[/mm]
[mm]1963^2\equiv 9\equiv 2\pmod{7}[/mm]
[mm]1963^3\equiv 6\pmod{7}[/mm]
[mm]1963^4\equiv 18\equiv 4\pmod{7}[/mm]
[mm]1963^5\equiv 12\equiv 5\pmod{7}[/mm]
[mm]1963^6\equiv 15\equiv 1\pmod{7}[/mm]
[mm]1963^7\equiv 3\pmod{7}[/mm]
Da [mm]1965\equiv 3\pmod{6}[/mm], folgt, dass [mm]1963^{1965}\equiv 6\equiv -1\pmod {7}[/mm]
Durch Subtraktion des Restes 3 erhält man für [mm]1963^{1965}-1963[/mm] den Rest [mm]-4[/mm], d.h. 7 ist kein Teiler von [mm]1963^{1965}-1963[/mm].
11:
[mm]1963^1\equiv 5\pmod{11}[/mm]
[mm]1963^2\equiv 25\equiv 3\pmod{11}[/mm]
[mm]1963^3\equiv 15\equiv 4\pmod{11}[/mm]
[mm]1963^4\equiv 20\equiv 9\pmod{11}[/mm]
[mm]1963^5\equiv 45\equiv 1\pmod{11}[/mm]
[mm]1963^6\equiv 5\pmod{11}[/mm]
[mm]1965\equiv 0\pmod{5} \Rightarrow k\cdot 11\not= 1963^{1965}-1963[/mm]
19:
[mm]1963^1\equiv 6\pmod{19}[/mm]
[mm]1963^2\equiv 36\equiv 17\pmod{19}[/mm]
[mm]1963^3\equiv 102\equiv 7\pmod{19}[/mm]
[mm]1963^4\equiv 42\equiv 4\pmod{19}[/mm]
[mm]1963^5\equiv 24\equiv 5\pmod{19}[/mm]
[mm]1963^6\equiv 30\equiv 11\pmod{19}[/mm]
[mm]1963^7\equiv 66\equiv 9\pmod{19}[/mm]
[mm]1963^8\equiv 16\equiv 16\pmod{19}[/mm]
[mm]1963^9\equiv 96\equiv 1\pmod{19}[/mm]
[mm]1963^{10}\equiv 6\equiv 6\pmod{19}[/mm]
[mm]1965\equiv 3\pmod{9} \Rightarrow k\cdot 19\not= 1963^{1965}-1963[/mm]
Hmm, scheint wohl nicht die eleganteste Lösung zu sein, aber das fiel (EDIT: Nanu, kleiner Rechtschreibfehler ;)) mir zuerst ein.
Gruß,
Hanno
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:29 Do 12.08.2004 | | Autor: | Hanno |
Anmerkung:
Irgendwie habe ich mir die Primzahleigenschaft nicht zu nutze gemacht, scheint mir wirklich so, als sei die Lösung zu lang und unelegant.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:58 Do 12.08.2004 | | Autor: | Stefan |
Lieber Hanno!
> Irgendwie habe ich mir die Primzahleigenschaft nicht zu
> nutze gemacht, scheint mir wirklich so, als sei die Lösung
> zu lang und unelegant.
Das stimmt, du hättest doch den kleinen Fermat ausnutzen können (wie du es ja eigentlich tun wolltest  ):
[mm] $a^{p-1} \equiv [/mm] 1 [mm] \pmod{p}$.
[/mm]
Das hast du jedesmal mühsam erst berechnet.
Dann wäre, so finde ich, deine Lösung sogar noch besser gewesen als die "Musterlösung" des Mathe-Olympiade-Verlages.
Liebe Grüße
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:40 Do 12.08.2004 | | Autor: | Hanno |
Hi Stefan.
Ich bin jetzt beim Training, nachher werde ich nochmal schauen.
Bis dann *froiüberrichtigelösung*
Gruß,
Hanno
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:25 Do 12.08.2004 | | Autor: | Stefan |
Lieber Hanno!
Das war aber ein kurzes Training.
Aber das Training hier macht vermutlich eh mehr Spaß.
> Ok, dann eben nicht 19
>
> Für 13 tritt wieder der Fall ein, dass es durch 1963
> teilbar ist, d.h.
> es ist ein Teiler des Terms ;)
![[daumenhoch]](/images/smileys/daumenhoch.gif "[daumenhoch]")
> Damit wäre die aufgabe gelöst *juchei*
Alle Achtung, eine großartige Leistung!!!! Immerhin war das eine Bundesrundenaufgabe für die Stufe 11-13. Wenn du auch alle anderen davon in dieser Geschwindigkeit löst, hast du gute Chancen auf eine gute Platzierung.
> EDIT:
> uuuuund der Beutelspacher ist da @ lineare Algebra
Super! ![[super]](/images/smileys/super.gif "[super]") Ich habe das erste Kapitel schon gelesen, heute morgen im Bus. Aber das ist auch unfair, schließlich habe ich ein Mathestudium hinter mir. Lass dir mehr Zeit, viel mehr Zeit, und lese alles sehr, sehr gründlich. Das ist ganz wichtig!! Auch Sachen, die dir trivial erscheinen, bitte gründlich lesen und alles hinterfragen und überdenken.
Ein Problem: Ich habe eine deutlich ältere Aufgabe als du. Von daher sollten wir die Aufgaben aus deinem Buch nehmen. Zudem hast du Lösungshinweise und ich nicht. Wir können es ja so machen: Du schreibst die Aufgaben, die du lösen willst, hier rein (also alle, hoffe ich ) und gibst dann anschließend als Mitteilung den Lösungshinweis mit an.
Fragen zu dem Buch kannst du natürlich jederzeit stellen, im Uni-LA-Forum.
Liebe Grüße
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:30 Do 12.08.2004 | | Autor: | Hanno |
Hi Stefan.
Warbei der Lehrerin, die für die Olympies zuständig ist, und ich werd wohl mit zur Landesrunde fahren. Damit habe ich mein Ziel schon erreicht ohne was gmahct zu haben ;-D. Nein, mal im Ernst. Vielleicht schaffe ich dort ja ein paar Aufgaben, wär ne klasse Sache.
Und mit dem Buch:
Wenn ich am WE Zeit habe, dann mach ich das. In der Woche ist Schule wichtiger, komme auch immer erst gegen 16:00 nach Hause und dann muss noch gelernt und Hausaufgaben gemacht werden.
Gruß,
Hanno
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:38 Do 12.08.2004 | | Autor: | Hanno |
Hiho.
Nein, die weiß nix. Die hatte mich noch nie in Mathe, die weiß nich dass ich je eine Aufgabe gerechnet habe, die weiß nix. Wenn es gut läuft, und wewnn nich dann auch, dann erzähl ichs ;). Und bei uns sind so wenige in der Region, dass wir eh gleich zur Landesrunde geschleppt werden soweit ich weiß ;)
Und die Landesrunde ist wohl so im Januar.
Gruß,
Hanno
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:02 Do 12.08.2004 | | Autor: | Hanno |
Hiho nochmals.
Ich will da nicht unbedingt vorher falsche Hoffnungen wecken. Ich mach lieber da mein Ding, und wenn es klappt, dann freu ich mich und mein Direktor auch ( tut er sowieso, auch wenn ich nur einen Punkt krieg, so ist der halt ;) ). Naja, aber wenn ich vorher sage dass ich schon so viel geübt habe dann baut sich da gleich so ein kleiner Druck auf und den will ich nicht haben.
Verstehst du doch hoffentlich ,oder?
Gruß,
Hanno
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:06 Do 12.08.2004 | | Autor: | Stefan |
Lieber Hanno!
Klar, verstehe ich das. Ich lasse mich auch nicht gerne unter Druck setzen.
Deine Einstellung ist super: Alles kann, vieles soll, nichts muss.
Liebe Grüße
Stefan
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:09 Do 12.08.2004 | | Autor: | Hanno |
Hiho.
Ganz genau:
alles kann: ich habe mal beide Landespapiere einer Runde gelöst
vieles soll: ich will natürlich ein paar punkte machen
nichts muss: niemand ( ausser mir ) erwartet was von mir
Gruß,
Hanno
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:30 Do 12.08.2004 | | Autor: | Stefan |
Lieber Hanno!
> Immerhin war das
> eine Bundesrundenaufgabe für die Stufe 11-13. Wenn du auch
> alle anderen davon in dieser Geschwindigkeit löst, hast du
> gute Chancen auf eine gute Platzierung.
Ich sollte vielleicht dazu sagen, dass es eine Aufgabe aus dem Jahre 1964 war. Da macht der Ausdruck "Bundesrunde" wenig Sinn. Aber es war halt in der DDR die letzte Runde vor der IMO.
Liebe Grüße
Stefan
|
|
|
|
![[banane]](/images/smileys/banane.gif "[banane]"){kind=small}
![[hot]](/images/smileys/hot.gif "[hot]"){kind=small}
![[respekt2]](/images/smileys/respekt2.gif "[respekt2]"){kind=small}
![[]](http://www.olympiade-mathematik.de/tex/o04_png_l/l_041342.png){kind=small}
http://www.olympiade-mathematik.de/tex/o04_png_l/l_041342.png