How can I prove that this equality is impossible?

Question

I need to prove that:

$$(6 + x^2) \mod 7 = 4$$

is not possible for $x\in \mathbb{N}$.

I know the proof would be by contradiction (i.e. assume we have a value of $x$ that solves this equation and reach a contradiction), but I'm not sure here to go from there. Any help would be appreciated.

You can simply plug in the $7$ values ($0$ through $6$) for $x$ and see that the equality does not hold. — tylerc0816, Dec 05 '13 at 21:15
@Govind Parmar : this doesn't look like a good problem for the contradiction technique — Stefan Smith, Dec 06 '13 at 02:47

score 6 · Accepted Answer · answered Dec 05 '13 at 21:11

Note that $$(x^2+6) \pmod{7} = 4 \iff x^2 \pmod{7} \equiv 5 \pmod7$$ Now we have $$ x^2 \equiv \begin{cases} 0\pmod7 & \text{if } x \equiv 0 \pmod7\\ 1\pmod7 & \text{if } x \equiv \pm 1 \pmod7\\ 4\pmod7 & \text{if } x \equiv \pm 2 \pmod7\\ 2\pmod7 & \text{if } x \equiv \pm 3 \pmod7\\ \end{cases} $$ Hence, $x^2 \pmod{7} \equiv 5 \pmod7$ has no solution.

score 5 · Answer 2 · answered Dec 05 '13 at 21:10

5

HINT: If $6+x^2\bmod 7=4$, then $x^2\bmod 7=5$.

answered Dec 05 '13 at 21:10

Brian M. Scott

616,228

How can I prove that this equality is impossible?

2 Answers2