Kongruenzlösbarkeitsäquivalenz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:33 Do 29.11.2012 | | Autor: | cluso. |
Hallo,
Wie fast immer fehlt mir die Idee für einen Beweis:
Sei p eine ungerade Primzahl , b [mm] \nequiv [/mm] 0 ( [mm] \mod [/mm] p ), n [mm] \in \mathbb [/mm] N [mm] \Rightarrow [/mm] folgende Aussagen sind äquivalent
[mm] a)x^{n} \equiv [/mm] b [mm] (\mod [/mm] p) lösbar in [mm] \mathbb [/mm] Z
[mm] b)b^{\frac{p-1}{\ggT(n,p-1)}} \equiv [/mm] 1 [mm] (\mod [/mm] p )
Könntet ihr mir wieder eine geben?
Gruß
Cluso.!
|
|
| |
|
> Hallo,
Guten Abend,
>
> Wie fast immer fehlt mir die Idee für einen Beweis:
Dann hast du hoffentlich dir schon einmal ein konkretes Beispiel angeschaut.
>
> Sei p eine ungerade Primzahl , b [mm]\nequiv[/mm] 0 ( [mm]\mod[/mm] p ), n
Was hat die 0 hier zu suchen? Meinst du [mm]b\equiv 0\mod p[/mm]. Wohl eher nicht?
> [mm]\in \mathbb[/mm] N [mm]\Rightarrow[/mm] folgende Aussagen sind
> äquivalent
>
> [mm]a)x^{n} \equiv[/mm] b [mm](\mod[/mm] p) lösbar in [mm]\mathbb[/mm] Z
> [mm]b)b^{\frac{p-1}{\ggT(n,p-1)}} \equiv[/mm] 1 [mm](\mod[/mm] p )
>
> Könntet ihr mir wieder eine geben?
>
Du rechnest also in [mm]\IZ/p\IZ[/mm] für eine Primzahl [mm]p[/mm]. Insbesondere ist [mm](\IZ/p\IZ)^\times[/mm] zyklisch von Ordnung [mm]\varphi(p)[/mm].
a) Die Einheitengruppe [mm](\IZ/p\IZ)^\times[/mm] hat Erzeuger (Primitivwurzeln) und mit diesen arbeitet man. Du brauchst auch nur [mm]n=0,\dotsc,p-2[/mm] betrachten. Es gibt da eindeutige Darstellungen.
b) Der Bruch im Exponent sollte dich ein wenig an Ordnungen von Untergruppen erinnern.
Gruß
wieschoo
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:29 Sa 01.12.2012 | | Autor: | felixf |
Moin,
> > Sei p eine ungerade Primzahl , b [mm]\nequiv[/mm] 0 ( [mm]\mod[/mm] p ), n
>
> Was hat die 0 hier zu suchen? Meinst du [mm]b\equiv 0\mod p[/mm].
> Wohl eher nicht?
ich tippe eher auf $b [mm] \not\equiv [/mm] 0 [mm] \pmod{p}$. [/mm] Sieht im Quellcode auch so aus. Und macht dann auch mehr Sinn 
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:10 Do 29.11.2012 | | Autor: | wieschoo |
"Kobgeruenz" ist eine neue Wortschöpfung und mathematischer Background von "5.Klasse" nimmt dir hier wohl niemand mehr ab.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:17 Fr 30.11.2012 | | Autor: | cluso. |
@Wieschoo:
Mor isr es völlig egal ob mir jemand glaubt ob ich in der 5. Klasse bin. Jedenfalls ist es so, und es ist doch egal ob mitdas jemand glaubt. Und ich meine natürlich Kongruenz.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 20:27 Fr 30.11.2012 | | Autor: | cluso. |
Das oben soll keine Frage sondern eine Mitteilung sein.
Und zur Aufgabe:
Mein Ansatz:
Es ist [mm] (\mathbb [/mm] Z /p [mm] \mathbb Z)^{\ast}=N [/mm] zyklisch [mm] \Rightarrow \forall [/mm] [a] [mm] \in [/mm] N : [mm] \exists [/mm] [k] [mm] \in [/mm] N: [mm] \exists [/mm] g [mm] \in \mathbb [/mm] Z: [mm] [k]^{g}=[a] \Rightarrow k^{g} \equiv [/mm] a ( mod p ) ist für beliebige a lösbar in [mm] \mathbb [/mm] Z. Jetzt muss ich mir noch was über g überlegen.
Ist der Ansatz zielführend oder eher sinnlos?
Gruß
Clsuo!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:29 Sa 01.12.2012 | | Autor: | cluso. |
Zu g fällt mir aber nichts ein.
Gruß
Cluso!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:25 Sa 01.12.2012 | | Autor: | cluso. |
Könntet ihr mir helfen?
Gruß
Cluso!
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:37 Sa 01.12.2012 | | Autor: | felixf |
Moin!
> Und zur Aufgabe:
>
> Mein Ansatz:
>
> Es ist [mm](\mathbb[/mm] Z /p [mm]\mathbb Z)^{\ast}=N[/mm] zyklisch
> [mm]\Rightarrow \forall[/mm] [a] [mm]\in[/mm] N : [mm]\exists[/mm] [k] [mm]\in[/mm] N: [mm]\exists[/mm]
> g [mm]\in \mathbb[/mm] Z: [mm][k]^{g}=[a][/mm]
Vorsicht! Mit Quantoren [mm] ($\exists$ [/mm] und [mm] $\forall$) [/mm] musst du aufpassen, in welche Reihenfolge du sie schreibst! Du meinst wohl eher [mm] $\exists [/mm] [k] [mm] \in [/mm] N [mm] \forall [/mm] [a] [mm] \in [/mm] N [mm] \exists [/mm] g [mm] \in \IZ [/mm] : [mm] [k]^g [/mm] = [a]$.
Andernfalls kannst du immer $k = a$ und $g = 1$ waehlen und die Aussage funktioniert in jeder Gruppe, nicht nur in zyklischen. (Sogar in jedem ![[]](/images/popup.gif) Magma. Ist also eine voellig langweilige und uninteressante Aussage.)
>[mm]\Rightarrow k^{g} \equiv[/mm] a (
> mod p ) ist für beliebige a lösbar in [mm]\mathbb[/mm] Z.
Bei solchen Aussagen ist nicht klar, was du mit "loesbar" meinst. Was ist gegeben (ausser $a$) und was ist gesucht? Mit $k$ meinst du vermutlich einen Erzeuger, dann gibt es tatsaechlich zu jedem $a$ (welches nicht durch $p$ teilbar ist!) ein solches $k$.
> Ist der Ansatz zielführend oder eher sinnlos?
Er geht in die richtige Richtung. Ist aber noch viel zu tun!
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:32 So 02.12.2012 | | Autor: | cluso. |
Hallo,
Danke für deine Antwort!
Ja stimmt. Die Quantoren waren falsch gesetzt. Eigentlich passiert mir so etwas nicht aber...
Nun und was ist mit g Dem Exponent? Mir fällt keine Bedingung ein (außer, dass [mm] [k]^{g}=[a] [/mm] sein muss. Aber das haben wir ja schon. Mir fällt keine zielführendere Formulierung/Äquivalenz ein).
Gruß
Cluso!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:42 Sa 08.12.2012 | | Autor: | cluso. |
Aber x spielt doch als Erzeuger eine wesentliche Rolle in der Lösbarkeit?
Aber x muss doch keine Variable in der zu zeigenden Kongruenzlösbarkeitsäquivalenz sein oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:01 So 09.12.2012 | | Autor: | felixf |
Moin!
> Aber x spielt doch als Erzeuger eine wesentliche Rolle in
> der Lösbarkeit?
> Aber x muss doch keine Variable in der zu zeigenden
> Kongruenzlösbarkeitsäquivalenz sein oder?
Was fuer ein $x$?
LG Felix
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:03 So 09.12.2012 | | Autor: | felixf |
Moin!
> Nun und was ist mit g Dem Exponent? Mir fällt keine
> Bedingung ein (außer, dass [mm][k]^{g}=[a][/mm] sein muss. Aber das
> haben wir ja schon. Mir fällt keine zielführendere
> Formulierung/Äquivalenz ein).
Da $[k]$ die Ordnung $p - 1$ hat, gilt [mm] $[k]^g [/mm] = [mm] [k]^h$ [/mm] genau dann, wenn $g [mm] \equiv [/mm] h [mm] \pmod{p - 1}$ [/mm] ist. Damit kannst du das multiplikative Problem auf ein additives Problem uebertragen, welches einfacher zu loesen ist.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 18:12 So 09.12.2012 | | Autor: | cluso. |
Mit x meine ich das x was auch in unserer zu zeigenden Kongruenzlösbarkeitsäquivalenz vor dem Äquivalenzpfeil stehende Kongruenzlösbarkeit vorkommt. Die Basis in der Potenz.
Bei der Überlegung ist x=k der Erzeuger muss also eine Variable sein. Aber darüber ist in der zu zeigenden Äquivalenz überhaupt nicht die Rede.(?)
Wo ist gegebenenfalls mein Denkfehler?
@(vorallem) felixf und den anderen:
Vielen Dank für deine/eure tolle Hilfe! Ohne sie hätte ich bestimmt nicht so viel Spaß ( er ist unglaublich groß ) an der Mathematik wie jetzt.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:47 Mo 24.12.2012 | | Autor: | felixf |
Moin!
> Sei p eine ungerade Primzahl , b [mm]\not\equiv[/mm] 0 ( [mm]\mod[/mm] p ), n
> [mm]\in \mathbb[/mm] N [mm]\Rightarrow[/mm] folgende Aussagen sind
> äquivalent
>
> [mm]a)x^{n} \equiv[/mm] b [mm](\mod[/mm] p) lösbar in [mm]\mathbb[/mm] Z
> [mm]b)b^{\frac{p-1}{\ggT(n,p-1)}} \equiv[/mm] 1 [mm](\mod[/mm] p )
Ich fuell dir mal ein wenig vom Beweis aus.
[mm] (a)$\Rightarrow$(b): [/mm] angenommen, es gibt so ein $x [mm] \in \IZ$ [/mm] mit [mm] $x^n \equiv [/mm] b [mm] \pmod{p}$. [/mm] Dann gilt [mm] $b^{(p-1)/ggT(n,p-1)} \equiv (x^n)^{(p-1)/ggT(n,p-1)} [/mm] = [mm] x^{(p-1) \cdot \frac{n}{ggT(n, p-1)}} [/mm] = [mm] (x^{p-1})^{\frac{n}{ggT(n, p-1)}} \equiv [/mm] ... [mm] \pmod{p}$.
[/mm]
[mm] (b)$\Rightarrow$(a): [/mm] Sei $g$ ein Erzeuger von [mm] $(\IZ/p\IZ)^\ast$. [/mm] Dann gibt es ein $k [mm] \in \IN$ [/mm] mit [mm] $g^k \equiv [/mm] b [mm] \pmod{p}$. [/mm] Wegen [mm] $g^{k \cdot (p-1)/ggT(n,p-1)} \equiv b^{(p-1)/ggT(n,p-1)} \equiv [/mm] 1 [mm] \pmod{p}$ [/mm] und da $g$ die Ordnung $p - 1$ hat folgt $k [mm] \cdot \frac{p - 1}{ggT(n, p - 1)} \equiv [/mm] 0 [mm] \pmod{p - 1}$.
[/mm]
Schreibe nun $p - 1 = ggT(p - 1, n) [mm] \cdot r_1$ [/mm] und $n = ggT(p - 1, n) [mm] \cdot r_2$. [/mm] Du hast also [mm] $r_1 \cdot [/mm] ggT(p - 1, n) [mm] \mid [/mm] (k [mm] \cdot r_1)$, [/mm] also $ggT(p - 1, n) [mm] \mid [/mm] k$. Sei $k = [mm] \ell \cdot [/mm] ggT(p - 1, n)$ und setze $x := [mm] g^{\ell}$.
[/mm]
Jetzt musst du [mm] $(g^\ell)^n \equiv [/mm] b [mm] \equiv g^k \pmod{p}$ [/mm] zeigen. Dies ist aequivalent zu [mm] $\ell \cdot [/mm] n [mm] \equiv [/mm] k [mm] \pmod{p - 1}$, [/mm] da $g$ die Ordnung $p - 1$ hat.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 10:42 Di 25.12.2012 | | Autor: | cluso. |
Vielen Dank!
Ich habe zur ersten Richtung noch eine Frage: anstatt ... Soll da ja 1 stehen oder? Aber ich weiß ggF. nicht warum.?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:20 Do 27.12.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 10:53 Di 25.12.2012 | | Autor: | cluso. |
Und bei der anderen Richtung verstehe ich nicht , warum [mm] r_1 \ggT [/mm] ( p-1,n ) | k [mm] \cdot r_1 [/mm] .
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:20 Do 27.12.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:29 Mi 26.12.2012 | | Autor: | cluso. |
Warum darf ich x = [mm] g^l [/mm] setzen? Was wenn x=0 ist?
|
|
|
| |
|
> Warum darf ich x = [mm]g^l[/mm] setzen? Was wenn x=0 ist?
Hier befinden wir uns in [mm] $(\IZ/p\IZ)^\times$. [/mm] Da gibt es keine 0, da 0 keine Einheit (nicht invertierbar) ist.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 08:00 Do 27.12.2012 | | Autor: | cluso. |
Aber wo steht das? In der Behauptung steht nichts über x?
|
|
|
| |
|
Hallo cluso.,
recht unübersichtlich, der ganze thread ...
> Aber wo steht das? In der Behauptung steht nichts über x?
Wenn ich das richtig gesehen habe, sind wir doch in der "Rückrichtung" [mm](b)\Rightarrow \ (a)[/mm].
Und da war doch [mm]g[/mm] als Erzeuger von [mm](\IZ/p\IZ)^\ast[/mm] angenommen ...
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:38 Sa 29.12.2012 | | Autor: | cluso. |
Meine Frage ist zwar überfällig, ber trotzdem wichtig.
|
|
|
|
