Chinesischer Restesatz Wurzel ziehen

Question

wie Ziehe ich die wurzel aus 37 mod 77 mit dem  Chinesischen Resetesatz?

also wie finde ich ein b für das gilt b² mod 77 = 37 mod 77?

Also irgendwie zerlegt man ja zunächst 77 zu 7*11 aber ich bewege mich im kreis und weiß nicht wie ich irgendeine gleichung aufstellen kann in der form b mod 77= xyz mod 77

LG

Answer 1

Der chinesische Restsatz liefert den Isomorphismus

$$f: \mathbb{Z}/77\mathbb{Z} \to \mathbb{Z}/7\mathbb{Z} \times \mathbb{Z}/11\mathbb{Z}, \\x + (77) \mapsto (x + (7), x + (11))$$

Wenn $37 = b^2$ dann gilt auch $f (37)=f ( b^2) = f(b)^2$.

Es gilt $f(37)=(2,4)$, such also mal ein $(x,y)\in\mathbb{Z}/7\mathbb{Z} \times \mathbb{Z}/11\mathbb{Z},$ mit $(x,y)^2 = (x^2,y^2) =(2,4)$.

Berechne dann $b = f^{-1}((x,y))$. Das entspricht dem Lösen des Systems:

$$b \equiv x \mod (7)\\ b \equiv y \mod (11)$$

Falls du Fragen hast, gerne melden.

Comments

wäre das dann einfach

$$3 \equiv b \ mod 7$$

$$2 \equiv b \ mod 11$$

$$==> b \equiv 79 mod 77$$

ist das einfach das ergebnis?

ich muss sagen ich verstehe dadruch immer noch nicht wo genau wie die wurzel gezogen wird

---

x=3, y=2 sind mögliche Werte. Beim b hast du dich verrechnet 79 = 2 mod 7 und nicht =3.

Rauskommen sollte 24 und es gilt $$24^2 \equiv 37 \mod (77)$$

Die Idee ist hier einfach das Wurzelziehen in kleinere Ringe zu verlagern (was dann evtl schneller geht)