Schubfachprinzip < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:09 Sa 11.12.2010 | | Autor: | Splish |
| Aufgabe | Seien [mm] a,m \in \{0;1\} [/mm] zwei teilerfremde natürliche Zahlen.
Zeigen Sie: es gibt eine natürliche Zahl k, [mm] 1\le k \le {m-1}[/mm], für die bei [mm] a^k [/mm] bei Division durch m den Rest 1 lässt (man schreibe dafür [mm] a^k \equiv [/mm] 1 mod m).
Verwenden Sie das "Schubfachprinzip" und keine anderen Sätze aus der Zahlentheorie, wie den Satz von EUler oder den kleinen Satz von Fermat. |
Hallo liebe Boardler,
ich sitz nun hier bei der Vorbereitung auf einen Test und komme bei dieser Aufgabe nicht weiter.
Meine Überlegungen sehen wie folgt aus:
da es heißt, dass [mm] a^k [/mm] mod m, bei k's gegebenen Eigenschaften, 1 ergeben soll, habe ich mir gedacht, dass die Anzahl der Restklasse prima geeignet wären als Schubfächer. In meinem Fall wäre das dann maximal m-1 da die Restklasse [0] rausfällt, da die beiden ja teilerfremd sind, oder?
Meine Elemente die ich habe sind dann wie gegeben [mm] a^k [/mm] wobei k ja dann zwischen 0 und m liegen soll, ich also m-1 möglichkeiten habe [mm] a^k [/mm] zu bilden.
Nun habe ich dann also m-1 Schubfächer und m-1 Elemente. Also könnte alles schön verteilt sein.
Nun zu meinem Problem:
Wer sagt mir, dass es so ist? Warum kann in der [1] nicht mehr als 1 oder garkein Element enthalten sein und wie kann ich das Zeigen?
Das Beispiel auf Wiki habe ich mir schon angeschaut, das ist auch wirklich logisch, da davon ausgegangen wird, dass wenn ich mehr Elemente als Schubfächer habe, ich automatisch bei der Verteilung in einem Fach mindestens 2 Elemente packen muss.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ich würd mich sehr über eure Hilfe freuen.
LG Lars
|
|
| |
|
Hallo Splish,
vorweg: bei a,m [mm] \in \{0;1\} [/mm] hast du dich verschrieben, oder? Sonst macht der Rest wirklich keinen Sinn.
Mein erster Gedanke war:
Naja, nimm einfach an, dass es eine Restklasse gibt, in der 2 Potenzen drin liegen und führe das zum Widerspruch --> dann muss ja in jeder Restklasse genau eins drin liegen.
Daran bin ich mehrfach gescheitert, und jetzt hab ich auch ein einfaches Gegenbeispiel gegen diese Idee:
a = 3, m = 4
[mm] 3^{1} \equiv [/mm] 3 mod 4
[mm] 3^{2} \equiv [/mm] 1 mod 4 (--> Behauptung stimmt also)
[mm] 3^{3} \equiv [/mm] 3 mod 4
Hier ist also eine Restklasse nicht besetzt, dafür eine andere doppelt. Das wird bei jedem geraden m so sein, wenn a ungerade ist - dann kann halt nie ein gerader Rest bleiben. Wenn du m=8 statt m=4 wählst, dann gibt es nur die Reste 1 und 3 - also werden nur 2 von möglichen 7 Restklassen (0 kann man ja vernachlässigen) besetzt.
Auf diese Schubladen kann das Schubladenprinzip also nicht ohne weiteres angewendet werden, aber es sind natürlich die logischsten.
Vielleicht bringen dich meine Überlegungen auf eine neue Idee, ich bin nicht beweis-kreativ genug dafür....
lg weightgainer
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:13 Sa 11.12.2010 | | Autor: | abakus |
> Seien [mm]a,m \in \{0;1\}[/mm] zwei teilerfremde natürliche
> Zahlen.
> Zeigen Sie: es gibt eine natürliche Zahl k, [mm]1\le k \le {m-1}[/mm],
> für die bei [mm]a^k[/mm] bei Division durch m den Rest 1 lässt
> (man schreibe dafür [mm]a^k \equiv[/mm] 1 mod m).
> Verwenden Sie das "Schubfachprinzip" und keine anderen
> Sätze aus der Zahlentheorie, wie den Satz von EUler oder
> den kleinen Satz von Fermat.
Hallo,
angenommen, der Rest 1 tritt nicht auf. Dann muss es zwei Potenzen [mm] a^c [/mm] und [mm] a^d [/mm] geben, bei denen für [mm]1\le c
Dann ist die Differenz [mm] a^d-a^c [/mm] durch m teilbar.
Also:
[mm] a^d-a^c=a^c(a^{d-c}-1)ist [/mm] durch m teilbar.
Da a und m teilerfremd sind, ist der Faktor [mm] a^c [/mm] NICHT durch m teilbar.
Folgerung???
Gruß Abakus
> Hallo liebe Boardler,
> ich sitz nun hier bei der Vorbereitung auf einen Test und
> komme bei dieser Aufgabe nicht weiter.
> Meine Überlegungen sehen wie folgt aus:
> da es heißt, dass [mm]a^k[/mm] mod m, bei k's gegebenen
> Eigenschaften, 1 ergeben soll, habe ich mir gedacht, dass
> die Anzahl der Restklasse prima geeignet wären als
> Schubfächer. In meinem Fall wäre das dann maximal m-1 da
> die Restklasse [0] rausfällt, da die beiden ja teilerfremd
> sind, oder?
> Meine Elemente die ich habe sind dann wie gegeben [mm]a^k[/mm]
> wobei k ja dann zwischen 0 und m liegen soll, ich also m-1
> möglichkeiten habe [mm]a^k[/mm] zu bilden.
> Nun habe ich dann also m-1 Schubfächer und m-1 Elemente.
> Also könnte alles schön verteilt sein.
>
> Nun zu meinem Problem:
> Wer sagt mir, dass es so ist? Warum kann in der [1] nicht
> mehr als 1 oder garkein Element enthalten sein und wie kann
> ich das Zeigen?
> Das Beispiel auf Wiki habe ich mir schon angeschaut, das
> ist auch wirklich logisch, da davon ausgegangen wird, dass
> wenn ich mehr Elemente als Schubfächer habe, ich
> automatisch bei der Verteilung in einem Fach mindestens 2
> Elemente packen muss.
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
> Ich würd mich sehr über eure Hilfe freuen.
>
> LG Lars
>
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:25 Sa 11.12.2010 | | Autor: | Splish |
Hallo ihr beiden und danke für die Antwort,
also weightgainer hat natürlich recht... nicht Element {0;1} sonder [mm] a,b \in \IN \backslash \{0;1\} [/mm] sry dafür.
Nun zu abakus, daraus muss folgen, dass [mm] (a^{d-c} [/mm] -1) teilbar m ist und das gilt für die Restklassen von [mm] [a^0]\equiv [1] [/mm] Woraus folgt dass d=c. So in etwa?
Gruß Lars
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:49 Sa 11.12.2010 | | Autor: | abakus |
> Hallo ihr beiden und danke für die Antwort,
>
> also weightgainer hat natürlich recht... nicht Element
> {0;1} sonder [mm]a,b \in \IN \backslash \{0;1\}[/mm] sry dafür.
>
> Nun zu abakus, daraus muss folgen, dass [mm](a^{d-c}[/mm] -1)
> teilbar m ist und das gilt für die Restklassen von
> [mm][a^0]\equiv [1][/mm] Woraus folgt dass d=c. So in etwa?
Oder, da [mm] c
Gruß Abakus
>
> Gruß Lars
|
|
|
| |
|
> Hallo ihr beiden und danke für die Antwort,
>
> also weightgainer hat natürlich recht... nicht Element
> {0;1} sonder [mm]a,b \in \IN \backslash \{0;1\}[/mm] sry dafür.
>
> Nun zu abakus, daraus muss folgen, dass [mm](a^{d-c}[/mm] -1)
> teilbar m ist und das gilt für die Restklassen von
> [mm][a^0]\equiv [1][/mm] Woraus folgt dass d=c. So in etwa?
>
Eher nein - denn wenn [mm]a^{d-c}-1 \equiv\ 0\ mod\ m[/mm] ist, dann kannst du auf beiden Seiten 1 addieren und erhälst das, was du eigentlich haben willst, nämlich [mm]a^{d-c} \equiv\ 1\ mod\ m[/mm], also gibt es einen Exponenten (hier d-c), für den bei der Division der Rest 1 bleibt.
Nutzung des Schubfachprinzips: Du nimmst an, es gibt in der Schublade "1" kein Element, dann muss es in zumindest einer anderen mind. 2 Elemente geben. Aber dann kann man auf gezeigtem Weg ein Element finden, das den Rest 1 hat, also ist die Annahme, dass in dieser Restklasse nix drin ist, falsch.
Sehr schöne Idee...
> Gruß Lars
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:12 Sa 11.12.2010 | | Autor: | Splish |
Sehr schön erklärt :) das bringt mir was :) vielen dank!
LG Lars
|
|
|
|
