0
$\begingroup$

I am proving that for any integers $a,b$, it is impossible to write $a^2 - 5b^2 \equiv 2 \mod 4$. The first thing I have said is to assume $a,b$ are both even. So I have said

$$a,b \equiv 0 \, \, \mathrm{or} \, \, 2 \mod 4 \implies a^2, b^2 \equiv 0 \mod 4$$

so I was then going to say that this means we have

$$0 \mod 4 - 5(0 \mod 4) = 0 - 5\cdot 0 \mod 4 = 0 \mod 4.$$

By laws of modulo arithmetic, am I allowed to multiply that $0$ by $5$ like that? So, if we consider when $a,b$ are odd, I will get $a^2,b^2 \equiv 1 \mod 4$ and so I will get

$$1 - 5 \mod 4 = -4 \mod 4 = 0 \mod 4.$$

Is that allowed and correct?

If it is correct, I know I will still need to do when one of them is even and the other odd.

$\endgroup$
1
  • 1
    $\begingroup$ It isbasically correct. Notation is not being well used. It is best not to mix congruence notation and the operator mod used in some Computer Science books. But it certainly true that if for example $a^2\equiv 0\pmod{4}$ and $b^2\equiv 0\pmod{4}$ then $a^2-5b^2\equiv 0-(5)(0)\equiv 0\pmod{4}$. $\endgroup$ Commented Apr 18, 2013 at 19:51

3 Answers 3

1
$\begingroup$

Yes, you can. What you really want to say is $5 \cdot 0 = 0\mbox{ mod }4$, which means that $4$ must divide $5\cdot 0 - 0 = 0$, which of course it does since any number divides zero. I personally dislike using the $\mbox{mod}$ notation in strings of equations and would rather use the definition directly. For example, if $a$ and $b$ are both even, then $4$ divides both $a^2$ and $b^2$ and so $a^2 = 4m$ and $b^2 = 4n$ for some $m$ and $n$. Therefore, $a^2 - 5b^2 = 4m - 20n = 4(m - 5n)$ and so 4 also divides $a^2 - 5b^2$ meaning that $(a^2 - 5b^2) = 0 \mbox{ mod } 4$.

$\endgroup$
0
$\begingroup$

Hint $\rm\,\ 2\mid a\!-\!b\:\Rightarrow\:2\mid a\!+\!b\:\Rightarrow\:4\mid a^2\!-\!b^2\:\Rightarrow\:4\mid a^2\!-\!5b^2$

Generally $\rm\ mod\,\ \color{#c00}2n\!: \, a\,\equiv\, b\, \Rightarrow\, mod\,\ \color{#c00}4n\!: \ a^2 \equiv\, b^2\ \ by \ \ a^2\! = (b\!+\!\color{#c00}2nk)^2\!=b^2\!+\!\color{#c00}4nk(b\!+\!nk)\equiv b^2$

$\endgroup$
0
$\begingroup$

Using the fact that an even number is equal to $2(x)$ and an odd number is equal to $2x+1$ and plugging that in for a and b, seems to work out much simpler, as all of the numbers end up being equal to $0~~ \text{or}~~ 1 \pmod 4$.

For example,

$(2x+1)^2$- $5(2x+1)^2$ = $4x^2+4x+1 - 20x^2 - 20x-5$

which, in (mod 4) is just equal to 0.

Using the same application for even numbers in the form of $2(x)$ you will clearly see this congruence can never be true

$\endgroup$
1
  • 1
    $\begingroup$ are_they_tasty? $\endgroup$
    – Martin
    Commented Apr 21, 2013 at 22:46

You must log in to answer this question.

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