10
$\begingroup$

Prove that the equation $12x^2-y^2 = 1$ has no integer solutions.

I thought about taking this modulo some number to find a contradiction, but couldn't get anything. What should I do?

$\endgroup$
2
  • 5
    $\begingroup$ Work modulo $3$. $\endgroup$ Aug 8, 2016 at 17:27
  • 2
    $\begingroup$ Seems to work modulo $3$ you get $y^2=-1$ which isn't true for any integer modulo $3$ is it? $\endgroup$ Aug 8, 2016 at 17:27

3 Answers 3

13
$\begingroup$

Work modulo $3$. The congruence $y^2\equiv -1\pmod{3}$ does not have a solution.

But you have a choice, you can also work modulo $4$. For any square is congruent to $0$ or $1$ modulo $4$.

$\endgroup$
1
  • 3
    $\begingroup$ This also works mod $4$ since $y^2\not\equiv-1\pmod4$ $\endgroup$
    – robjohn
    Aug 8, 2016 at 19:12
4
$\begingroup$

Massive overkill: from the theory of Pell equations it is known that for any integer $D>0$ that is not a square, the equation $$ x^2-D y^2 = -1 $$ has a solution (hence infinite solutions) or not, depending on the length of the period of the continued fraction of $\sqrt{D}$. Since $$ \sqrt{12}=[3;\overline{2,6}] $$ the original equation $12x^2-y^2=1$ has no integer solutions.
Anyway, that is trivial $\!\!\pmod{3}$ or $\!\!\pmod{4}$.

$\endgroup$
3
$\begingroup$

I'll try to explain the idea of André's answer in a simple manner.

Note that if we divide any integer by $3$ there are only $3$ possibilities:

  1. We get a remainder of $0$
  2. We get a "remainder" of $1$ or $-2$
  3. We get a "remainder" of $2$ or $-1$

Hence any integer can be represented as one of the following:

$$3k+0$$

$$3k+1$$

$$3k+2$$

Where $k$ is an integer

As a side note, using this, if we compute:

$n^2$

By setting $n=3k+0,3k+1,3k+2$ we will notice that any perfect square can only have remainder $0$ or $1$ when divided by $3$.

Now going back to the equation you are interested in:

$$12x^2-y^2=1$$

Set $x=3k+z$ and $y=3u+z$ where $z$ is $0$, $1$ or $2$ and $k$ is any integer:

$$12(9k^2+6kz+z^2)-(9u^2+6uz+z^2)=1$$

This is equivalently:

$$12(9k^2+6kz+z^2)-(9u^2+6uz)-z^2=1$$

Or:

$$12(9k^2+6kz+z^2)-(9u^2+6uz)=1+z^2$$

The right hand side must only have remainder $1$ or $2$ when divided by $3$ (this holds for all integers $z$ from our calculation of $n^2$ but for simplicity just take our original $z=0,1,2$).

The left hand side on the other hand is divisible by $3$ and thus must have remainder $0$ when divided by $3$.

Thus we conclude that they can't possible be equal for integers $x$ and $y$ because they give different remainders when divided by $3$.

$\endgroup$
1
  • $\begingroup$ I think you need to set $x = 3k + z_1$ and $y = 3u + z_2$ $\endgroup$
    – idpd15
    Dec 11, 2017 at 13:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .