Jak rozwiązać tę kwadratową kongruencję? $27w^2+20w+35 \equiv 0 \pmod{23}$ [duplikować]

Question

Dany $27w^2+20w+35 \equiv 0 \pmod{23}$

Jak rozwiązać tę kwadratową kongruencję? Wszelkie podpowiedzi są mile widziane. Ukończyłem kwadrat, więc uzyskałem$27(x+\frac{10}{27})^2+\frac{845}{27} \equiv 0 \pmod{23} $ Potrzebuję 2 rozwiązań w systemie najmniej pozostałości, które są poprawnymi odpowiedziami: $w\equiv 6 \pmod{23}$ i $w \equiv 12 \pmod{23}$

Answer 1

Aby ułatwić obliczenia ręczne, przepisujemy równanie na $$4w^2-3w+12\equiv0\bmod23$$ Podzielić przez wiodący współczynnik, czyli pomnożyć przez $4^{-1}=6$: $$w^2+5w+3\equiv0\bmod23$$ Teraz zastosuj wzór kwadratowy: $$w\equiv\frac{-5\pm\sqrt{13}}2\bmod23$$ Musimy obliczyć pierwiastki kwadratowe z $13$ w $\mathbb Z_{23}$. $6$ można łatwo zweryfikować jako jeden root, więc $-6$ jest inny: $$w\equiv\frac{-5\pm6}2\equiv9\pm3\bmod23$$

Answer 2

Wskazówka:

$$\pmod{23}: 4w^2-3w+12\equiv 0 \implies 8w^2-6w+1\equiv 0 \implies (2w-1)(4w-1)\equiv 0. $$

Aktualizacja Aby uzasadnić, dlaczego mnożę 2 do$4w^2-3w+12$, łatwiej jest pracować z liczbami całkowitymi niż ułamkami, więc aby ukończyć kwadrat, zachowując wszystkie współczynniki całkowite, mnożymy przez 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}$$

a teraz widzisz dlaczego.

Aktualizacja 2: Podoba mi się sposób, w jaki Parcly Taxel tworzy kwadratowe moniki jako pierwsze:

$$w^2+5w+3\equiv0\pmod{23}$$

Potem można to zrobić trochę szybciej:

$$w^2-18w+3\equiv 0 \implies (w-9)^2 = 78\equiv 9 =3^2 \implies (w-6)(w-12) \equiv 0 \pmod{23}$$

Answer 3

Od $27 \equiv 4$ możemy zapisać równanie jako $4w^2 + 20w + 35 \equiv 0.$ Wypełnienie kwadratu daje $(2w+5)^2 + 10 \equiv 0,$ to znaczy $(2w+5)^2 \equiv -10.$ Ale $-10 \equiv -10+2\cdot 23=36=6^2,$ więc $2w+5\equiv\pm 6,$ to znaczy $2w=-5\pm 6.$

Walizka $+$: $2w=-5+6=1\equiv 1+23=24=2\cdot12$ więc $w\equiv12.$

Walizka $-$: $2w=-5-6=-11\equiv -11+23=12=2\cdot6$ więc $w\equiv6.$

Stąd rozwiązania $w=12$ i $w=6$.