Wie kann man diese quadratische Kongruenz lösen? $27w^2+20w+35 \equiv 0 \pmod{23}$ [Duplikat]
Gegeben $27w^2+20w+35 \equiv 0 \pmod{23}$
Wie kann man diese quadratische Kongruenz lösen? Alle Hinweise sind willkommen. Ich habe das Quadrat fertiggestellt, also habe ich es erhalten$27(x+\frac{10}{27})^2+\frac{845}{27} \equiv 0 \pmod{23} $ Ich brauche 2 Lösungen im System mit den geringsten Rückständen, die die richtigen Antworten sind: $w\equiv 6 \pmod{23}$ und $w \equiv 12 \pmod{23}$
Antworten
Zur Erleichterung der manuellen Berechnung schreiben wir die Gleichung wie folgt um $$4w^2-3w+12\equiv0\bmod23$$ Teilen Sie durch den führenden Koeffizienten, dh multiplizieren Sie mit $4^{-1}=6$:: $$w^2+5w+3\equiv0\bmod23$$ Wenden Sie nun die quadratische Formel an: $$w\equiv\frac{-5\pm\sqrt{13}}2\bmod23$$ Wir müssen die Quadratwurzeln von herausfinden $13$ im $\mathbb Z_{23}$. $6$ ist leicht als eine Wurzel zu verifizieren, so $-6$ ist der andere: $$w\equiv\frac{-5\pm6}2\equiv9\pm3\bmod23$$
Hinweis:
$$\pmod{23}: 4w^2-3w+12\equiv 0 \implies 8w^2-6w+1\equiv 0 \implies (2w-1)(4w-1)\equiv 0. $$
Update Um zu rechtfertigen, warum ich 2 mit multipliziere$4w^2-3w+12$Es ist einfacher, mit ganzen Zahlen als mit Brüchen zu arbeiten. Um also das Quadrat zu vervollständigen und dabei alle Koeffizienten ganzzahlig zu halten, multiplizieren wir sie mit 16:
$$16(4w^2-3w+12)=64w^2-48w+192=(8w-3)^2+183\equiv (8w-3)^2-1 = (8w-2)(8w-4)=8(4w-1)(2w-1) \pmod{23}$$
und jetzt siehst du warum.
Update 2: Ich mag Parcly Taxels Art, zuerst das quadratische Monic zu machen:
$$w^2+5w+3\equiv0\pmod{23}$$
Danach geht es etwas schneller:
$$w^2-18w+3\equiv 0 \implies (w-9)^2 = 78\equiv 9 =3^2 \implies (w-6)(w-12) \equiv 0 \pmod{23}$$
Schon seit $27 \equiv 4$ wir können die Gleichung schreiben als $4w^2 + 20w + 35 \equiv 0.$ Das Ausfüllen des Quadrats gibt $(2w+5)^2 + 10 \equiv 0,$ dh $(2w+5)^2 \equiv -10.$ Aber $-10 \equiv -10+2\cdot 23=36=6^2,$ damit $2w+5\equiv\pm 6,$ dh $2w=-5\pm 6.$
Fall $+$:: $2w=-5+6=1\equiv 1+23=24=2\cdot12$ damit $w\equiv12.$
Fall $-$:: $2w=-5-6=-11\equiv -11+23=12=2\cdot6$ damit $w\equiv6.$
Somit sind die Lösungen $w=12$ und $w=6$.