Mathematical-Reasoning · Unit 10 · Video 7 · Interactive Practice

Rule Out Four Cases, Prove Two: Odd Squares Modulo 6

IKey Formulas

Statement	Role in the proof
Every integer $a$ satisfies $a \equiv r \pmod 6$ for exactly one $r \in \{0, 1, 2, 3, 4, 5\}$	Gives the six cases
$6k + 2j = 2(3k + j)$ for $j = 0, 1, 2$	Remainders $0$ , $2$ , $4$ make $a$ even: impossible when $a$ is odd
$6k + 3 = 3(2k + 1)$	Remainder $3$ makes $3 \mid a$ : impossible when $3 \nmid a$
If $a \equiv b \pmod n$ , then $a^m \equiv b^m \pmod n$ ; if $a \equiv b$ and $b \equiv c \pmod n$ , then $a \equiv c \pmod n$	Power and transitive properties: settle the two surviving cases

Key Insight: If $a$ is odd and $3 \nmid a$ , then $a \equiv 1$ or $a \equiv 5 \pmod 6$ , and in both cases $a^2 \equiv 1 \pmod 6$ , because $1^2 = 1$ and $5^2 = 25 = 6 \cdot 4 + 1$ .

IIRuling Out Cases with the Hypotheses

Each hypothesis removes exactly the remainders it contradicts; together they leave only $1$ and $5$ .

a is odd 3 ∤ a

Case $a \equiv 0 \pmod 6$

a = 6k = 2(3k), \qquad a = 6k = 3(2k), \qquad k \in \mathbb{Z}

Since

3k \in \mathbb{Z}

a

is even; since

2k \in \mathbb{Z}

3 \mid a

. Either hypothesis alone gives a contradiction.

Case $a \equiv 1 \pmod 6$

a = 6k + 1 = 2(3k) + 1 = 3(2k) + 1, \qquad k \in \mathbb{Z}

a

is odd and leaves remainder

1

on division by

3

: neither hypothesis is contradicted. The power property gives

a^2 \equiv 1^2 = 1 \pmod 6

Case $a \equiv 2 \pmod 6$

a = 6k + 2 = 2(3k + 1), \qquad k \in \mathbb{Z}

Since

3k + 1 \in \mathbb{Z}

a

is even, which contradicts that

a

is odd.

Case $a \equiv 3 \pmod 6$

a = 6k + 3 = 3(2k + 1) = 2(3k + 1) + 1, \qquad k \in \mathbb{Z}

Here

a

is odd, so oddness cannot remove this case. Since

2k + 1 \in \mathbb{Z}

3 \mid a

, which contradicts

3 \nmid a

Case $a \equiv 4 \pmod 6$

a - 4 = 6k \;\Longrightarrow\; a = 6k + 4 = 2(3k + 2), \qquad k \in \mathbb{Z}

Since

3k + 2 \in \mathbb{Z}

a

is even, which contradicts that

a

is odd.

Case $a \equiv 5 \pmod 6$

a = 6k + 5 = 2(3k + 2) + 1 = 3(2k + 1) + 2, \qquad k \in \mathbb{Z}

a

is odd and leaves remainder

2

on division by

3

: neither hypothesis is contradicted. The power property gives

a^2 \equiv 5^2 = 25 \pmod 6

, and

25 \equiv 1 \pmod 6

💡 A struck case is not skipped: each one is closed by its own short proof by contradiction, so all six cases are accounted for.

IIISix Columns of Integers

Every integer sits in exactly one remainder column, and that column alone fixes the remainder of $a^2$ .

a −7

IVCase 2: From 25 Down to 1

In Case 2, $a \equiv 5 \pmod 6$ , the power property only reaches $a^2 \equiv 25$ ; the definition of congruence and transitivity carry it down to $1$ .

Example a Step 1

1 · The case

a \equiv 5 \pmod 6, \quad\text{that is,}\quad 6 \mid a - 5

2 · Power property

a^2 \equiv 5^2 = 25 \pmod 6

This congruence is true, but it is not yet the claim.

3 · Definition of congruence

25 - 1 = 24 = 6 \cdot 4, \quad\text{so}\quad 25 \equiv 1 \pmod 6

4 · Transitive property

a^2 \equiv 25 \ \text{and}\ 25 \equiv 1 \pmod 6 \;\Longrightarrow\; a^2 \equiv 1 \pmod 6

Behind it:

a^2 - 1 = (a^2 - 25) + (25 - 1)

is a sum of two multiples of

6

VQuiz Questions

Problem 1 · Closing the Case $a \equiv 4$

Given: $a$ is odd and, in the case being ruled out, $a = 6k + 4$ for some integer $k$ . Which line produces the contradiction?

✅ Correct!

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

and

3k + 2

is an integer, so

a

is even, contradicting that

a

is odd.

❌ Not quite. Expand it:

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

, not

6k + 4

. Half of

6k + 4

3k + 2

❌ True, but no contradiction.

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

is correct and does show

3 \nmid a

— but an odd integer can perfectly well satisfy

3 \nmid a

, so it contradicts nothing. The contradiction must be with oddness.

❌ Not quite.

\tfrac{3}{2}k + 1

need not be an integer (for

k = 1

a = 10

and

4 \nmid 10

), so this line proves nothing. Factor out

2

instead.

Show solution

Suppose, to the contrary, that $a \equiv 4 \pmod 6$ . Then $6 \mid a - 4$ , so $a - 4 = 6k$ for some integer $k$ , and

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

Since $3k + 2$ is an integer, $a$ is even. No integer is both even and odd, which contradicts the assumption that $a$ is odd. Hence an odd integer is never congruent to $4$ modulo $6$ .

Problem 2 · Not Yet the Claim

Given: In Case 2 ( $a \equiv 5 \pmod 6$ ), the power property gives $a^2 \equiv 25 \pmod 6$ . Which statement correctly finishes the case?

✅ Correct! The definition of congruence turns

24 = 6 \cdot 4

into

25 \equiv 1

, and transitivity chains

a^2 \equiv 25 \equiv 1 \pmod 6

❌ Not quite.

a^2 \equiv 25 \pmod 6

does not mean

a^2 = 25

. For

a = 11

a^2 = 121

; what is true is

121 - 25 = 96 = 6 \cdot 16

❌ Not quite.

a^2 \equiv 25 \pmod 6

means

6 \mid a^2 - 25

, not

6 \mid 25

. Case 2 does happen:

a = 5

is odd,

3 \nmid 5

, and

5 \equiv 5 \pmod 6

❌ Not quite. The power property runs from

a

a^2

, not backwards — and in this case

a \equiv 5

, not

1

. What must be reduced is

a^2

, not

a

Show solution

From $a \equiv 5 \pmod 6$ , the power property gives $a^2 \equiv 5^2 = 25 \pmod 6$ . This is true, but the claim is $a^2 \equiv 1$ . Check that

25 - 1 = 24 = 6 \cdot 4,

so $6 \mid 25 - 1$ and $25 \equiv 1 \pmod 6$ by the definition of congruence. Now $a^2 \equiv 25$ and $25 \equiv 1 \pmod 6$ , so the transitive property gives $a^2 \equiv 1 \pmod 6$ .

Problem 3 · Drop the Second Hypothesis

Given: $a$ is an odd integer, with no assumption about divisibility by $3$ . Find which cases modulo $6$ survive, and which remainders $a^2$ can leave on division by $6$ .

Which cases $a \equiv r \pmod 6$ survive?

Which remainders can $a^2$ leave on division by $6$ ?

✅ Correct! Oddness removes only

0

2

4

. Case

3

survives and gives

a^2 \equiv 9 \equiv 3

, so the remainder

1

is no longer guaranteed — exactly the video's example

3^2 = 9 = 6 \cdot 1 + 3

❌ Not quite. Removing case

3

needed the hypothesis

3 \nmid a

, which is gone. And

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

is odd.

❌ Not quite. Case

0

is still removed:

a = 6k = 2(3k)

is even. One contradiction is enough.

❌ Backwards.

0

2

4

are the cases oddness rules out — they make

a

even.

❌ Not quite. That needed

3 \nmid a

. Try

a = 3

a^2 = 9 = 6 \cdot 1 + 3

❌ Not quite. Those are the remainders of

a

, not of

a^2

. Square each case:

5^2 = 25 \equiv 1 \pmod 6

❌ Not quite. The remainder

4

comes from

a \equiv 2

a \equiv 4

, which make

a

even and are ruled out.

Show solution

Cases. If $a \equiv 0, 2, 4 \pmod 6$ , then $a = 6k + 2j = 2(3k + j)$ is even, a contradiction. Nothing removes $1$ , $3$ , $5$ : all three remainders are odd, and without $3 \nmid a$ there is no second hypothesis to contradict.

Squares. By the power property:

a \equiv 1 \Rightarrow a^2 \equiv 1, \qquad a \equiv 3 \Rightarrow a^2 \equiv 9 \equiv 3,

a \equiv 5 \Rightarrow a^2 \equiv 25 \equiv 1 \pmod 6,

using $9 - 3 = 6 = 6 \cdot 1$ and $25 - 1 = 24 = 6 \cdot 4$ . So $a^2$ leaves remainder $1$ or $3$ , and both occur: $1^2 = 1$ and $3^2 = 9 = 6 \cdot 1 + 3$ .

Problem 4 · The Same Pattern Modulo 8

Prove: if $a$ is an odd integer, then $a^2 \equiv 1 \pmod 8$ , by the method of this video: list the cases $a \equiv r \pmod 8$ with $r \in \{0, 1, \dots, 7\}$ , rule out the ones the hypothesis contradicts, and use congruence arithmetic on the rest.

How many cases survive the ruling-out?

In the case $a \equiv 3 \pmod 8$ , what does the argument conclude?

✅ Correct! Oddness removes the four even remainders, leaving

1

3

5

7

, and each square reduces to

1

1

9 = 8 + 1

25 = 8 \cdot 3 + 1

49 = 8 \cdot 6 + 1

❌ Not quite. Modulo

6

, two hypotheses left two cases. Here there is only oddness, and it removes only the even remainders

0

2

4

6

❌ Not quite. Count the odd remainders between

0

and

7

1

3

5

7

❌ Not quite. Eight is the number of cases before ruling out. Each even remainder gives

a = 8k + 2j = 2(4k + j)

, which is even.

❌ Not quite. That is the remainder of

a

. The power property squares it:

a^2 \equiv 3^2 = 9 \pmod 8

❌ Not quite. Squaring is not doubling: the power property gives

a^2 \equiv 3^2 = 9

, not

2 \cdot 3 = 6

❌ Not quite. Reduce

9

modulo

8

9 - 1 = 8

, so

9 \equiv 1

, while

9 - 7 = 2

is not a multiple of

8

Show solution

Ruling out. If $a \equiv 2j \pmod 8$ with $j \in \{0, 1, 2, 3\}$ , then $a = 8k + 2j = 2(4k + j)$ is even, contradicting that $a$ is odd. That removes $0$ , $2$ , $4$ , $6$ and leaves four cases: $1$ , $3$ , $5$ , $7$ .

The four cases. By the power property and then transitivity:

a \equiv 1 \Rightarrow a^2 \equiv 1, \qquad a \equiv 3 \Rightarrow a^2 \equiv 9 \equiv 1 \pmod 8,

a \equiv 5 \Rightarrow a^2 \equiv 25 \equiv 1, \qquad a \equiv 7 \Rightarrow a^2 \equiv 49 \equiv 1 \pmod 8,

because $9 - 1 = 8 \cdot 1$ , $25 - 1 = 8 \cdot 3$ and $49 - 1 = 8 \cdot 6$ . In every case $a^2 \equiv 1 \pmod 8$ .

Solved: 0 / 4