Lösbarkeit von quadratischen Kongruenzen

24.06.2011, 17:03	nupps	Auf diesen Beitrag antworten »
Lösbarkeit von quadratischen Kongruenzen Meine Frage: Welche der folgenden Kongruenzen ist lösbar? a) x² = 59 mod 79 b)... Meine Ideen: Wenn das Legendresymbol gleich Eins ist, ist die Kongruenz lösbar. Also $\begin{eqnarray} \left(\frac{59}{79}\right)=? \end{eqnarray}$ Mit dem Eulerschen Kriterium $\begin{eqnarray} \left(\frac{a}{p}\right)=a^{\frac{p-1}{2}} \end{eqnarray}$ mod p wird das vermutlich nichts bei so großen Zahlen. Nen Tip, wie ich dort vorgehen muss, wäre nett.
24.06.2011, 18:15	tmo	Auf diesen Beitrag antworten »
Das Quadratische Reziprozitätsgesetz hilft hier weiter.
25.06.2011, 12:09	npps	Auf diesen Beitrag antworten »
Also Reziprokitätsgesetz anwenden: $\begin{eqnarray} \left(\frac{59}{79}\right)=\left(\frac{79}{59}\right)(-1)^{\frac{79-1}{2} \frac{59-1}{2}}= \left(\frac{79}{59}\right)(-1)^{1131}=(-1)\left(\frac{79}{59}\right)=(-1)\left(\frac{20}{59}\right)=(-1)\left(\frac{2}{59}\right)\left(\frac{2}{59}\right)\left(\frac{5}{59}\right) \end{eqnarray}$ Die beiden Legendresymbole die eine Zwei enthalten mittels Ergänzungssatz bestimmen. (L(2,59==-1) $\begin{eqnarray} (-1)\left(\frac{2}{59}\right)\left(\frac{2}{59}\right)\left(\frac{5}{59}\right)=(-1)(-1)(-1)\left(\frac{5}{59}\right)=(-1)(-1)(-1)\left(\frac{59}{5}\right)(-1)^{\frac{59-1}{2}\frac{5-1}{2}}=(-1)(-1)(-1)\left(\frac{59}{5}\right)(-1)^{89}=(-1)(-1)(-1)\left(\frac{4}{5}\right)=(-1)(-1)(-1)(1)=-1 \end{eqnarray*}$ Stimmt das so?

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »