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

Cases Modulo n: Every Integer Is Congruent to Its Remainder

IKey Formulas

Statement	Name	Role
$a = nq + r$ with $0 \le r < n$ , for unique integers $q$ and $r$	Division Algorithm	Gives every integer $a$ a remainder $r$ on division by $n \in \mathbb{N}$
If $a = nq + r$ and $0 \le r < n$ , then $a \equiv r \pmod{n}$	Theorem	An integer is congruent to its own remainder, since $a - r = nq$
Each $a \in \mathbb{Z}$ is congruent modulo $n$ to precisely one of $0, 1, \dots, n - 1$	Corollary	Splits a proof about every integer into $n$ cases
If $a \not\equiv 0 \pmod{5}$ , then $a^2 \equiv 1$ or $a^2 \equiv 4 \pmod{5}$	Proposition	Four cases, each settled by the power and transitive properties

Key Insight: An integer is congruent to many integers ( $9 \equiv 2 \equiv 16 \equiv -5 \pmod{7}$ ), but to exactly one of $0, 1, \dots, n - 1$ , so the cases $a \equiv 0$ , $a \equiv 1$ , …, $a \equiv n - 1$ cover every integer with no overlap.

IIRow q, Column r: The Remainder Decides the Congruence

The Division Algorithm puts $a$ in row $q$ and column $r$ , and every entry of column $r$ is congruent to $r$ .

n 7 a −12

IIIFour Cases Settle the Squares Modulo 5

When $5 \nmid a$ , the corollary leaves four cases, and each one sends $a^2$ to $1$ or $4$ modulo $5$ .

a 8

IVWhich Remainders Can a Square Have?

Modulo any $n$ , the $n$ cases $a \equiv 0, 1, \dots, n - 1$ decide every remainder a square can have.

n 8 case a ≡ 3

VQuiz Questions

Problem 1 · The Remainder of a Negative Integer

Given: $a = -23$ and $n = 6$ . Which Division Algorithm form gives the remainder $r$ , the one integer with $0 \le r < 6$ and $-23 \equiv r \pmod{6}$ ?

✅ Correct!

6(-4) + 1 = -24 + 1 = -23

and

0 \le 1 < 6

, so

r = 1

; indeed

-23 - 1 = -24 = 6(-4)

, so

-23 \equiv 1 \pmod{6}

❌ Not quite. This divides

23

, not

-23

. Check the congruence:

-23 - 5 = -28

, which is not a multiple of

6

, so

-23 \not\equiv 5 \pmod{6}

❌ Not quite. The equation is true, and

-23 \equiv -5 \pmod{6}

holds, but

-5

is not a remainder: the Division Algorithm requires

0 \le r < 6

. Lower the quotient by one to make the remainder non-negative.

❌ Not quite. The equation is true, but

7

is not less than

6

, so this is not the Division Algorithm form. Raise the quotient by one:

-23 = 6(-4) + 1

Show solution

We need integers $q$ and $r$ with $-23 = 6q + r$ and $0 \le r < 6$ . The largest multiple of $6$ that is at most $-23$ is $-24 = 6(-4)$ , so $q = -4$ and $r = -23 - (-24) = 1$ :

-23 = 6(-4) + 1, \qquad 0 \le 1 < 6.

By the theorem, $-23 \equiv 1 \pmod{6}$ : indeed $-23 - 1 = -24 = 6(-4)$ . For a negative integer the quotient is negative and the remainder stays in $0, 1, \dots, 5$ . The forms with $r = -5$ and $r = 7$ are true equations, but neither remainder satisfies $0 \le r < 6$ .

Problem 2 · Congruent to Exactly One — of What?

Given: $30 = 7 \cdot 4 + 2$ . Which statement about $30$ modulo $7$ is true?

✅ Correct!

30 - 9 = 21 = 7 \cdot 3

and

30 - (-5) = 35 = 7 \cdot 5

, so

30

is congruent to infinitely many integers; the corollary only says exactly one of them lies in

0, 1, \dots, 6

, and that one is the remainder

2

❌ Not quite.

30

is congruent to many integers modulo

7

: for example

30 - 9 = 21 = 7 \cdot 3

, so

30 \equiv 9 \pmod{7}

. Uniqueness holds only among

0, 1, \dots, 6

❌ Not quite. Both congruences are true, but there is no contradiction: the corollary is about the numbers

0, 1, \dots, 6

, and

9

is not one of them.

❌ Not quite. The congruence picks out the remainder, not the quotient:

30 - 4 = 26

is not a multiple of

7

, so

30 \not\equiv 4 \pmod{7}

Show solution

From $30 = 7 \cdot 4 + 2$ with $0 \le 2 < 7$ , the theorem gives $30 \equiv 2 \pmod{7}$ .

The integer $30$ is also congruent to $9$ , since $30 - 9 = 21 = 7 \cdot 3$ , and to $-5$ , since $30 - (-5) = 35 = 7 \cdot 5$ . So statement (a) is false, and statement (b) misreads the corollary.

The corollary says that exactly one of $0, 1, \dots, 6$ is congruent to $30$ : at least one because $30$ is congruent to its remainder $2$ , and at most one by the uniqueness of the Division Algorithm. Among $2$ , $9$ and $-5$ , only $2$ lies in that range, so statement (d) is true. Statement (c) uses the quotient: $30 - 4 = 26$ is not a multiple of $7$ .

Problem 3 · Cubes Modulo 7 by Cases

Given: $a$ is an integer with $7 \nmid a$ . Using one case for each possible value of $r$ with $a \equiv r \pmod{7}$ , and the power property with exponent $3$ , find exactly which of $0, 1, \dots, 6$ the cube $a^3$ can be congruent to modulo $7$ .

✅ Correct! The six cases give

1^3 = 1

2^3 = 8 \equiv 1

3^3 = 27 \equiv 6

4^3 = 64 \equiv 1

5^3 = 125 \equiv 6

and

6^3 = 216 \equiv 6

❌ Not quite. Those are the remainders of the squares modulo

7

(

1^2

3^2 = 9 \equiv 2

2^2 = 4

). Cube instead: for example

a \equiv 3

gives

a^3 \equiv 27 = 7 \cdot 3 + 6

, so

a^3 \equiv 6

❌ Not quite. Different cases can land on the same value. Reduce each cube:

2^3 = 8 = 7 \cdot 1 + 1

, so case

2

also gives

1

❌ Not quite.

a^3 \equiv 0

would need the case

a \equiv 0

, which the hypothesis

7 \nmid a

rules out:

a \equiv 0 \pmod{7}

means

7 \mid a

Show solution

Since $7 \nmid a$ , we have $a \not\equiv 0 \pmod{7}$ , so by the corollary $a$ is congruent to exactly one of $1, 2, 3, 4, 5, 6$ . In each case the power property gives $a^3 \equiv r^3$ , and transitivity lets us replace $r^3$ by its remainder (all congruences modulo $7$ ):

$a \equiv 1$ : $a^3 \equiv 1^3 = 1$ .
$a \equiv 2$ : $a^3 \equiv 8$ , and $8 - 1 = 7$ , so $a^3 \equiv 1$ .
$a \equiv 3$ : $a^3 \equiv 27$ , and $27 - 6 = 21 = 7 \cdot 3$ , so $a^3 \equiv 6$ .
$a \equiv 4$ : $a^3 \equiv 64$ , and $64 - 1 = 63 = 7 \cdot 9$ , so $a^3 \equiv 1$ .
$a \equiv 5$ : $a^3 \equiv 125$ , and $125 - 6 = 119 = 7 \cdot 17$ , so $a^3 \equiv 6$ .
$a \equiv 6$ : $a^3 \equiv 216$ , and $216 - 6 = 210 = 7 \cdot 30$ , so $a^3 \equiv 6$ .

Every case ends at $1$ or $6$ , and both occur (for example $a = 1$ and $a = 3$ ). So $a^3$ can be congruent to exactly $1$ and $6$ among $0, 1, \dots, 6$ .

Problem 4 · Sums of Two Squares Modulo 4

Given: The four cases $x \equiv 0, 1, 2, 3 \pmod{4}$ give $x^2 \equiv 0$ or $x^2 \equiv 1 \pmod{4}$ for every integer $x$ . Which of these integers is not equal to $x^2 + y^2$ for any integers $x$ and $y$ ?

✅ Correct!

2023 = 4 \cdot 505 + 3

, so

2023 \equiv 3 \pmod{4}

, while

x^2 + y^2

is congruent to

0

1

2

modulo

4

❌ Not quite.

2020 = 42^2 + 16^2 = 1764 + 256

. Look for the integer whose remainder modulo

4

no sum of two squares can have.

❌ Not quite.

2025 = 45^2 + 0^2

. Look for the integer whose remainder modulo

4

no sum of two squares can have.

❌ Not quite.

2026 = 45^2 + 1^2 = 2025 + 1

. Look for the integer whose remainder modulo

4

no sum of two squares can have.

Show solution

Squares modulo 4. By the corollary each integer $x$ is congruent to exactly one of $0, 1, 2, 3$ modulo $4$ . The power property gives $x^2 \equiv 0$ , $1$ , $4$ or $9$ , and since $4 \equiv 0$ and $9 \equiv 1 \pmod{4}$ , transitivity gives $x^2 \equiv 0$ or $x^2 \equiv 1 \pmod{4}$ .

Sums. Adding congruences, $x^2 + y^2$ is congruent modulo $4$ to $0 + 0 = 0$ , $0 + 1 = 1$ , $1 + 0 = 1$ or $1 + 1 = 2$ .

The integer 2023. Suppose, for a contradiction, that $2023 = x^2 + y^2$ . Since $2023 = 4 \cdot 505 + 3$ , the theorem gives $2023 \equiv 3 \pmod{4}$ , so $x^2 + y^2 \equiv 3$ . But $x^2 + y^2$ is also congruent to one of $0, 1, 2$ , and by the corollary an integer is congruent to only one of $0, 1, 2, 3$ modulo $4$ . This contradiction shows $2023$ is not a sum of two squares.

The other three are sums of two squares: $2020 = 42^2 + 16^2$ , $2025 = 45^2 + 0^2$ and $2026 = 45^2 + 1^2$ .

Solved: 0 / 4