Lösungen einer Kongruenz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 10:47 Do 24.01.2013 | | Autor: | wauwau |
| Aufgabe | Für welche Primzahlen p ist die folgende Kongruenz in n lösbar
[mm] $3^n \equiv [/mm] 2 (p)$ |
für p=5,7,17,19,23,29,31,43,47,53,71,
ist die Kongruenz lösbar also nicht für alle Primzahen.
Wie gelingt es die p zu charakterisieren, für die das lösbar bzw unlösbar ist.
|
|
| |
|
Hallo wauwau,
ich würde da über quadratische Reste (QR) und Nichtreste (NR) gehen.
> Für welche Primzahlen p ist die folgende Kongruenz in n
> lösbar
> [mm]3^n \equiv 2 (p)[/mm]
> für p=5,7,17,19,23,29,31,43,47,53,71,
> ist die Kongruenz lösbar also nicht für alle Primzahen.
> Wie gelingt es die p zu charakterisieren, für die das
> lösbar bzw unlösbar ist.
Sicher ist: wenn 3 QR mod p ist, aber 2 NR, dann gibt es keine Lösung.
Das ist leicht zu zeigen: jede Potenz von 3 ist dann auch QR.
Ich meine auch, dass wenn 3 NR mod p ist, es immer eine Lösung gibt.
Das ist nicht so leicht zu zeigen. Ich versuchs später einmal.
Fraglich ist nun: wenn 2 und 3 beide QR mod p sind, ist dann eine Aussage möglich? Da hänge ich.
Soviel vorerst als erste Idee; ich lasse die Frage halboffen.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:14 Do 24.01.2013 | | Autor: | wauwau |
Habe das nun numerisch ein wenig überprüft und es scheint tatsächlich so, wie wenn dein erster Fall (3 QR mod p und 2 NR mod p) genau die Fälle sind, wo die Kongruenz nicht lösbar ist.
Beweis wäre natürlich ganz nett...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:57 Do 24.01.2013 | | Autor: | reverend |
Hallo nochmal,
nee, so stimmt das doch alles noch nicht.
> ich würde da über quadratische Reste (QR) und Nichtreste
> (NR) gehen.
Das erschlägt leider doch nicht alles.
> > Für welche Primzahlen p ist die folgende Kongruenz in n
> > lösbar
> > [mm]3^n \equiv 2 (p)[/mm]
> > für
> p=5,7,17,19,23,29,31,43,47,53,71,
> > ist die Kongruenz lösbar also nicht für alle
> Primzahen.
> > Wie gelingt es die p zu charakterisieren, für die das
> > lösbar bzw unlösbar ist.
>
> Sicher ist: wenn 3 QR mod p ist, aber 2 NR, dann gibt es
> keine Lösung.
> Das ist leicht zu zeigen: jede Potenz von 3 ist dann auch
> QR.
Gut, dieser Teil bleibt natürlich.
> Ich meine auch, dass wenn 3 NR mod p ist, es immer eine
> Lösung gibt.
> Das ist nicht so leicht zu zeigen. Ich versuchs später
> einmal.
Stimmt nicht, z.B. für 67, 103 und 151. Da ist jeweils [mm] 3^{\bruch{p-1}{6}}\equiv -1\mod{p}, [/mm] damit ist 3 quadratischer Nichtrest. Trotzdem erfüllt keine Dreierpotenz die geforderte Kongruenz [mm] \equiv 2\mod{p}.
[/mm]
> Fraglich ist nun: wenn 2 und 3 beide QR mod p sind, ist
> dann eine Aussage möglich? Da hänge ich.
Da bin ich auch kein Stück weiter, habe mir nur ein paar kleine Beispiele (bis p=503) angesehen.
Für folgende p sind 2 und 3 beide QR mod p:
23, 47, 71, 73, 97, 167, 191, 193, 239, 241, 263, 311, 313, 337, 359, 383, 409, 431, 433, 457, 479, 503
Für die schwarzen Primzahlen ist die Kongruenz lösbar, für die roten nicht.
Hinweis: [mm] 3^{12}\equiv 1\mod{73}, 3^{16}\equiv 1\mod{193}, 3^{39}\equiv 1\mod{313}, 3^{27}\equiv 1\mod{433}
[/mm]
Es wird sich also lohnen, auch die Ordnung von 3 [mm] \mod{p} [/mm] zu untersuchen. Ist sie =p-1, ist die Kongruenz natürlich lösbar, aber ist sie nur ein (dann kleinerer) Teiler davon, sehe ich gerade nicht, wie man das allgemein löst
> Soviel vorerst als erste Idee; ich lasse die Frage
> halboffen.
Dabei bleibt es wohl auch weiterhin...
Grüße
reverend
Nachtrag:
Eine notwendige Bedingung, die schon ein relativ starkes aber leider nicht sicheres Kriterium bietet, ist diese:
[mm] \operatorname{ord}(2)|\operatorname{ord}(3)\mod{p}
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:52 Fr 01.02.2013 | | Autor: | hippias |
Da die multiplikative Gruppe von [mm] $\IZ_{p}$ [/mm] zyklisch ist, existiert genau dann ein [mm] $n\in \IN$ [/mm] mit [mm] $3^{n}\equiv_{p} [/mm] 2$ wenn [mm] $o(3)\vert [/mm] o(2)$ (Ordnungen alle in [mm] $\IZ_{p}$). [/mm] Wegen [mm] $3^{m}\equiv_{p}3^{n}\iff o(3)\vert [/mm] n-m$ ist die Menge aller $n$ fuer die, diese Kongruenz loesbar ist gleich [mm] $n_{0}+o(3)\IN$, [/mm] wobei [mm] $n_{0}$ [/mm] eine partikulaere Loesung ist.
Es "genuegt" also die Ordnungen von $2$ und $3$ in [mm] $\IZ_{p}$ [/mm] zu ermitteln. Ich weiss nichts darueber.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:20 Fr 08.02.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
