การหารากของพหุนามโดยใช้กำลังสองซึ่งกันและกัน
พหุนามหรือไม่ $X^2− X + 19$ มีรากใน $\mathbb Z/61\mathbb Z$เหรอ? ฉันไม่แน่ใจว่าจะแก้ไขปัญหานี้อย่างไร แต่ฉันได้สรุปวิธีการแก้ไขปัญหาเหล่านี้ในปัญหาด้านล่าง
กำลังสองหรือไม่ $X^2 -59$ มีรากใน $\mathbb Z/61\mathbb Z$เหรอ?
สิ่งที่ฉันได้ทำไปแล้วคือถามตัวเองว่า $59$คือกากกำลังสอง กล่าวอีกนัยหนึ่งคืออะไร$59/61$เหรอ? โดยการตอบแทนซึ่งกันและกันเรามี$59/61 = 61/51 = 10/51$ ตั้งแต่ $61 ≡ 10\bmod51$. $10$ ไม่ใช่ไพรม์ดังนั้นเราจะแยกตัวประกอบเป็น $(2/51)*(5/51).$ แต่ $2/51$ คือ $-1$ ตั้งแต่ $3 ≡ 51\bmod8$. เราจึงเขียนใหม่เป็น$-1 * (5/51)$และโดยการตอบแทนซึ่งกันและกัน $5/51 = 51/5 = 1/5$ ตั้งแต่ $1 ≡ 51\bmod5$. ดังนั้น$-1*(5/51) = - (1/5) = -1 (1) = -1$ดังนั้น $x^2 - 59$ ไม่มีราก
คำตอบ
$$x^2-x+19\equiv x^2-x-42=(x+6)(x-7).$$ ตอนนี้จบได้ไหม
เติมเต็มกำลังสอง
$X^2-X+19\equiv0\bmod61\iff 4X^2-4X+76\equiv0\bmod61$
$\iff (2X-1)^2\equiv-75\equiv47\equiv169=13^2\bmod61$
$2X-1\equiv\pm13\bmod61$
$2X\equiv 14$ หรือ $-12\bmod 61$
$X\equiv7$ หรือ $-6\bmod 61$
วิธีทั่วไปในการแก้กำลังสองคือการทำให้กำลังสองสมบูรณ์ ถ้าคุณมี$ax^2+bx+c \equiv 0 \pmod{p}$ จากนั้นการกรอกสแควร์จะทำให้คุณ $y^2\equiv d \pmod{p},$ ที่ไหน $y = 2ax+b$ และ $d=b^2-4ac.$
สิ่งที่ดีก็คือ $y$ คืออนุพันธ์ของทางซ้ายมือดั้งเดิมและ $d$คือการแยกแยะตามปกติของกำลังสอง ดังนั้นสำหรับปัญหาของคุณ:
$y = 2x+1$ และ $d=1^2-4\cdot 19 = -75$.
ดังนั้นถ้า $-75$ เป็นกากกำลังสองคุณแก้ได้ $y$ จากนั้นจึงแก้ปัญหาสำหรับ $x$.