Primzahlen, die das erfüllen

27.06.2005, 15:27

Spieky

Auf diesen Beitrag antworten »

Primzahlen, die das erfüllen

Folgende Aufgabe ist zu lösen:
Man bestimme alle Primzahlen p>5, für die die Kongruenz
$\begin{eqnarray*} 3x^{2} \equiv x+1 \end{eqnarray*}$ mod p
eine Lösung hat.
Tipp: Da die Zahl 12 in $\begin{eqnarray*} \mathbb Z/p \mathbb Z \end{eqnarray*}$ invertierbar ist, darf man obige Kongruenz mit 12 multiplizieren und anschließend y=6x setzen. Leiten Sie auf diese Weise die äquivalente Kongruenz $\begin{eqnarray*} y^{2} \equiv 2y+12 \end{eqnarray*}$ her.

Wie kommt man auf den Tipp (Wie komme ich darauf, dass 12 invertierbar), wie löst man Kongruenzen, mit y^2 und y in einer Gleichung? Kann mir bitte auch hierzu einer eine allgemeine Lösungsstrategie angeben?

27.06.2005, 15:52

AD

Auf diesen Beitrag antworten »

RE: Primzahlen, die das erfüllen
Die Zahl a besitzt modulo m ein Inverses, wenn a und m teilerfremd sind. Hier ist dieses $\begin{eqnarray*} m=p>5 \end{eqnarray*}$ eine Primzahl und $\begin{eqnarray*} a=12=2^2\cdot 3 \end{eqnarray*}$ , also ist die Teilerfremdheit erfüllt.

Sinn und Zweck der Operation ist natürlich, links ein Quadrat ohne Vorfaktor zu erzeugen. Dazu würde prinzipiell auch die Multiplikation mit 3 genügen, aber wenn man vor das Linearglied rechts einen geraden Vorfaktor zwecks quadratischer Ergänzung haben will, ist 12 als Faktor eben besser. Augenzwinkern

Augenzwinkern

27.06.2005, 19:07

Spieky

Auf diesen Beitrag antworten »

RE: Primzahlen, die das erfüllen
Joa, danke schon mal. Und wie löst man dann sowas, wenn da halt sowohl y also auch y^2 in einer Gleichung vorkommen? Ich meine, nur y ist klar und nur y^2 auch, aber beides? Ich habe echt keine Ahnung. Kann ich das evtl getrennt betrachten, also erst die Kongruenz für y und dann die für y^2? doch bestimmt nicht, oder?

27.06.2005, 21:19

Ben Sisko

Auf diesen Beitrag antworten »

RE: Primzahlen, die das erfüllen
Wenn $\begin{eqnarray*} y^{2} \equiv 2y+12 \end{eqnarray*}$ ist, dann gilt $\begin{eqnarray*} y^{2}-2y-12 \equiv 0 \end{eqnarray*}$ Augenzwinkern

Augenzwinkern

Gruß vom Ben

27.06.2005, 22:58

Spieky

Auf diesen Beitrag antworten »

RE: Primzahlen, die das erfüllen
Schon klar, und wenn ich das mit quadratischer Ergänzung umforme, bekomme ich $\begin{eqnarray*} (y-1)^{2}-13 \equiv 0 \end{eqnarray*}$ , also meinetwegen auch $\begin{eqnarray*} (y-1)^{2}\equiv 13 \end{eqnarray*}$ . Das bringt mich auch nicht weiter. verwirrt

verwirrt

27.06.2005, 23:13

AD

Auf diesen Beitrag antworten »

Das Quadratische Reziprozitätsgesetz kennst du doch, oder?

Anzeige

28.06.2005, 19:11

Spieky

Auf diesen Beitrag antworten »

Klar. Aber ich habe leider keine Ahnung wie ich das anwende, wenn ich da stehen habe: $\begin{eqnarray*} (y-1)^{2} \equiv 13 \end{eqnarray*}$ . Wenn da nur $\begin{eqnarray*} y^{2} \equiv 13 \end{eqnarray*}$ stehen würde, wüsste ich wies geht.

28.06.2005, 19:31

AD

Auf diesen Beitrag antworten »

Ob da nun $\begin{eqnarray*} y \end{eqnarray*}$ , oder $\begin{eqnarray*} y-1 \end{eqnarray*}$ steht, wo ist da das Problem??? geschockt

geschockt

geschockt

geschockt

29.06.2005, 10:27

Spieky

Auf diesen Beitrag antworten »

Also kann ich mir im Prinzip dieses y-1 als z setzen, dann normal das Reziprozitätsgesetz anwenden?

29.06.2005, 19:23

AD

Auf diesen Beitrag antworten »

Richtig.

Freude

30.06.2005, 17:56

Spieky

Auf diesen Beitrag antworten »

ok, danke.

30.06.2005, 22:44

Spieky

Auf diesen Beitrag antworten »

Ich habe aber doch noch mal eine Frage:
Wenn ich da in der Gleichung, wie ja schon geschrieben diese y-1 als z setze und das Reziprozitätsgesetz anwende, dann muss ich ja ausrechnen, wann $\begin{eqnarray*} (\frac{13}{p})=1 \end{eqnarray*}$ gilt.Ich bekomme dann da raus, dass $\begin{eqnarray*} (\frac{13}{p})=1, falls p\equiv 1,39(52) \end{eqnarray*}$ und $\begin{eqnarray*} (\frac{13}{p})=-1, falls p\equiv 25,27(52) \end{eqnarray*}$ . Kann das sein oder habe ich mich da verrechnet?
vor allem: Wo geht da die Bedingung, dass p>5 ist in die Rechnung ein?

30.06.2005, 23:01

AD

Auf diesen Beitrag antworten »

Deine Rechnung ist für mich nicht ganz nachvollziehbar. Also zunächst mal das Reziprozitätsgesetz:

$\begin{eqnarray*} \left(\frac{13}{p}\right)\cdot \left(\frac{p}{13}\right)=(-1)^{\frac{p-1}{2}\cdot\frac{13-1}{2}}=(-1)^{3(p-1)}=1 \end{eqnarray*}$ für alle ungeraden Primzahlen p.

Also gilt $\begin{eqnarray*} \left(\frac{13}{p}\right) = \left(\frac{p}{13}\right) \end{eqnarray*}$ . Nun gibt es aber modulo 13, und dann auch modulo 52 ein paar mehr quadratische Reste, als du sie angegeben hast!

01.07.2005, 22:35

Spieky

Auf diesen Beitrag antworten »

Also, zu meinem Rechenweg:
Ich habe zuerst einmal genau das gleiche ausgerechnet, wie du gerade aufgeschrieben hast und da allgemein herausbekommen, dass $\begin{eqnarray*} (-1)^{ \frac{p-1}{2}}=1 falls p\equiv 1(4) \end{eqnarray*}$ , $\begin{eqnarray*} (-1)^\frac{p-1}{2})=-1 falls p \equiv 3(4) \end{eqnarray*}$ . Dann habe ich mit $\begin{eqnarray*} (\frac{p}{13} ) \end{eqnarray*}$ weitergerechnet und herausbekommen, dass $\begin{eqnarray*} (\frac{p}{13})=1 falls p \equiv 1(13) \end{eqnarray*}$ , $\begin{eqnarray*} (\frac{p}{13})=-1 falls p \equiv 12(13) \end{eqnarray*}$ Wenn ich die beiden Ergebnisse zusammenpacke, dann komme ich auf das obengenannte Ergebnis. Ist da irgendwo ein Fehler drin? Wenn ja, dann sage mir bitte wo, bzw. gib mir bitte einen Tipp, wie ich auf weitere Restklassen kommen soll.

01.07.2005, 23:04

AD

Auf diesen Beitrag antworten »

Zitat:

Original von Spieky
dass $\begin{eqnarray*} (-1)^{ \frac{p-1}{2}}=1 falls p\equiv 1(4) \end{eqnarray*}$ , $\begin{eqnarray*} (-1)^\frac{p-1}{2})=-1 falls p \equiv 3(4) \end{eqnarray*}$ .

Das ist erstmal unstrittig richtig. Aber was soll das mit dem

Zitat:

Original von Spieky
Dann habe ich mit $\begin{eqnarray*} (\frac{p}{13} ) \end{eqnarray*}$ weitergerechnet und herausbekommen, dass $\begin{eqnarray*} (\frac{p}{13})=1 falls p \equiv 1(13) \end{eqnarray*}$ , $\begin{eqnarray*} (\frac{p}{13})=-1 falls p \equiv 12(13) \end{eqnarray*}$

zu tun haben, das ist mir schleierhaft.

Fakt ist erstmal, dass alle Primzahlen $\begin{eqnarray*} p \end{eqnarray*}$ bezüglich modulo 13 entweder Rest oder Nichtrest sind, also gilt für jedes $\begin{eqnarray*} p \end{eqnarray*}$ entweder $\begin{eqnarray*} \left(\frac{p}{13}\right)=1 \end{eqnarray*}$ oder $\begin{eqnarray*} \left(\frac{p}{13}\right)=-1 \end{eqnarray*}$ . Du äußerst dich nun nur zu zwei der 13 Restklassen. Was ist mit den anderen 11 Restklassen modulo 13 ?

Ich rechne das ab diesem Moment einfach so: Für $\begin{eqnarray*} x\equiv 0, \pm 1, \pm 2, \pm 3, \pm 4, \pm 5, \pm 6 \mod 13 \end{eqnarray*}$ erhält man die quadratischen Reste $\begin{eqnarray*} x^2\equiv 0,1,4,9,3,12,10 \end{eqnarray*}$ , also ergibt sich:

quadratische Reste modulo 13: 0,1,3,4,9,10,12
quadratische Nichtreste modulo 13: 2,5,6,7,8,11

02.07.2005, 16:37

Spieky

Auf diesen Beitrag antworten »

Aha, das heißt dann also für die Primzahlen, die gesucht sind was? Das sie kongruent zu einem dieser quadratischen Reste mod 13 sein müssen?

02.07.2005, 16:56

AD

Auf diesen Beitrag antworten »

Richtig.

Freude

Gehört zwar nicht mehr zur Aufgabe, aber: Laut Dirichlet gibt es in allen arithmetischen Folgen $\begin{eqnarray*} (an+b)_{n=0,1,2,\ldots} \end{eqnarray*}$ mit teilerfremden a,b (sogenannte "arithmetische Progressionen") sogar unendlich viele Primzahlen. Hier kann man das für a=13 und b=1,3,4,9,10,12 nutzen. Für b=0 gibt es aber natürlich nur eine Primzahl in so einer Progression, nämlich p=13 selbst.

02.07.2005, 17:23

Spieky

Auf diesen Beitrag antworten »

Danke für die Hilfe.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »