6

A positive integer $n$ is a perfect square. Prove that it cannot be of the form $4k+3$, where $k$ is an integer.

I tried to prove this by proof by contradiction: if $n$ is a perfect square, then its square root, say $x$, is an integer. Suppose $n$ is of the form $4k+3$. Then $$x^2= 4k+3$$ which we can also write as $$x^2\equiv3 \mod 4$$ However, this congruence has no solutions. Therefore our initial assumption that $n$ is of the form $4k+3$ was false and $n$ cannot be of the form $4k+3$.

I know there's something missing or wrong in this proof but I don't know what. Any help would be appreciated.

alexwlchan
  • 2,060
Paradox 101
  • 1,091
  • 1
    Nothing missing, it is a very nice proof (note that in fact one can show that odd squares and congruent to $1$ mod $8$). – Tobias Kildetoft Dec 18 '14 at 10:12
  • Can you explain how one would go about showing odd squares being congruent to 1 mod 8?Didn't get it. – Paradox 101 Dec 18 '14 at 10:16
  • Simply by writing $(2k+1)^2 = 4k^2 + 4k + 1 = 8\frac{k(k+1)}{2} + 1$ (note that the fraction is indeed an integer). – Tobias Kildetoft Dec 18 '14 at 10:17
  • 1
    Nothing is proved as "this congruence has no solutions" is not justified. –  Dec 18 '14 at 10:17
  • @YvesDaoust That depends on the level one wants the proof. Any statement whose validity can be checked by testing a (small) finite number of cases need not usually be further justified. – Tobias Kildetoft Dec 18 '14 at 10:22
  • 1
    @YvesDaoust can you explain how i should correct this proof? – Paradox 101 Dec 18 '14 at 10:23
  • 1
    @TobiasKildetoft: if you skip that part, the proof is completely void. "Any statement whose validity can be checked by testing a (small) finite number of cases need not usually be further justified.": your saying. –  Dec 18 '14 at 10:24
  • 3
    Obviously by proving that $x^2\equiv3\mod4$ is impossible. –  Dec 18 '14 at 10:25
  • That's it? So basically I've claimed that it has no solutions but haven't shown how and that's all what's missing? – Paradox 101 Dec 18 '14 at 10:32
  • That's 90% of the proof. –  Dec 18 '14 at 10:33
  • 2
    What you've done is trivial. What needs to be proved is your statement that the congruence has no solutions, as Yves points out. – David Mitra Dec 18 '14 at 10:34
  • @DavidMitra I disagree. Checking $4$ congruences is trivial. Getting the idea to work mod $4$ is the main thing. – Tobias Kildetoft Dec 18 '14 at 10:37
  • 1
    @TobiasKildetoft: what $4$ congruences ? Two are enough. Leaving such "details" implicit is risky. –  Dec 18 '14 at 10:43
  • 2
    @TobiasKildetoft I think that pointing out that "$n^2$ is not of the form $4k+3$" is equivalent to "the congruence $n^2\equiv 3,\text{mod}4$ has no solutions" is certainly not the "intended proof" here. – David Mitra Dec 18 '14 at 10:45
  • Replacing $n=4k+3$ by $n\equiv3\mod 4$ is no great deal. The true idea is that the congruential equation can be solved by a finite case study, which is not evoked and even less made explicit. An allusion to the known properties of quadratic residues would have been a valid argument too, but my feeling is that such an answer to the exercise would get an F for laziness. –  Dec 18 '14 at 11:10
  • @Paradox101 The missing part just amounts to adding $0^2\equiv0\pmod{4}$, $1^2\equiv1\pmod{4}$, $2^2\equiv0\pmod{4}$, $3^2\equiv1\pmod{4}$. – egreg Dec 18 '14 at 11:42
  • @egreg: what's the use of checking for $2$ and $3$ ? $0$ and $1$ suffice. I believe in a confusion between $x\bmod4$ and $x^2\bmod4$. The devil is in the details. –  Dec 18 '14 at 16:41
  • @YvesDaoust Excluding $0$ and $2$ would require justification; not a long one, of course, but $2^2=4$ is shorter. – egreg Dec 18 '14 at 16:42
  • @egreg: excluding $0$ and $2$ will not work. And using with $x\mod 4$ deserves an explanation why this covers all cases for $x^2$. Yet another implicit assumption. –  Dec 18 '14 at 16:49

3 Answers3

6

For even $\sqrt n=2m$, $n=(2m)^2=4m^2\equiv\color{blue}0\mod 4$.

For odd $\sqrt n=2m+1$, $n=(2m+1)^2=4m^2+4m+1\equiv\color{blue}1\mod 4$.

So you never achieve congruency to $\color{blue}3$, as there are no other cases.

As a byproduct, this also establishes that $4k+2$ is never a perfect square.

2

$4k+3$ is an odd number. A square of an even number is even. So the only candidates to have a square of the form $4k +3$ are $4a +1$ and $4a+3$.

Now $(4a+1)(4a+1) = 16a^2+8a+1$ and that is of the "form" $4k+1$. Also $(4a+3)(4a+3) = 16 a^2 + 24a + 9 = 16 a^2 + 24 a + 8 + 1$ is of the form $4k+1$.

QED.

mick
  • 15,946
2

Assume to the contrary that there is integer $\ k$ such that $\ 4k+ 3$ is a perfect square

Let $\ x^2= 4k+3$

$\ 4k+3 = 2(2k+2)+1 \implies x^2$ is odd which follows $\ x$ is also odd

Then

Let $\ x= 2a+1$ for some integer $\ a$

Now we can write that \begin{align} &x^2 = 4k+3\\ \implies &(2a+1)^2 =4k+3\\ \implies &4a^2+4a+1 = 4k+3 \\ \implies &4a^2+4a-4k = 2 \\ \implies &4(a^2+a+k) = 2 \\ \implies &2(a^2+a+k)= 1 \\ \end{align} which is impossible since (a^2+a+k) is integer qed

Manjoy Das
  • 1,006
  • 7
  • 21
Alcarli
  • 31