Quadratische Reste

04.10.2014, 02:49	mathemensch123	Auf diesen Beitrag antworten »
Quadratische Reste Hallo, ich soll mittels Induktion zeigen: Seien $\begin{eqnarray} p_1,\hdots , p_r \end{eqnarray}$ verschiedene Primzahlen und $\begin{eqnarray} (n/p_i)=1 \end{eqnarray}$ (Legendre-Symbol) für alle i. Dann hat die Kongruenz $\begin{eqnarray} x^2 \equiv n \mod p_1\cdots p_r \end{eqnarray}$ genau $\begin{eqnarray} 2^n \end{eqnarray}$ Lösungen modulo $\begin{eqnarray} p_1\cdots p_r \end{eqnarray}$ . Den Fall n=1 habe ich (denke ich) - dabei aber nicht gebraucht, dass 1 quadratischer Rest modulo p_i ist (btw - das ist doch ohnehin immer so oder?). Weiter weiß ich nun aber leider nicht. Das sieht ja alles verdächtig nach Chinesischem Restesatz aus - das problem ist nur, dass ich nicht weiß, was ich über die Anzahl der Lösungen aussagen kann... Ich wäre über jede Hilfe sehr dankbar!
06.10.2014, 10:56	tmo	Auf diesen Beitrag antworten »
Ja, in der Tat folgt die Aussage eigentlich direkt aus dem chin. Restsatz, wenn man z.B. folgendes allgemeines leicht zu zeigendes Resultat parat hat: Seien $\begin{align} A,B \end{align}$ zwei Ringe (meinentwegen so wie bei uns kommutativ mit Eins). Hat die Gleichung $\begin{align} f(x)=a \end{align}$ in $\begin{align} A \end{align}$ genau $\begin{align} m \end{align}$ Lösungen und die Gleichung $\begin{align} g(y)=b \end{align}$ in $\begin{align} B \end{align}$ genau $\begin{align} n \end{align}$ Lösungen, so hat die Gleichung $\begin{align} (f(x),g(y))=(a,b) \end{align}$ in $\begin{align} A \times B \end{align}$ genau $\begin{align} mn \end{align}$ Lösungen. PS: Ich sehe gerade, dass in der Aufgabenstellung ein Fehler ist, deswegen auch deine Verwirrung beim Fall n=1. Die Anzahl der Lösungen ist nicht etwa $\begin{align} 2^n \end{align}$ , sondern $\begin{align} 2^r \end{align}$ ! Die Abhängigkeit der Anzahl der Lösungen von $\begin{align} n \end{align}$ würde auch gar kein Sinn machen, weil die Gleichung ja offenbar unter der Änderung $\begin{align} n \mapsto n + kp_1 \dotsb p_r \end{align}$ für jedes k invariant bleibt, laut Aufgabenstellung sich jedoch die Anzahl der Lösungen drastisch erhöht

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »