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^2 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)