0

I am studying for an admission exam and I came to this system of congruences

$$x^2 \equiv 2 \text{ mod } 7 \hspace{1cm} x \equiv 1 \text{ mod } 5 $$

I know how to solve linear systems, but I don't know what to do with a quadratic one.

Could anyone explain me ho to solve it?

Thanks

Santiago
  • 186

1 Answers1

2

You can try to sub in first $3$ rests by $7$, so $1, 2, 3$. We get $$x^2\equiv 1, 4, 2\pmod7 $$ From this, $$x\equiv 3\,\lor x\equiv7-3=4 \pmod7$$ Now it's linear.

Jakobian
  • 10,247
  • Sorry, but i don't understand what are you doing. What do you mean by "You can try to sub in first 3 rests by 7, so 1,2,3."? – Santiago Oct 21 '18 at 19:33
  • @Santiago $(x+7k)^2 \equiv x^2 \pmod7$ so, we just need to consider $0, 1, 2, 3, 4, 5, 6$. But squaring them all would be a chore (in this case, not really, but we could for example try to solve for $43$ instead of $7$, and that would be $42$ cases to check), so we further see that $x^2 \equiv (7-x)^2 \pmod 7$, so we need to check only 3 first besides $0$ (which is irrelevant). – Jakobian Oct 21 '18 at 19:58
  • Ok, I got that part. How you conclude that $x\equiv 3 \vee x\equiv 7−3=4\text{ mod(7) }$ – Santiago Oct 21 '18 at 21:35
  • @Santiago Because $3^2=9\equiv 2 \pmod7$ – Jakobian Oct 22 '18 at 05:44