-2

I tried to prove the following question using contrapositive proof:

"Prove that if $a\in\mathbb Z$, then not $4\mid(a^2+1)$"

And I got to a $a=\sqrt{4k-1}, k\in\mathbb Z$

My question is: How do we show that $a=\sqrt{4k-1}, k\in\mathbb Z$ and $a\in\mathbb Z$

Mengen Liu
  • 109
  • 2
    You made the problem more complicated, rather than simplifying it. Hint: for the start, if $4\mid a^2+1$, would $a$ be even or odd? –  Sep 25 '22 at 19:03
  • I have already answered my question using proof by cases. But I wish to prove $a=\sqrt{4k-1}, k\in\mathbb Z$ – Mengen Liu Sep 25 '22 at 19:06
  • No, you wish to prove that it is cannot happen that $a=\sqrt{4k-1}$ for any integers $a,k\in\mathbb Z$. And, okay, fair enough, you don't want to use distinguishing cases anywhere in the proof, even if the proof is legitimately by contradiction. Why do you think the conclusion "$a$ must be odd because, if it was even, $a^2+1$ would be odd" would count as "distinguishing cases"? (Isn't it, sort-of, a mini-proof-by-contradiction-inside-a-proof-by-contradiction?) –  Sep 25 '22 at 19:12

3 Answers3

1

With your Method, you have to show that $a=\sqrt{(4k-1)}$ has no Integer Solution.

Alternately, we can Directly Prove the Original Claim by taking $a=2A$ or $a=2A+1$ , where we will get $a^2+1=4A^2+1=4k+1$ or $a^2+1=4A^2+4A+1+1=4k+2$ , hence it is not $4|(a^2+1)$

Without "Distinguishing Cases" :
Let $a=2A+P$ where $P$ is the Parity , either $1$ or $0$.
Then $a^2+1=4A^2+4AP+P^2+1=4k+(P+1)$ [[ We are using $1^2=1$ & $0^2=0$ ]]
With $(P+1)$ must be $1$ or $2$ , We can see that it is not $4|(a^2+1)$

Prem
  • 9,669
1

This is, of course, a very well-known proof, and may indeed be very similar to the proof using "distinguishing cases" that you already have. All I am doing below is adapting this proof so that it sounds purely as a proof by contradiction (twice over). Hope that helps.

On with the proof! Suppose the opposite, i.e. that there exists $a\in\mathbb Z$ such that $4\mid a^2+1$.

Let's first prove that $a$ must be odd. Suppose the opposite, i.e. that $a$ is even. But then, $a^2$ will be even, and so $a^2+1$ would be odd, and therefore not divisible by $4$. Contradiction.

Now, knowing that $a$ is odd, it means that $a=2k+1$ for some $k\in\mathbb Z$. Then,

$$a^2+1=(2k+1)^2+1=4k^2+4k+2=4(k^2+k)+2$$

which is not divisible by $4$ because it has remainder $2$ when divided by $4$. Contradiction (again)!

  • 2
    More generally, division of the proof into "proofs by exhaustion", "proofs by distinguishing cases", "proofs by contraposition", "proofs by contradiction" is artificial and only exists for educational purposes (to be used when the students are introduced to the concept of proof for the first time). In "real" maths, all those techniques are seamlessly combined with each other to produce proofs, and there is no need to call them out. Maybe a good analogy is music, where your first examples are melodies using notes C, then D, then E... but nobody in the real world classifies... –  Sep 25 '22 at 20:00
  • ... musical melodies as "melodies using note C", " melodies using note D" etc. –  Sep 25 '22 at 20:00
  • I guess, you had a change in opinion about answering such questions, after advising me to not answer ! More-over, assuming that some comments to the Question Post were deleted, I think I do not have the "complete context", to the current Situation ! – Prem Sep 27 '22 at 10:22
  • @Prem Fair enough. I have deleted my comment advising you to not answer. I did have a change of heart because, although usually the community would close questions for which people think there is lack of context, it did not happen with this question. Thus, it is not a "low quality question", I suppose. –  Sep 27 '22 at 16:27
0

I'm believe you're looking for a proof by the contrapositive, so here's how I'd do it that way. Suppose $4 | (a^2+1)$. This means $a^2=3 \mod 4$. But all squares of integers are either $0$ or $1 \mod 4$. So $a$ is not an integer.

Merosity
  • 2,489
  • 1
  • 8
  • 16