matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

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
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenRelationenModulo-Arithmetik
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Relationen" - Modulo-Arithmetik
Modulo-Arithmetik < Relationen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Relationen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Modulo-Arithmetik: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 13:23 Mi 26.09.2007
Autor: Kroni

Aufgabe
Zeigen Sie, dass für jede Primzahl p gilt:

[mm] $(p-1)!\equiv [/mm] -1 [mm] (mod\; [/mm] p)$

Benutze, dass jeder Faktor von $(p-1)!$ in [mm] $\IZ/p$ [/mm] invertierbar ist

Hi,

die Aussage besagt, ja, dass p ein Teiler von $(p-1)!+1$ sein muss. Denn sonst würde die Äuqivalenzrelation $m [mm] \equiv [/mm] n (mod [mm] \; [/mm] o) [mm] \gdw [/mm] o | (m-n)$ nicht stimmen.

Okay, soweit so gut.

Jetzt darf also nach meiner Überlegung [mm] $\frac{(p-1)!+1}{p}$ [/mm] nur eine natürliche Zahl sein, denn sonst gäbe es ja einen Rest.

Jetzt habe ich aber Probleme, das nachzuweisen, bzw. mit der Invertierbarkeit.

Wenn ein Faktor invertierbar ist, dann muss doch gelten:

[mm] $[x]\*[y]=[1]$ [/mm] oder nicht?!

Also kann ich jeden Faktor der Fakultät umschreiben in $[x]=[1/y]$. Wobei ich die 1 noch umschreiben kann in np+1, damit bei der Division durch p noch ein Rest von 1 bleibt, so dass man sich dann in der Äquivalenzklasse 1 befindet.

Jetzt komme ich aber nicht weiter. Wie kann ich das in meinen normalen Bruch einarbeiten?

Ich meine gut, ich weiß, dass dort am Ende irgendetwas wie [p] herauskommen muss, damit der Rest bei der Teilung 0 ergibt, aber ich habe ehrlich gesagt nicht mehr so viel Ahnung, wie ich jetzt weiterkomme.

Gut, wenn ich jetzt meinetwegen den Faktor 1 der Fakultät durch p teile, so kann ich die 1 in die Äq.Klasse [1] packen. Die 2 in die Klasse [2], die 3 in [3] bis p-1 in die [p-1] Klasse.
Dann kann ich das 1/p noch in [1] packen.

Aber was bringt mir das jetzt?!

Kann ich jetzt irgendwie mit der Invertierbarkeit weiterarbeiten? Wenn ja, wie muss ich diese Info verarbeiten?

LG

Kroni



        
Bezug
Modulo-Arithmetik: Antwort
Status: (Antwort) fertig Status 
Datum: 14:02 Mi 26.09.2007
Autor: statler

Hallo Kroni!

> Zeigen Sie, dass für jede Primzahl p gilt:
>  
> [mm](p-1)!\equiv -1 (mod\; p)[/mm]
>  
> Benutze, dass jeder Faktor von [mm](p-1)![/mm] in [mm]\IZ/p[/mm] invertierbar
> ist

> die Aussage besagt, ja, dass p ein Teiler von [mm](p-1)!+1[/mm] sein
> muss.

Genau!

> Denn sonst würde die Äuqivalenzrelation [mm]m \equiv n (mod \; o) \gdw o | (m-n)[/mm]
> nicht stimmen.

Das ist semantischer Käsekram. Aussagen können stimmen oder auch nicht, in Mathe-Speak 'sind wahr' oder 'sind falsch'. Die Aussage 'Diese Relation ist eine Äquiv.-Rel.' kann also z. B. wahr sein. Die Aussage 'Die Äquivalenzrelation stimmt.' ist ähnlich sinnlos wie 'Der Wind ist grün.' Soviel dazu.

Jetzt zur Sache. Versuch mal, in diesem Produkt von 1 bis p-1 die Faktoren danach zu sortieren, ob sie selbstinvers sind oder nicht. Daß sie alle ein Inverses haben, weißt du ja und darfst du verwenden.

Warum heißt es in der Frage 'Sie' und im Hinweis 'du'? :-)

Gruß aus HH-Harburg
Dieter


Bezug
                
Bezug
Modulo-Arithmetik: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 14:08 Mi 26.09.2007
Autor: Kroni

Hi,

das liegt daran, weil ich den Hinweis einfach so hingeschrieben habe, dass dort ein du auftaucht*g*

Also, mit Selbstinvers meinst du, z.B. so etwas wie [1]*[1]=[1]?

D.h. ich muss nach Paaren suchen, die mit sich selbst multipliziert eins oder np+1 ergeben oder?
D.h. es muss gelten [mm] $x^2=np+1$. [/mm]

Aber da kann ich ja auch noch nicht weiterrechnen, da ich nicht weiß, wie groß p ist?!

Achso, PS: Ich habe jetzt noch ein wenig weitergerechnet, und kam dann darauf, dass $[(p-1)!+1]=[p]=[0]$ sein muss.

Also gilt: [(p-1)!+1]=[(p-1)!]+[1]$
Also muss [(p-1)!]=-1 sein?!

LG

Kroni

Bezug
                        
Bezug
Modulo-Arithmetik: Rückfrage
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:16 Mi 26.09.2007
Autor: statler

Was weißt du denn so alles über das Gebilde [mm] \IZ/p? [/mm] Du machst es dir glaubich viel zu schwer mit deinem Ansatz.

Dieter

Bezug
                                
Bezug
Modulo-Arithmetik: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:28 Mi 26.09.2007
Autor: Kroni

Hi,

ich weiß, dass [mm] $\IZ/p$ [/mm] eine Äquivalenzrelation ist. Dort gibt es dann einige Ä-Klassen:

[0] , [1], ... , [p-1].

Es gibt dann inverese, wenn die Zahl der Ä-Klasse teilerfremd mit p ist (das gilt ja für alle Zahlen, da p eine Primzahl ist) und dann gilt:

[x]*[y]=[1].

Aber wie man jetzt genau das Inverse allgemein berechnet weiß ich nicht. Ich kann es nur, wenn eine konkrete Zahl gegeben ist.

Ansonsten weiß ich noch nicht so viel über das Gebilde, außer, dass man dann damit auch rechnen kann wie [x]+[y]=[x+y] etc.
Und wenn mann z.B. im [mm] $\IZ/7$ [/mm] ist, so gilt: [1]=[8]=.. usw.

Mehr weiß ich nicht.

Ich denke mir auch schon, dass es einfacher sein müsste, aber ich habe momentan wirklich keine Ahnung, wie ich die Info, dass alle Faktoren ein Inverses haben, einbauen kann.

LG

Kroni

Bezug
                                        
Bezug
Modulo-Arithmetik: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 14:57 Mi 26.09.2007
Autor: statler


> Hi,
>  
> ich weiß, dass [mm]\IZ/p[/mm] eine Äquivalenzrelation ist.

Nein, das ist nicht die Äquivalenzrelation. Das ist bereits die Menge der Äquivalenzklassen.

> Dort gibt
> es dann einige Ä-Klassen:
>  
> [0] , [1], ... , [p-1].
>  
> Es gibt dann inverese, wenn die Zahl der Ä-Klasse
> teilerfremd mit p ist (das gilt ja für alle Zahlen, da p
> eine Primzahl ist) und dann gilt:
>  
> [x]*[y]=[1].
>  
> Aber wie man jetzt genau das Inverse allgemein berechnet
> weiß ich nicht. Ich kann es nur, wenn eine konkrete Zahl
> gegeben ist.
>  
> Ansonsten weiß ich noch nicht so viel über das Gebilde,
> außer, dass man dann damit auch rechnen kann wie
> [x]+[y]=[x+y] etc.

Das ist ganz wichtig! Man kann auch multiplizieren und prüfen, wann ein Produkt die [0] ergibt. Feststellung: Wenn [x][y] = [0], dann ist [x] = 0 oder [y] = [0]. Die Begründung dafür überlasse ich dir.

Da wir selbstinverse Elemente [x] suchen, müssen wir die Gl. [x][x] = [1] lösen oder [x][x] - [1] = [0] oder (Binomi) ([x] + [1])([x] - [1]) = [0]. Das heißt aber nach dem Vorherigen [x] = [1] oder [x] = -[1] = [p-1]. Jetzt haben wir die beiden selbstinversen El. Alle anderen El. kann ich zu Paaren zusammenfassen, die miteinander multipliziert [1] ergeben. Was bedeutet das jetzt für das zu untersuchende Produkt?

Gruß
Dieter

Bezug
                                                
Bezug
Modulo-Arithmetik: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 15:10 Mi 26.09.2007
Autor: Kroni

Hi,

>
> Das ist ganz wichtig! Man kann auch multiplizieren und
> prüfen, wann ein Produkt die [0] ergibt. Feststellung: Wenn
> [x][y] = [0], dann ist [x] = 0 oder [y] = [0]. Die
> Begründung dafür überlasse ich dir.

Dass man damit so multiplizieren kann etc. haben wir schon bewisen.

>  
> Da wir selbstinverse Elemente [x] suchen, müssen wir die
> Gl. [x][x] = [1] lösen oder [x][x] - [1] = [0] oder
> (Binomi) ([x] + [1])([x] - [1]) = [0]. Das heißt aber nach
> dem Vorherigen [x] = [1] oder [x] = -[1] = [p-1].

Warum genau gilt -[1]=[p-1]?

[1]=[np+1] Also gilt dann -[1]=[-np-1]? Und dann wähle ich n=-1 so dass dann dort [p-1] steht? Kann ich das so begründen?



>Jetzt

> haben wir die beiden selbstinversen El. Alle anderen El.
> kann ich zu Paaren zusammenfassen, die miteinander
> multipliziert [1] ergeben.

Das ist für mich noch nicht genau ersichtlich. Das würde ja bedeuten, dass z.B. die Klassen [2],[3],...,[p-2],[p-1] irgendwo einen Partner haben, so dass es 1 ergibt?
Warum ist dem so?

> Was bedeutet das jetzt für das
> zu untersuchende Produkt?

Okay, wenn es dann immer diese Paare gibt, dann steht dort im Endeffekt im Produkt:

[1]*[1]*[p-1].

Die erste [1] ist die Selbstinverse. Da die restlichen Paare mutlipliziert [1] ergeben kommt dann in der MItte eine [1] hin, die [p+1] ist das letzte Element.

Wenn ich nun [(p-1)!]=[p-1] setze, und dazu dann wie oben schon geschrieben die Klasse [1] addiere, kommt am Ende tatsächlich [p]=[0] heraus.

Aber warum genau haben die sich auf?!

LG

Kroni

>  
> Gruß
>  Dieter


Bezug
                                                        
Bezug
Modulo-Arithmetik: Antwort
Status: (Antwort) fertig Status 
Datum: 15:31 Mi 26.09.2007
Autor: angela.h.b.


> Hi,
>  
> >
> > Das ist ganz wichtig! Man kann auch multiplizieren und
> > prüfen, wann ein Produkt die [0] ergibt. Feststellung: Wenn
> > [x][y] = [0], dann ist [x] = 0 oder [y] = [0]. Die
> > Begründung dafür überlasse ich dir.
>  
> Dass man damit so multiplizieren kann etc. haben wir schon
> bewisen.

Hallo,

ich nehme an, daß Ihr gezeigt habt, daß also [mm] \IZ/p [/mm] ein Körper ist.

>  
> >  

> > Da wir selbstinverse Elemente [x] suchen, müssen wir die
> > Gl. [x][x] = [1] lösen oder [x][x] - [1] = [0] oder
> > (Binomi) ([x] + [1])([x] - [1]) = [0]. Das heißt aber nach
> > dem Vorherigen [x] = [1] oder [x] = -[1] = [p-1].
>  
> Warum genau gilt -[1]=[p-1]?

Es ist [p-1]+[1]=[p-1+1]=[p]=[0], also ist [p-1] das Inverse zu [1] bzgl. der Addition. In Zeichen -[1]=[p-1].


> >Jetzt
> > haben wir die beiden selbstinversen El. Alle anderen El.
> > kann ich zu Paaren zusammenfassen, die miteinander
> > multipliziert [1] ergeben.
>  
> Das ist für mich noch nicht genau ersichtlich. Das würde ja
> bedeuten, dass z.B. die Klassen [2],[3],...,[p-2],[p-1]
> irgendwo einen Partner haben, so dass es 1 ergibt?
>  Warum ist dem so?

Genau, die haben alle solch einen Partner, und das weißt Du, weil Ihr sicher gezeigt habt, daß [mm] \IZ/p [/mm] ein Körper ist.

Du weißt auch, daß unter den genannten Restklassen nur [p-1] selbstinvers ist.
Die andern werden jeweils durch einen von ihnen verschiedenen Partner invertiert, welcher wiederum [2],...,[p-2] entstammt.

Weil es ein Körper ist, werden nicht zwei der Restklassen [2],...,[p-2]  durch ein und denselben Partner invertiert.
Also finden sich hier Paare zusammen.
  

> > Was bedeutet das jetzt für das
> > zu untersuchende Produkt?

(p-1)!= 2*...*(p-2)(p-1)= (Produkt aus zueinander inversen Paaren)(p-1)=...

>  
> Okay, wenn es dann immer diese Paare gibt, dann steht dort
> im Endeffekt im Produkt:
>  
> [1]*[1]*[p-1].

Achso, da steht es ja fast.

Es sind u.U. am Anfang ein Paar Einsen mehr, nämlich [mm] \bruch{p-3}{2} [/mm] Faktoren [1], weil sich ja die p-3 Restklassen  [2],...,[p-2]  in Paaren zusammenschließen.

Gruß v. Angela

Bezug
                                                                
Bezug
Modulo-Arithmetik: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 15:36 Mi 26.09.2007
Autor: Kroni

Hi,

>  
> Hallo,
>  
> ich nehme an, daß Ihr gezeigt habt, daß also [mm]\IZ/p[/mm] ein
> Körper ist.

nein, das haben wir nicht gezeigt. Folglich kann ich deine Arugmentation auch nicht wissen....

>  
> >  

> > >  

> > > Da wir selbstinverse Elemente [x] suchen, müssen wir die
> > > Gl. [x][x] = [1] lösen oder [x][x] - [1] = [0] oder
> > > (Binomi) ([x] + [1])([x] - [1]) = [0]. Das heißt aber nach
> > > dem Vorherigen [x] = [1] oder [x] = -[1] = [p-1].
>  >  
> > Warum genau gilt -[1]=[p-1]?
>  
> Es ist [p-1]+[1]=[p-1+1]=[p]=[0], also ist [p-1] das
> Inverse zu [1] bzgl. der Addition. In Zeichen -[1]=[p-1].

Okay, das glaube ich dann mal so.

>  
>

>  
> Genau, die haben alle solch einen Partner, und das weißt
> Du, weil Ihr sicher gezeigt habt, daß [mm]\IZ/p[/mm] ein Körper
> ist.

Nein, ich weiß noch nicht einmal, was ein Körper ist. (Naja, es ist ja auch "nur" ein Vorkurs Mathematik...)

>  
> Du weißt auch, daß unter den genannten Restklassen nur
> [p-1] selbstinvers ist.

Ja, das haben wir ja gezeigt.

>  Die andern werden jeweils durch einen von ihnen
> verschiedenen Partner invertiert, welcher wiederum
> [2],...,[p-2] entstammt.

Das glaube ich jetzt einfach mal.

>  
> Weil es ein Körper ist, werden nicht zwei der Restklassen
> [2],...,[p-2]  durch ein und denselben Partner invertiert.
>  Also finden sich hier Paare zusammen.
>    
> > > Was bedeutet das jetzt für das
> > > zu untersuchende Produkt?
>  
> (p-1)!= 2*...*(p-2)(p-1)= (Produkt aus zueinander inversen
> Paaren)(p-1)=...
>  
> >  

> > Okay, wenn es dann immer diese Paare gibt, dann steht dort
> > im Endeffekt im Produkt:
>  >  
> > [1]*[1]*[p-1].
>  
> Achso, da steht es ja fast.

Ja.

>  
> Es sind u.U. am Anfang ein Paar Einsen mehr, nämlich
> [mm]\bruch{p-3}{2}[/mm] Faktoren [1], weil sich ja die p-3
> Restklassen  [2],...,[p-2]  in Paaren zusammenschließen.

Ja, aber wenn ich diese einsen Zusammenmultipliziere steht dann dort im großen und Ganzen [1] für die Inversen.


Okay, wenn ich das einfach so hinnehme, kann ich die Diskussion nachvollziehen.
Aber da ich nicht weiß, was ein Körper ist, kann ich die Argumentation nur glauben.

LG

Kroni

>  
> Gruß v. Angela


Bezug
                                                                        
Bezug
Modulo-Arithmetik: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 15:54 Mi 26.09.2007
Autor: angela.h.b.


> Okay, wenn ich das einfach so hinnehme, kann ich die
> Diskussion nachvollziehen.
>  Aber da ich nicht weiß, was ein Körper ist, kann ich die
> Argumentation nur glauben.

Nee, Du mußt dann noch eine zusätzliche Überlegung machen.

Daß jedes Element ein Inverses hat, wurde mitgeteilt.

Daß lediglich (p-1) und 1 selbstinvers sind, hast Du herausgefunden.

Aus der Körpereigenschaft habe ich gefolgert, daß von den verbleibenden p-3 Restklassen nicht 2 durch dasselbe Element invertiert werden.

Der Grund dafür wäre zu überlegen.

Das kannst Du tun, indem Du annimmst, daß zwei durch dasselbe Element invertiert werden und dann zeigst, daß sie in dem Fall gleich sind.

Gruß v. Angela



Bezug
                        
Bezug
Modulo-Arithmetik: Antwort
Status: (Antwort) fertig Status 
Datum: 15:11 Mi 26.09.2007
Autor: angela.h.b.


> Achso, PS: Ich habe jetzt noch ein wenig weitergerechnet,
> und kam dann darauf, dass [mm][(p-1)!+1]=[p]=[0][/mm] sein muss.
>  
> Also gilt: [(p-1)!+1]=[(p-1)!]+[1]$
> Also muss [(p-1)!]=-1 sein?!

Hallo,

ja, wenn Du weißt, daß [(p-1)!+1]=[0] ist, hast Du die Lösung.

Die Frage ist bloß, WIE Du dorthin gekommen bist.


> Also, mit Selbstinvers meinst du, z.B. so etwas wie
> [1]*[1]=[1]?

Genau. Oder wie [(p-1)][p-1]=...

Nun überlege Dir, welche der Elemente [1], [2],...,[p-1] selbstinvers sind.

>  
> D.h. ich muss nach Paaren suchen, die mit sich selbst
> multipliziert eins oder np+1 ergeben oder?

Ja.

Schau Dir dann mal (p-1)! an.

Es ist ja (p-1)!=1*2*...*(p-2)(p-1)=2*...*(p-2)(p-1).

Wieviele Faktoren sind das?
Wieviele davon (und welche) sind nicht selbstinvers?

Unter welchen Zahlen/Restklassen finden diejenigen, die nicht selbstinvers sind, ihren inversen Partner?

Oh - ich sehe gerade, daß Dieter das alles schon geschrieben hat...
Ich lasse es trotzdem stehen. Manchmal sind ja auch geringfügig andere Worte nützlich.

Gruß v. Angela










>  D.h. es muss gelten [mm]x^2=np+1[/mm].
>  
> Aber da kann ich ja auch noch nicht weiterrechnen, da ich
> nicht weiß, wie groß p ist?!
>  
> Achso, PS: Ich habe jetzt noch ein wenig weitergerechnet,
> und kam dann darauf, dass [mm][(p-1)!+1]=[p]=[0][/mm] sein muss.
>  
> Also gilt: [(p-1)!+1]=[(p-1)!]+[1]$
> Also muss [(p-1)!]=-1 sein?!


Bezug
                                
Bezug
Modulo-Arithmetik: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 15:21 Mi 26.09.2007
Autor: Kroni


> > Achso, PS: Ich habe jetzt noch ein wenig weitergerechnet,
> > und kam dann darauf, dass [mm][(p-1)!+1]=[p]=[0][/mm] sein muss.
>  >  
> > Also gilt: [(p-1)!+1]=[(p-1)!]+[1]$
> > Also muss [(p-1)!]=-1 sein?!
>  
> Hallo,
>  
> ja, wenn Du weißt, daß [(p-1)!+1]=[0] ist, hast Du die
> Lösung.
>  
> Die Frage ist bloß, WIE Du dorthin gekommen bist.

Hi,

indem ich aus der Anfangsbedingung gesehen habe, dass p|(p-1)!+1, also muss die Äq.Klasse davon gleich p oder 0 sein.

>  
>
> > Also, mit Selbstinvers meinst du, z.B. so etwas wie
> > [1]*[1]=[1]?
>  
> Genau. Oder wie [(p-1)][p-1]=...

Okay, [p-1][p-1]=[p(p-2)+1] mit n=p-2, also slebstinvers.

>  
> Nun überlege Dir, welche der Elemente [1], [2],...,[p-1]
> selbstinvers sind.

Die 1 und p-1.

>  
> >  

> > D.h. ich muss nach Paaren suchen, die mit sich selbst
> > multipliziert eins oder np+1 ergeben oder?
>  
> Ja.
>  
> Schau Dir dann mal (p-1)! an.
>  
> Es ist ja (p-1)!=1*2*...*(p-2)(p-1)=2*...*(p-2)(p-1).
>
> Wieviele Faktoren sind das?

Wenn ich die 1 mitzähle sinds p-1, ohne die 1 sind es p-2.

> Wieviele davon (und welche) sind nicht selbstinvers?

Da nur zwei Davon selbstinvers sind, sind die restlichen p-3 bzw. p-4 nicht selbstinvers. Alle anderen außer [1] und [p-1] sind nicht selbstinvers.

>  
> Unter welchen Zahlen/Restklassen finden diejenigen, die
> nicht selbstinvers sind, ihren inversen Partner?

Das ist eine sehr gute Frage. Die wirst du wahrscheinlich gerade in deinem anderen Post erklären, aber trotzdem hier noch eine Idee von mir:

Wenn ich z.B. die Klasse [2] habe, dann muss gelten:
[2]*[p-x]=[1]=[np+1]

[2]*[p-x]=[2p-2x] n=2 in diesem Falle, und -2x müsste gleich 1 sein. Das ist aber nur der Fall, wenn x=-0.5 wäre, und [p+0.5] gibt es nicht. Wo ist also der Fehler?!

>  
> Oh - ich sehe gerade, daß Dieter das alles schon
> geschrieben hat...
>  Ich lasse es trotzdem stehen. Manchmal sind ja auch
> geringfügig andere Worte nützlich.

Ja, es hlift mir immer ein wenig weiter.
Aber naja, von selbst wäre ich da nicht drauf gekommen. Ich nehme mal an, dass man so etwas nur dann sieht, wenn man sich damit schon länger beschäftigt?!

LG

Kroni

>  
> Gruß v. Angela
>  
>
>
>
>
>
>
>
>
>
> >  D.h. es muss gelten [mm]x^2=np+1[/mm].

>  >  
> > Aber da kann ich ja auch noch nicht weiterrechnen, da ich
> > nicht weiß, wie groß p ist?!
>  >  
> > Achso, PS: Ich habe jetzt noch ein wenig weitergerechnet,
> > und kam dann darauf, dass [mm][(p-1)!+1]=[p]=[0][/mm] sein muss.
>  >  
> > Also gilt: [(p-1)!+1]=[(p-1)!]+[1]$
> > Also muss [(p-1)!]=-1 sein?!
>  


Bezug
                                        
Bezug
Modulo-Arithmetik: Antwort
Status: (Antwort) fertig Status 
Datum: 15:45 Mi 26.09.2007
Autor: angela.h.b.


> > Unter welchen Zahlen/Restklassen finden diejenigen, die
> > nicht selbstinvers sind, ihren inversen Partner?
>  
> Das ist eine sehr gute Frage. Die wirst du wahrscheinlich
> gerade in deinem anderen Post erklären, aber trotzdem hier
> noch eine Idee von mir:
>  
> Wenn ich z.B. die Klasse [2] habe, dann muss gelten:
>  [2]*[p-x]=[1]=[np+1]
>  
> [2]*[p-x]=[2p-2x] n=2 in diesem Falle, und -2x müsste
> gleich 1 sein. Das ist aber nur der Fall, wenn x=-0.5 wäre,
> und [p+0.5] gibt es nicht. Wo ist also der Fehler?!

Der Fehler ist, daß Du nicht genau unterscheidest, ob Du mit Restklassen oder Zahlen rechnest.

Du suchst nicht ein x so, daß -2x=1 ist, sondern so, daß -[2][x]=[1] ist, oder anders aufgeschrieben

[mm] -2x\equiv [/mm] 1 mod p.

Du suchst somit das Inverse zu -[2]=[p-2] bzgl der Multiplikation.
Aber für die Aufgabe brauchst Du es nicht ausdrücklich zu benennen.Es reicht, daß es vorhanden ist.

Gruß v. Angela



Bezug
                                                
Bezug
Modulo-Arithmetik: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 15:48 Mi 26.09.2007
Autor: Kroni

Hi,

ja, ich glaube schon, dass es zu jedem Element ein Inverses gibt, aber da wir keine Körper hatten kann ich das ja nicht einfach so wissen?!

LG

Kronih

Bezug
                                                        
Bezug
Modulo-Arithmetik: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 15:52 Mi 26.09.2007
Autor: Kroni

Hi,

noch eine Frage:

Wenn ich den Tip jetzt lese: "Benutzen Sie, dass jeder Faktor von (p-1)! in [mm] $\IZ/15$ [/mm] invertierbar ist", ist das damit dann gemeint, dass man in all diesen Klassen zu jeder Klasse eine findet, die mit der multipliziert die Klasse [1] ergibt?

Wenn ja, könnte ich das so begründen ...

LG

Kroni

Bezug
                                                                
Bezug
Modulo-Arithmetik: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 15:57 Mi 26.09.2007
Autor: angela.h.b.


> Hi,
>  
> noch eine Frage:
>  
> Wenn ich den Tip jetzt lese: "Benutzen Sie, dass jeder
> Faktor von (p-1)! in [mm]\IZ/15[/mm] invertierbar ist", ist das
> damit dann gemeint, dass man in all diesen Klassen zu jeder
> Klasse eine findet, die mit der multipliziert die Klasse
> [1] ergibt?
>  
> Wenn ja, könnte ich das so begründen ...

Haargenauso ist das gemeint. muß natürlich in [mm] \IZ/p [/mm] heißen.

Gruß v. Angela

Bezug
                                                                        
Bezug
Modulo-Arithmetik: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 16:00 Mi 26.09.2007
Autor: Kroni

Hi,

okay....

Dann muss ich also nur zeigen, dass es zu jedem Element genau ein anderes Element gibt, das mit dem Element multipliziert [1] ergibt. Ich muss also zeigen, wie du schon sagtest, dass zwei Elemente gleich sind, wenn sie mit dem selben Element mutlipliziert 1 ergeben:

[x]*[y]=[1]
[z]*[y]=[1]

Daraus folgt:

[x]=[1/y] (kann ich ja so schrieben, da sie invertierbar sind)
[z]=[1/y]=[x] q.e.d.

Geht das so einfach?

LG

Kroni

Bezug
                                                                                
Bezug
Modulo-Arithmetik: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 18:28 Mi 26.09.2007
Autor: angela.h.b.


> [x]*[y]=[1]
> [z]*[y]=[1]
>  
> Daraus folgt:
>  
> [x]=[1/y] (kann ich ja so schrieben, da sie invertierbar
> sind)
>  [z]=[1/y]=[x] q.e.d.
>  
> Geht das so einfach?

Nein, leider nicht.

Denn unter z.B. [mm] [\bruch{1}{4}] [/mm]  kann ich mir nichts vorstellen - schon gar nicht etwas, was zu den Restklassen modulo p paßt.

> [x]*[y]=[1]
> [z]*[y]=[1]

=>[xy]=[1] und [zy]=[1]

Also sind xy und zy in deselben Restklasse modulo p, d.h. [xy]-[zy]=[0], also [xy-zy]=[0].

Also läßt xy-zy=(x-z)y bei Division durch p den Rest 0.

Folglich gibt es ein n mit (x-z)y=np.

Nun mußt Du Dir überlegen, daß p  y oder x-z teilt und die Konsequenzen daraus ziehen.

Gruß v. Angela

Bezug
                                                                                        
Bezug
Modulo-Arithmetik: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 16:13 Do 27.09.2007
Autor: Kroni

Hi,

okay, werde mal die Tage darüber nachdenken.

Die Sache, dass es dann aber immer nur paare gibt, wurde bei uns auch so rein logisch vorrausgesetzt in der Übung, so dass wir theoretisch den Beweis nicht explizit geben müssten.

Aber ich werde später noch einmal darüber nachdenken=)

An alle Helfer: Vielen Dank für eure Hilfe =) Finds toll, dass einem hier immer so gut geholfen wird =)

LG

Kroni

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


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]