Proof check modulo arithmetic

Question

what is wrong with this proof, so I am supposed to show $7x^2-15y^2=1$ has no integer solutions...

so since $7x^2=1+3(5y^2)$ so $7x^2\equiv 1 \pmod{3}$ hence in mod $3$, $x\equiv 0, 1$ or $2$ so $x^2\equiv 0, 1$ and $7x^2\equiv0$ or $7$ and since $7$ is congruent to $1 \bmod3$ I end up with solutions.

I also tried it with mod $5$ since $15y^2=5(3y^2)$ and I ended up with no solution so why not in case above?

@labbhattacharjee I tried it with mod5 it worked but don't know why it doesn't with 3... — , May 04 '18 at 01:20
@Eden For future reference, \equiv gives you the congruence symbol. — B. Mehta, May 04 '18 at 01:21
".... I end up with solutions"; here's the catch: Having solutions in $\Bbb Z_n$ doesn't necessarily imply having solutions in $\Bbb Z$ — Prasun Biswas, May 04 '18 at 01:35
@PrasunBiswas I see thanks! but so why would not getting solutions in $\Bbb{Z}_n$ imply no solutions in $\Bbb{Z}$ ? — , May 04 '18 at 01:38
Because if an equality holds in $\Bbb Z$, it should also hold as a congruence in $\Bbb Z_n$ ($a=b\implies a\equiv b\pmod n$ but not the other way around) — Prasun Biswas, May 04 '18 at 01:44

lhf · Accepted Answer · 2018-05-04T02:00:56.663

To prove that a polynomial equation has no integer solutions, it is enough to prove that it has no solutions mod $m$, for some $m$, usually prime. (*)

However, if the equation has solutions mod $m$, for some $m$, it does not necessarily follow that the equation has integer solutions.

The equation $7x^2-15y^2=1$ has solutions mod $3$, but not mod $5$, and so has no integer solutions.

(*) However, there are many polynomial equations that have no integer solutions, but have solutions mod $p$, for all prime $p$. One example is $(x^2-2)(x^2-3)(x^2-6)=0$.

Will Jagy · Answer 2 · 2018-05-04T01:51:16.543

0

There are also no integer solutions to $$ 13 x^2 - 17 y^2 = 1. $$ We know that there are rational solutions, therefore $p$-adic, as we can solve $$ 13 x^2 - 17 y^2 = 25 $$ in integers. $$ 13 \cdot 7^2 - 17 \cdot 6^2 = 637 - 612 = 25 $$

edited May 04 '18 at 01:51

answered May 04 '18 at 01:42

Will Jagy

139,541

Proof check modulo arithmetic

2 Answers2