www.matheraum.de
Das Matheforum.
Das Matheforum des MatheRaum.

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenDiskrete MathematikSchubfachprinzip
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
Forum "Diskrete Mathematik" - Schubfachprinzip
Schubfachprinzip < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Schubfachprinzip: Ladehemmung an einer Stelle
Status: (Frage) beantwortet Status 
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


        
Bezug
Schubfachprinzip: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 13:50 Sa 11.12.2010
Autor: weightgainer

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


Bezug
        
Bezug
Schubfachprinzip: Antwort
Status: (Antwort) fertig Status 
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
>  


Bezug
                
Bezug
Schubfachprinzip: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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

Bezug
                        
Bezug
Schubfachprinzip: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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


Bezug
                        
Bezug
Schubfachprinzip: Antwort
Status: (Antwort) fertig Status 
Datum: 16:50 Sa 11.12.2010
Autor: weightgainer


> 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


Bezug
                                
Bezug
Schubfachprinzip: vielen dank
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 18:12 Sa 11.12.2010
Autor: Splish

Sehr schön erklärt :) das bringt mir was :) vielen dank!

LG Lars

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Diskrete Mathematik"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheforum.net
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]