Mathematical-Reasoning · Unit 8 · Video 3 · Interactive Practice

Proving Nonexistence by Contradiction: Even Equals Odd

IKey Formulas

Formula	Name	What it gives the proof
$\neg(P \to Q) \equiv P \wedge \neg Q$	Negation of a conditional	A proof by contradiction assumes $P$ and also $\neg Q$ : one more assumption than a direct proof
$\neg\big(\neg (\exists z)\, R(z)\big) \equiv (\exists z)\, R(z)$	Negation of a nonexistence claim	Assume the object exists, then calculate with it
$4k + 2 = 2(2k + 1)$ and $6m + 3 = 2(3m + 1) + 1$	Even and odd forms	Every $n \equiv 2 \pmod 4$ is even; every $n \equiv 3 \pmod 6$ is odd
$(2m + 1)^2 + (2n + 1)^2 = 4(m^2 + m + n^2 + n) + 2$ and $(2k)^2 = 4k^2$	Two odd squares vs an even square	The sum is $2$ more than a multiple of $4$ ; an even square is a multiple of $4$

Key Insight: When a conclusion says "not" or "does not exist", its negation hands you an object to calculate with. Both proofs here end with an even integer equal to an odd one, and no integer is both.

IIVisualization 1 — Can One Integer Be in Both Lists?

No integer satisfies $n \equiv 2 \pmod 4$ and $n \equiv 3 \pmod 6$ at once, because of parity.

n 6

IIIVisualization 2 — The Nonexistence Proof, Step by Step

Each step adds a fact about $z^2$ , until $z^2$ cannot equal any sum $x^2 + y^2$ of two odd squares.

Step 1

Step 1 — Assume the negation. There are odd integers

x

and

y

and an integer

z

with

x^2 + y^2 = z^2

Step 2 — Name the odd integers. There are integers

m

and

n

with

x = 2m + 1

and

y = 2n + 1

; the letters differ because

x

and

y

need not be equal.

Step 3 — Stage 1: $z^2$ is even.

x^2 + y^2 = 4m^2 + 4m + 1 + 4n^2 + 4n + 1 = 2(2m^2 + 2m + 2n^2 + 2n + 1),

z^2 = x^2 + y^2

is even.

Step 4 — Stage 2: $z$ is even. For each integer

a

, if

a^2

is even then

a

is even (proved in Unit 7 by contrapositive). So

z

is even, and

z = 2k

for some integer

k

Step 5 — Substitute for $x$ , $y$ and $z$ .

(2m + 1)^2 + (2n + 1)^2 = (2k)^2 \quad\Longrightarrow\quad 4m^2 + 4m + 4n^2 + 4n + 2 = 4k^2.

Step 6 — Divide by $2$ : odd equals even.

2(m^2 + m + n^2 + n) + 1 = 2k^2.

The left side is odd and the right side is even, and no integer is both. This contradiction shows that no such

z

exists.

\blacksquare

💡 The strip stops at $50$ , but Steps 5 and 6 settle every integer at once: $4(m^2 + m + n^2 + n) + 2$ is never a multiple of $4$ .

IVVisualization 3 — Where the Hypothesis "Both Odd" Matters

Two squares can add to a square, as $3^2 + 4^2 = 5^2$ , but never when both are odd.

VQuiz Questions

Problem 1 · What Does the Proof Assume?

Given: For each integer $n$ , if $n \equiv 2 \pmod 4$ , then $n \not\equiv 3 \pmod 6$ . Which assumption starts a proof by contradiction?

✅ Correct!

\neg(P \to Q) \equiv P \wedge \neg Q

: keep the hypothesis

n \equiv 2 \pmod 4

and add the opposite of the conclusion,

n \equiv 3 \pmod 6

❌ That assumes the conclusion.

n \not\equiv 3 \pmod 6

is what the proposition claims; a proof by contradiction assumes its negation,

n \equiv 3 \pmod 6

❌ The hypothesis stays. Only the conclusion is negated:

\neg(P \to Q) \equiv P \wedge \neg Q

, so

n \equiv 2 \pmod 4

is kept, not denied.

❌ That is the contrapositive.

\neg Q \to \neg P

is equivalent to the proposition itself, so it is something to prove, not an assumption, and it is a conditional, not a pair of facts about

n

Show solution

Let $P$ be " $n \equiv 2 \pmod 4$ " and $Q$ be " $n \not\equiv 3 \pmod 6$ ". The negation of $P \to Q$ is

\neg(P \to Q) \equiv P \wedge \neg Q,

so the proof assumes $n \equiv 2 \pmod 4$ and $n \equiv 3 \pmod 6$ . Then $n - 2 = 4k$ and $n - 3 = 6m$ for integers $k$ and $m$ , so $4k + 2 = 6m + 3$ , that is, $2(2k + 1) = 2(3m + 1) + 1$ : an even integer equals an odd one, a contradiction.

Problem 2 · Negating a Nonexistence Claim

Given: For all odd integers $x$ and $y$ , there is no integer $z$ with $x^2 + y^2 = z^2$ . Which statement does a proof by contradiction assume?

✅ Correct! The negation of "for all odd

x, y

, no

z

" is "for some odd

x, y

, some

z

": the object exists, so there is a specific

z

to calculate with.

❌ That agrees with the proposition. It says some odd pair has no matching

z

, which is a special case of the claim, not its negation.

❌ The outer quantifier must flip too. Negating "for all

x, y

" gives "there exist

x, y

"; this option negated only the inner part and asks for far more than the negation says.

❌ The hypothesis stays. The negation still has

x

and

y

odd; a pair with an even entry, such as

3^2 + 4^2 = 5^2

, says nothing about the proposition.

Show solution

Write the proposition with quantifiers:

(\forall x, y \in \mathbb{Z})\big[(x, y \text{ odd}) \to \neg (\exists z \in \mathbb{Z})(x^2 + y^2 = z^2)\big].

Negate: the $\forall$ becomes $\exists$ , and $\neg(P \to Q) \equiv P \wedge \neg Q$ keeps " $x, y$ odd" and removes the inner negation:

(\exists x, y \in \mathbb{Z})\big[(x, y \text{ odd}) \wedge (\exists z \in \mathbb{Z})(x^2 + y^2 = z^2)\big].

So the proof assumes there are odd integers $x, y$ and an integer $z$ with $x^2 + y^2 = z^2$ , then derives $2(m^2 + m + n^2 + n) + 1 = 2k^2$ , an odd integer equal to an even one.

Problem 3 · A New Pair of Congruences

Given: Prove by contradiction: for each integer $n$ , if $n \equiv 3 \pmod 4$ , then $n \not\equiv 2 \pmod 8$ . Assume $n \equiv 3 \pmod 4$ and $n \equiv 2 \pmod 8$ .

Using the definition of congruence and solving each equation for $n$ , which equation follows?

Factoring out $2$ turns that equation into which odd = even statement?

✅ Correct!

4k + 3 = 8m + 2

becomes

2(2k + 1) + 1 = 2(4m + 1)

: an odd integer equals an even one, so

n \not\equiv 2 \pmod 8

❌ Check the equation.

4 \mid n - 3

gives

n = 4k + 3

and

8 \mid n - 2

gives

n = 8m + 2

; set the two expressions for

n

equal.

❌ Check the factoring. Expand each side of your choice and compare with

4k + 3

and

8m + 2

❌ Different multipliers need different letters. Nothing says the integer with

n - 3 = 4k

equals the one with

n - 2 = 8m

; using

k

twice adds an assumption the proof does not have.

❌ Check the signs.

n - 3 = 4k

solves to

n = 4k + 3

, not

4k - 3

, and

n - 2 = 8m

solves to

n = 8m + 2

❌ Check the second sign.

n \equiv 2 \pmod 8

means

8 \mid n - 2

, so

n - 2 = 8m

and

n = 8m + 2

❌ Expand it.

2(2k + 1) = 4k + 2

and

2(4m + 1) + 1 = 8m + 3

, so this is a different equation; the left side

4k + 3

is the odd one.

❌ Expand it.

2(2k + 3) = 4k + 6

and

2(4m + 2) = 8m + 4

, so this is not the equation; and with both sides even there would be no contradiction.

❌ Expand the right side.

2(4m + 1) + 1 = 8m + 3

, not

8m + 2

; the right side

8m + 2 = 2(4m + 1)

is even.

Show solution

We use a proof by contradiction. Let $n$ be an integer, and assume $n \equiv 3 \pmod 4$ and $n \equiv 2 \pmod 8$ . By the definition of congruence, $4 \mid n - 3$ and $8 \mid n - 2$ , so there are integers $k$ and $m$ with

n - 3 = 4k \qquad\text{and}\qquad n - 2 = 8m.

Solving each for $n$ and setting the expressions equal:

4k + 3 = 8m + 2.

Factor $2$ out of each side:

2(2k + 1) + 1 = 2(4m + 1).

Since $2k + 1$ and $4m + 1$ are integers, the left side is odd and the right side is even. No integer is both, so this is a contradiction. Hence if $n \equiv 3 \pmod 4$ , then $n \not\equiv 2 \pmod 8$ . $\blacksquare$

Problem 4 · Which Argument Is a Proof?

Given: There do not exist integers $m$ and $z$ with $z^2 = 4m + 2$ . Which argument proves this?

✅ Correct! It assumes the object exists, uses "

z^2

even

\Rightarrow

z

even" exactly as Stage 2 of the video did, and reaches even

=

odd.

❌ Examples are evidence, not proof. Four values of

m

say nothing about the infinitely many others.

❌ Only half the integers are ruled out. The argument assumed

z

is odd, so an even

z

is never addressed. The negation to assume is simply that some

z

exists.

❌ That assumes the conclusion. A proof by contradiction assumes that such

z

does exist; the "contradiction" here is just a restatement of the assumption.

Show solution

We use a proof by contradiction. Assume there are integers $m$ and $z$ with $z^2 = 4m + 2$ .

Then $z^2 = 2(2m + 1)$ , and $2m + 1$ is an integer, so $z^2$ is even. By the theorem from Unit 7, $z$ is even, so $z = 2k$ for some integer $k$ . Substituting,

4k^2 = 4m + 2 \quad\Longrightarrow\quad 2k^2 = 2m + 1.

The left side is even and the right side is odd. No integer is both, so this is a contradiction, and no integers $m$ and $z$ satisfy $z^2 = 4m + 2$ . $\blacksquare$

This is the same structure as the video's second proof: there, $z^2 = x^2 + y^2 = 4(m^2 + m + n^2 + n) + 2$ had exactly the form $4q + 2$ .

Solved: 0 / 4