Chinesischer Restsatz beim Modulorechnen

Question

ich sitze schon seit Tagen an meinem Hausübungsblatt und komme einfach nicht weiter...

In Zahlentheorie geht es aktuell um quadratische Reste und wir haben letzte Woche den chinesischen Restsatz besprochen.

Da ich jetzt eine quadratische Funktion auf Z/38Z lösen soll, habe ich mich gefragt, ob sich der chinesische Restsatz aus auf Kongruenzen der Form

x² = a_1 mod p_1^z_1

x² = a_2 mod p_2^z_2

      ...

x² = a_n mod p_n^z_n

ausweiten lässt.

Wie ließe sich das beweisen, sofern es möglich wäre?

Comments

Da ich jetzt eine quadratische Funktion auf Z/38Z lösen soll

Das hängt sehr von der Funktion ab.

z.B. ist 2 kein quadratischer Rest mod 38, also

hat z.B. x² = 2 hier keine Lösung.

---

Danke für deine Antwort, aber es geht mir nicht um eine Lösung der Aufgabe an sich, sondern um eine mögliche Erweiterung des chinesischen Restsatzes auf quadratische Kongruenzen.

---

Da habe ich keine Idee.

---

Dennoch vielen Dank!

---

was verstehst du denn unter dem chinesichen Restsatz? Gib die Aussage mal an, dann kann ich dir eventuell eine Verallgemeinerung nennen.

---

Das wäre super!

Ich habe folgendes Theorem kennengelernt:

Theorem 3.5. (Chinesischer Restsatz)

Seien m_1, . . . , m_n ∈ Z paarweise teilerfremd.

Dann hat das System von Kongruenzen mod m_1 mod m_2
x = a_1 mod m_1

x = a_2 mod m_2

...

x = a_n mod m_n

genau eine Lösung x ∈ Z mit 0 ≤ x < m := m_1 * ... m_n.

---

Wenn du mit $p_i$ paarweise verschiedene Primzahlen meinst tritt doch genau der Fall ein, dass die $m_i := p_i^{z_i}$ paarweise teilerfremd sind? Dann kannst du diese Aussage anwenden.

Falls die $p_i$ nicht paarweise verschieden sein müssen und du z.B. Moduli $2^2 = 4$ und $2^3 = 8$ gleichzeitig zulassen willst liegt natürlich keine p.w. Teilerfremdheit mehr vor.

Allgemeiner gilt aber:

Sind $m_1,..., m_n \in \mathbb N$ und $a_1,..., a_n \in \mathbb Z$, dann hat das System linerarer Kongruenzen

$$\begin{aligned} x &\equiv a_1 \mod (m_1) \\ &\kern+1.4ex\vdots \\ x &\equiv a_n \mod (m_n) \end{aligned}$$

genau dann eine eindeutige Lösung $x \in \mathbb Z$ mit $0 \le x < \operatorname{kgV}(m_1,...,m_n)$, wenn $\forall i \neq j$ gilt

$$a_i \equiv a_j \mod (\operatorname{ggT}(m_i,m_j))$$

---

Genau, das ist mir klar.

Es geht mir hierbei nur leider um eine Verallgemeinerung der Aussage für quadratische Kongruenzen, da ich sie nicht für lineare Kongruenzen, sondern für quadratische nutzen möchte.

Ich habe etwas von Isomorphismen in der Aussage für Hauptidealringe gelesen, aber das konnte ich ehrlich gesagt nicht so richtig nachvollziehen.

---

Oh sorry ich habe die Quadrate links übersehen, ich schreib später etwas dazu. Der Ansatz den Isomorphismus aus dem verallgemeinerten chinesischen Restsatz zu betrachten ist aber schon einmal gar nicht so schlecht.

---

Nein, alles gut. Vielen Dank für deine Hilfe!

Answer 1

Die additive Gruppe eines Rings ist ja nach Definition immer abelsch und somit auf natürliche Weise eine $\mathbb Z$-Algebra, denn für einen Ring $R$ haben wir für $x \in R$ und $n \in \mathbb Z$ die natürliche "Skalarmultiplikation"

$$n \cdot x ~:= \begin{cases} x + ... + x & \text{falls } n > 0 \text{ (Summe hat n Summanden)}\\0_R & \text{falls } n=0\\ -((-n)\cdot x)& \text{falls } n < 0\end{cases}$$

Zuerst einmal sollten wir zwei ganz allgemeine Aussagen besprechen:

Sind $R, ~S$ Ringe und ist $\varphi ~:~ R \to S$ ein Ringisomorphismus, sowie $f = \sum_{i=0}^k f_i \cdot t^i \in \mathbb Z[t]$ ein Polynom mit ganzzahligen Koeffizienten, dann gilt für alle $x \in R$:

$$f(x) = 0_R \iff f(\varphi(x)) = 0_S$$

Der Beweis ist nicht schwer:

Es ist ganz allgemein $$f(\varphi(x) ) = \sum_{i=0}^k f_i\varphi(x)^i = \sum_{i=0}^k f_i\varphi(x^i) = \varphi(\sum_{i=0}^k f_i \cdot x^i) = \varphi(f(x))$$

(Ein Isomorphismus vertauscht mit Summen, Produkten und Invertierung im Ring, also vertauscht er insb. auch mit Skalarmultiplikation mit Elementen aus $\mathbb Z$, das ist ja im Prinzip nur Summation im Ring)

=> Falls $f(x) = 0_R$ ist also $f(\varphi(x)) = \varphi(f(x)) = \varphi(0_R) = 0_S$

<= Falls $f(\varphi(x)) = 0_S$, dann ist auch $\varphi(f(x)) = 0_S$ und da $\varphi$ ein Isomorphismus ist sind Urbilder eindeutig bestimmt, wegen $\varphi(0_R)=0_S$ muss also schon $f(x) = 0_R$ sein.

---

Zweite Aussage:

Sind $R_1,...,R_n$ Ringe und $f = \sum_{i=0}^k f_i \cdot t^i \in \mathbb Z[t]$ ein Polynom mit ganzzahligen Koeffizienten dann gilt für alle $(x_1,...,x_n) \in R_1 \times \dotsm \times R_n$ (Produktring):

$$f( (x_1,...,x_n) ) = (0_{R_1},...,0_{R_n}) \iff \forall i \in \{1,...,n\} ~:~ f(x_i) = 0_{R_i}$$

Beweis:

Auch hier gilt ganz allgemein:

$$\begin{aligned} f( (x_1,...,x_n) ) &= \sum_{i=0}^k f_i \cdot (x_1,...,x_n)^i \\&= \sum_{i=0}^k f_i \cdot (x_1^i,...,x_n^i) \\&= \left(\sum_{i=0}^k f_i \cdot x_1^i,..., \sum_{i=0}^k f_i \cdot x_n^i\right) \\&= (f(x_1),...,f(x_n)) \end{aligned}$$

Rest ist klar.

---

Wenn wir jetzt für $m = p_1^{e_1} \cdot ... \cdot p_n^{e_n }$ und ein Polynom $f \in \mathbb Z[t]$ die Kongruenz

$$f(x) \equiv 0 \mod (m)$$ lösen möchten, können wir das natürlich mit dem chinesischen Restsatz machen, indem wir erst einmal die Kongruenzen:

$$f(x) \equiv 0 \mod (p_i^{e_i}) \quad \forall i =1,...,n$$

separat lösen. Wenn wir für jede dieser Gleichungen eine Lösung $y_i$ finden, können wir daraus mit dem Isomorphismus aus dem chinesischen Restsatz eine Lösung für unsere ursprüngliche Kongruenz lösen. Wir haben ja den Isomorphismus:

$$\varphi ~:~ \mathbb Z /m \mathbb Z \to \mathbb Z /p_1^{e_1} \mathbb Z \times \dotsm \times \mathbb Z /p_n^{e_n} \mathbb Z$$

Wir wissen außerdem, dass $f(y_i) \equiv 0 \mod (p_i^{e_i})$, also nach der zweiten Aussage oben auch $f((y_1,...,y_n)) = (0,...,0)$. Da wir einen Isomorphismus haben, gibt es ein Urbild: $x := \varphi^{-1}((y_1,...,y_n))$. Und nach der ersten Aussage oben ist:

$$f(x) = 0 \iff f( \varphi^{-1}((y_1,...,y_n))) = 0 \iff f(\varphi( \varphi^{-1}((y_1,...,y_n)))) = f((y_1,...,y_n))=(0,...,0)$$

Und da die rechte Aussage erfüllt ist, ist dann auch die linke Seite erfüllt.

Ein Beispiel zur Anwendung auf quadratische Polynome folgt gleich in einem Kommentar.

Comments

Sagen wir mal du möchtest ein $x \in \mathbb Z$ finden, s.d.

$$x^2 \equiv 6 \mod (75) \iff x^2 - 6 \equiv 0 \mod (75)$$

es ist $75 = 3 \cdot 5^2$ wir bestimmen also zunächst Lösungen für

$$x^2 \equiv 6 \equiv 0 \mod (3)$$

Naja gut modulo 3 ist die einzige Lösung 0.

$$x^2 \equiv 6 \equiv 0 \mod (25)$$

Und hier muss man sich jetzt überlegen wann Zahlen Quadrate modulo Primzahlpotenzen sind: https://en.wikipedia.org/wiki/Quadratic_residue#Prime_power_modulus

$6 = 5^0 \cdot 6$ ist ein Quadrat modulo 25, da $6 \equiv 1 \mod (5)$ ein Quadrat ist. Wenn man sich nur fragt OB es Lösungen gibt ist man jetzt fertig. Wenn man die Lösungen braucht muss man jetzt weiter rechnen.

Man findet z.b. $9^2 \equiv 6 \mod (25)$ und $(25-9)^2 \equiv 16^2 \equiv 6 \mod (25)$.

Die Lösungen im Produktring sind also (0,9), (0,16). Daraus kann man jetzt die gesuchten Lösungen:

9 und 66

berechnen.

---

Beispiel mit keiner Lösung:

$$x^2 \equiv 7 \mod (75)$$

Wir betrachten $x^2 \equiv 7\equiv 1 \mod (3)$, dass hat Lösungen 1, 2

und $x^2 \equiv 7 \mod (25)$. Das hat keine Lösungen, denn (siehe Link oben) $7 = 5^0 \cdot 7$ und $7 \equiv 2 \mod (5)$ ist kein Quadrat modulo 5.

Also können auch insgesamt keine Lösungen existieren.

Beantwortet das deine Frage soweit?

---

Vielen Dank, MatHaeMatician! Das hat mir sehr weitergeholfen.