satz von euler < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:21 Sa 25.12.2010 | | Autor: | Bodo0686 |
| Aufgabe | | Zeige [mm] \forall [/mm] a [mm] \in \IZ: a^{1728}\equiv [/mm] 1 mod 1729 |
Hallo,
offensichtlich ist dies ja für a=1 erfüllt... Aber wie zeige ich, dass nun für alle a? Grüße
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:54 Sa 25.12.2010 | | Autor: | felixf |
Moin!
> Zeige [mm]\forall[/mm] a [mm]\in \IZ: a^{1728}\equiv[/mm] 1 mod 1729
>
> offensichtlich ist dies ja für a=1 erfüllt... Aber wie
> zeige ich, dass nun für alle a? Grüße
Das ist aber ziemlich mager. Sonst faellt dir da gar nichts zu ein?
Ohne zu wissen was du schon in der VL hattest und ohne weitere Anstrengungen von dir weiss ich nicht, wie wir dir da weiterhelfen sollen...
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:00 Sa 25.12.2010 | | Autor: | Bodo0686 |
Also wir hatten:
[mm] \forall [/mm] a [mm] \in \IZ: a^{n-1}\equiv [/mm] 1 mod n [mm] \gdw [/mm] n ist quadratfrei und für jedes p [mm] \in \IP [/mm] aus p|n auch p-1|n-1
Satz von Euler: [mm] a^{\phi(m)}\equiv [/mm] 1 mod m.
Muss man evtl erstmal hier [mm] \phi(m) [/mm] ausrechnen?
Grüße
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:59 Sa 25.12.2010 | | Autor: | Marcel |
Hallo,
> Also wir hatten:
>
> [mm]\forall[/mm] a [mm]\in \IZ: a^{n-1}\equiv[/mm] 1 mod n [mm]\gdw[/mm] n ist
> quadratfrei und für jedes p [mm]\in \IP[/mm] aus p|n auch p-1|n-1
>
> Satz von Euler: [mm]a^{\phi(m)}\equiv[/mm] 1 mod m.
>
> Muss man evtl erstmal hier [mm]\phi(m)[/mm] ausrechnen?
ganz ehrlich: Ich kenne mich im Bereich der Zahlentheorie fast nicht aus. Aber bzgl. Deiner Frage kann ich einfach nur sagen:
Manchmal hilft es einfach, mal ![[]](/images/popup.gif) nachzulesen, was der Satz, den man anwenden will, überhaupt besagt - und das heißt insbesondere, dass man sich alle Begriffe, die dort auftauchen, entweder nochmal ins Gedächtnis zu rufen weiß oder sie halt nachschlägt. Insbesondere heißt das bei Dir, nochmal nachzugucken, was denn die Eulersche Phi-Funktion ist.
Beste Grüße,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:01 Sa 25.12.2010 | | Autor: | leduart |
Hallo
> Also wir hatten:
>
> [mm]\forall[/mm] a [mm]\in \IZ: a^{n-1}\equiv[/mm] 1 mod n [mm]\gdw[/mm] n ist
> quadratfrei und für jedes p [mm]\in \IP[/mm] aus p|n auch p-1|n-1
warum untersuchst du nicht, ob das gilt für dein n?
Gruss leduart
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:26 Sa 25.12.2010 | | Autor: | felixf |
Moin!
> Zeige [mm]\forall[/mm] a [mm]\in \IZ: a^{1728}\equiv[/mm] 1 mod 1729
Die Aussage ist uebrigens schlichtweg falsch. Setz z.B. mal $a = 0$ ein.
(Es ist allerdings nicht sooo schwer, sie zu reparieren.)
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:53 Di 28.12.2010 | | Autor: | Bodo0686 |
Hallo,
dass steht aber genauso auf dem Aufgabenzettel...
Also [mm] \phi(1728)=576
[/mm]
Aber so ganz verstehe ich nicht, was ich da machen soll.
[mm] b^{n-1}\equiv [/mm] 1 mod n und ich soll zeigen,dass
[mm] b^{1728}\equiv [/mm] 1 mod 1729 gilt. So muss ich doch das b ausrechnen...
Das geht aber nur, wenn [mm] b\ge [/mm] 1 ist.
[mm] b^{1728} [/mm] = [mm] \alpha*576+\beta
[/mm]
-> [mm] b^{1728} [/mm] = [mm] b^{\alpha*576}*b^{\beta}
[/mm]
??? So wirklich weiß ich nicht, warum ich hier [mm] \phi(1728) [/mm] ausrechnen muss bzw. wie ich hier gescheit auf das b schließen kann...
Bitte um Hilfe
|
|
|
| |
|
Hallo Bodo,
es wäre eigenartig, wenn Du diese Äquivalenz nach b auflösen könntest bzw. überhaupt solltest. Was würde das denn für Deine Aufgabe bedeuten?
Wie Felix schon anmerkt, stimmt die Aufgabenstellung nicht ganz.
Sicher hast Du schon bemerkt, dass n=1729 eine zusammengesetzte Zahl ist, und dass (wie bereits bekannt) für alle p|n auch gilt: p-1|n-1.
Die Primfaktoren sind 7,13,19.
Mit diesem Wissen könntest Du die Aufgabe nun auch allein mit Fermat und dem chinesischen Restsatz lösen, und würdest dabei auch noch die von Felix angesprochene "Reparatur" vornehmen können.
Darfst Du den Satz von Euler hier denn überhaupt verwenden? Dann sind doch sowohl die Nachbesserung als auch die Lösung fast schon trivial. Hast Du ihn denn nochmal nachgelesen? Es steht doch praktisch alles im dort verlinkten Eintrag.
Grüße
reverend
PS: Zudem ist 1729 die kleinste Zahl, die man auf zwei verschiedene Weisen als Summe zweier Kubikzahlen darstellen kann. Aber das tut hier nichts zur Sache.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:50 Di 28.12.2010 | | Autor: | Bodo0686 |
Hallo also ich habe nun:
[mm] b^{1728}=b^{576*3+0}=(b^{576*3})*b^0 \equiv (1^{576})^3*b^0 \equiv 1^{576}*b^0 [/mm] = 1 [mm] \equiv [/mm] 1 mod 1729
grüße
|
|
|
| |
|
Hallo Bodo,
das sieht doch schon besser aus.
Und, hast Du es nun damit bewiesen oder nicht?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:03 Di 28.12.2010 | | Autor: | Bodo0686 |
ich glaube doch schon ...
|
|
|
| |
|
Ich glaube, eher nicht...
Was ist [mm] 14^{1728}\mod{1729} [/mm] ?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:17 Di 28.12.2010 | | Autor: | Bodo0686 |
Hallo ich habe doch nun
[mm] (14^{576})^3 [/mm] * [mm] 14^0 \equiv 1^{576}*14^0= [/mm] 1 [mm] \equiv [/mm] 1 mod 1729
oder nicht?
|
|
|
| |
|
Nein, die erste Äquivalenz stimmt nicht. Rechne doch mal nach, ohne den Satz von Euler zu benutzen. Geht mit Excel ganz leicht, wenn Du immer wieder die REST-Funktion benutzt.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:47 Di 28.12.2010 | | Autor: | Bodo0686 |
Hallo,
leider versagt das Excel-Programm... kann mir die Zahl nicht ausgeben...
Aber muss das Ergebnis, eher gesagt b, dann nicht quadratfrei sein. Das ist es ja nur bei den Primzahlen oder?
Grüße
|
|
|
| |
|
Hallo Bodo,
> leider versagt das Excel-Programm... kann mir die Zahl
> nicht ausgeben...
Excel-Tabelle anbei. Ergebnis:
[mm] 14^{1728}\equiv 742\mod{1729}
[/mm]
> Aber muss das Ergebnis, eher gesagt b, dann nicht
> quadratfrei sein. Das ist es ja nur bei den Primzahlen
> oder?
14 ist quadratfrei, und nicht prim. 742 übrigens auch, aber das tut hier gar nichts zur Sache (742=2*7*53).
Grüße
reverend
![[a]](/images/paperclip.gif "Dateianhänge") Link zum 1. Dateianhang
Dateianhänge:
Anhang Nr. 1 (Typ: xls) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:18 Di 28.12.2010 | | Autor: | felixf |
Moin reverend,
> PS: Zudem ist 1729 die kleinste Zahl, die man auf zwei
> verschiedene Weisen als Summe zweier Kubikzahlen darstellen
> kann. Aber das tut hier nichts zur Sache.
die kleinste Carmichael-Zahl ist es jedoch nicht, jedoch die kleinste Carmichael-Zahl, die man mit der Methode von Chernick konstruieren kann 
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:52 Di 28.12.2010 | | Autor: | reverend |
Hallo nochmal,
steht noch unter "ungesichtete Änderungen":
... für alle Basen a, die keinen Primfaktor mit 1729 (1729=7*13*19) gemeinsam haben, ...
Ist das missverständlich?
Aktuell steht da noch: ... für alle Basen a, die keinen Primfaktor mit 1729 (für 1729 sind dies: 7, 13, 19, 91, 133 und 247) gemeinsam haben,...
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:38 Di 28.12.2010 | | Autor: | felixf |
Moin reverend,
> steht noch unter "ungesichtete Änderungen":
oh man, da hab ich doch tatsaechlich die ungesichteten Aenderungen mit der derzeitigen Version verwechselt. Ja, deine Korrektur ist richtig, das Original ist falsch
Sorry!
LG Felix
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:35 Di 28.12.2010 | | Autor: | qsxqsx |
Was ich dazu weiss:
1. Es gibt einen "kleinen Satz von Fermat" der so lautet:
Für alle n [mm] \in \IN [/mm] mit n [mm] \ge [/mm] 2 gilt:
n Primzahl [mm] \gdw (a^{n-1} \equiv [/mm] 1 (mod n) für alle a [mm] \in \IZ_{n} [/mm] \ 0 )
2. Es gibt einen "Satz von Euler" der so lautet:
Für alle n [mm] \in \IN [/mm] mit n [mm] \ge [/mm] 2 gilt:
[mm] a^{phi(n)} \equiv [/mm] 1 (mod n) für alle a [mm] \in \IZ_{n}^{stern}
[/mm]
, wobei phi(n) die Eulersche Phi-Funktion ist
Der Satz von Fermat lässt sich mit dem Satz von Euler von links nach rechts beweisen. Der Satz von Euler kann mit Gruppentheorie bewiesen werden.
Du bist doch mathematiker, da kennst du dich sicher mit aus...?
Gruss
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:55 Di 28.12.2010 | | Autor: | qsxqsx |
Hallo,
Ich habe noch vergessen zu sagen was [mm] \IZ_{n} [/mm] bzw. [mm] \IZ_{n}^{stern} [/mm] ist.
[mm] \IZ_{n}^{stern} [/mm] = [mm] \{ a \in \IZ_{n} ohne 0 | ggT(a,n) = 1 \}
[/mm]
Ich meinte aber dass es beim kleinen Satz von Fermat für alle a auss 0 gilt.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:58 Di 28.12.2010 | | Autor: | reverend |
Hallo nochmal,
> Ich habe noch vergessen zu sagen was [mm]\IZ_{n}[/mm] bzw.
> [mm]\IZ_{n}^{stern}[/mm] ist.
>
> [mm]\IZ_{n}^{stern}[/mm] = [mm]\{ a \in \IZ_{n} ohne 0 | ggT(a,n) = 1 \}[/mm]
Aha.
> Ich meinte aber dass es beim kleinen Satz von Fermat für
> alle a auss 0 gilt.
Dann probier mal mit p=5 folgendes:
[mm] 15^{5-1}\mod{5}\equiv{?}
[/mm]
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:00 Di 28.12.2010 | | Autor: | qsxqsx |
Ich meinte a [mm] \in \IZ_{n} [/mm] ausser 0. Jetzt haben wirs.
Gruss
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:03 Di 28.12.2010 | | Autor: | reverend |
Ja, so gehts für den Fermat. Aber warum nicht gleich eine Formulierung nehmen, die auch für Euler taugt?
Die Vorbedingung ist für die vorliegende Aufgabe ja wesentlich, nur darum hacke ich darauf herum. Es gibt verschiedene Schreibweisen, aber Hauptsache, die Einschränkung auf teilerfremde a liegt vor.
Grüße
reverend
|
|
|
|
