Solve if possible and give all solutions, or explain why thereare no solutions.

Question

Solve if possible and give all solutions, or explain why thereare no solutions. x2 congruent -1 (mod 17) Solve if possible and give all solutions, or explain why thereare no solutions. x2 congruent -1 (mod 17)

Explanation / Answer

For starters, it suffices to search for solutions for x in therange {0,1,2,..16} since the final answer would be a residue classmodulo that answer, so if for instance a is a solution in this set,any integer congruent to a modulo 17 is also a solution. Secondly, if x is a solution, then so is -x, since x^2=(-x)^2. Third, 4^2=16=-1 mod 17 so 4 (and by the previous observation) and13 are both solutions. Note that 13 is congruent to -4 modulo17. Now we claim that there are no other solutions. Indeed, if x isneither 4, nor 13 but x^2 is congruent to -1 mod 17, then x^2=4^2mod 17, so x^2-4^2=(x-4)(x+4) is congruent to 0 mod 17 => 17divides (x-4)(x+4). Since 17 is prime, it divides one or theother. If 17 divides (x-4) then it is equivalent to saying that x is 4modulo 17. If 17 divides (x+4) then it is equivalent to saying that x is-4=13 modulo 17. Since we started with x being neither, we have acontradiction. Hence the only solutions are x congruent to 4 or -4 modulo 17.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.