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

Adding, Multiplying and Powering Congruences

IKey Formulas

Statement	Equation behind it	Source
$a \equiv b \pmod n$	$a = b + nk$ for some $k \in \mathbb{Z}$	Definitions of congruence and divides
$(a + c) \equiv (b + d) \pmod n$	$(a + c) - (b + d) = n(k + q)$	Part (1), sums
$ac \equiv bd \pmod n$	$ac - bd = n(bq + dk + nkq)$	Part (2), products
$a^m \equiv b^m \pmod n$ for each $m \in \mathbb{N}$	Part (2) applied to $a \equiv b$ again for each further power	Part (3), powers

Key Insight: With $n \in \mathbb{N}$ , $a \equiv b \pmod n$ and $c \equiv d \pmod n$ (written $a = b + nk$ , $c = d + nq$ ), congruences with the same modulus can be added, multiplied and raised to powers side by side, like equations. Cancelling a common factor is not automatic: $2 \cdot 1 \equiv 2 \cdot 4 \pmod 6$ , yet $4 - 1 = 3$ and $6 \nmid 3$ , so $1 \not\equiv 4 \pmod 6$ .

IIPart (1) · Adding Two Congruences

With $a = b + nk$ and $c = d + nq$ , the sum $a + c$ sits exactly $k + q$ hops of length $n$ from $b + d$ .

n 6 b 3 d 5 k 2 q 1

IIIPart (2) · Multiplying Two Congruences

In $ac = (b + nk)(d + nq)$ , every one of the four pieces except $bd$ carries a factor of $n$ .

n 6 b 3 d 5 k 2 q 1

💡 The rectangle needs positive lengths, but the expansion $(b + nk)(d + nq) = bd + n(bq + dk + nkq)$ holds for all integers, including negative $b$ , $d$ , $k$ and $q$ .

IVPart (3) · Powers, One Multiplication at a Time

Multiplying $a^{m-1} \equiv b^{m-1}$ by $a \equiv b$ with part (2) gives $a^m \equiv b^m$ , one power at a time.

n 6 a 15 power m 1

💡 Each rung is one more application of part (2), so the ladder covers only the powers actually written down; a proof for every $m \in \mathbb{N}$ at once uses mathematical induction, which comes later in the course.

VQuiz Questions

Problem 1 · The Leftover Integers

Given: $23 \equiv 2 \pmod 7$ and $18 \equiv 4 \pmod 7$ , with $23 - 2 = 7k$ and $18 - 4 = 7q$ for integers $k$ and $q$ .

Which integer $j$ gives $(23 + 18) - (2 + 4) = 7j$ ?

Which integer $j$ gives $23 \cdot 18 - 2 \cdot 4 = 7j$ ?

✅ Correct! With

k = 3

and

q = 2

, the sum leaves

k + q = 5

and the product leaves

bq + dk + nkq = 4 + 12 + 42 = 58

; indeed

7 \cdot 5 = 35

and

7 \cdot 58 = 406

❌ Not quite.

41 = 23 + 18

a + c

itself. The difference is

41 - 6 = 35

, and

7 \cdot 41 = 287 \ne 35

❌ Not quite.

6 = kq

multiplies the witnesses

k = 3

and

q = 2

. For a sum they add:

7 \cdot 6 = 42 \ne 35

❌ Not quite.

35

is the difference itself;

j

is what is left after dividing it by

7

❌ Not quite.

kq = 6

is only part of the

n^2kq

piece. The difference is

414 - 8 = 406

, and

7 \cdot 6 = 42

❌ Not quite.

k + q = 5

is the leftover for the sum, not the product:

7 \cdot 5 = 35 \ne 406

❌ Close, but…

bq + dk = 4 + 12 = 16

drops the term

nkq = 7 \cdot 3 \cdot 2 = 42

, which comes from the piece

n^2kq

after factoring out one

n

❌ Not quite. Compute

(23 + 18) - (2 + 4)

and divide by

7

❌ Not quite. Compute

23 \cdot 18 - 2 \cdot 4

and divide by

7

Show solution

The witnesses: $23 - 2 = 21 = 7 \cdot 3$ , so $k = 3$ ; and $18 - 4 = 14 = 7 \cdot 2$ , so $q = 2$ .

Sum. $(23 + 18) - (2 + 4) = 41 - 6 = 35 = 7 \cdot 5$ , and $5 = 3 + 2 = k + q$ , as part (1) predicts.

Product. $23 \cdot 18 - 2 \cdot 4 = 414 - 8 = 406$ . Part (2) predicts the leftover

bq + dk + nkq = 2 \cdot 2 + 4 \cdot 3 + 7 \cdot 3 \cdot 2 = 4 + 12 + 42 = 58,

and indeed $7 \cdot 58 = 406$ .

Problem 2 · Cancelling a Factor

Given: integers $a$ and $b$ with $4a \equiv 4b \pmod 8$ . Which conclusion is valid for every such pair?

✅ Correct! From

4a - 4b = 8j

we get

4(a - b) = 4(2j)

, so

a - b = 2j

and

2 \mid (a - b)

❌ Not quite. This cancels the

4

as if congruences were equations. Take

a = 1

b = 3

4 - 12 = -8 = 8 \cdot (-1)

, so

4 \equiv 12 \pmod 8

, but

1 - 3 = -2

and

8 \nmid -2

❌ Not quite. The same pair

a = 1

b = 3

satisfies

4a \equiv 4b \pmod 8

, but

1 - 3 = -2

and

4 \nmid -2

❌ Not quite. Something does follow: writing

4a - 4b = 8j

and dividing the equation by

4

shows that

a - b

is even.

Show solution

Assume $4a \equiv 4b \pmod 8$ . Then $8 \mid (4a - 4b)$ , so there is an integer $j$ with $4(a - b) = 8j$ . Dividing this equation of integers by $4$ gives $a - b = 2j$ , so $2 \mid (a - b)$ and $a \equiv b \pmod 2$ .

The stronger conclusions fail: $a = 1$ , $b = 3$ gives $4 \cdot 1 - 4 \cdot 3 = -8 = 8 \cdot (-1)$ , so the hypothesis holds, yet $1 - 3 = -2$ is divisible by neither $4$ nor $8$ .

The theorem lets us multiply congruences; cancelling a factor needs its own argument, and here it changes the modulus from $8$ to $2$ .

Problem 3 · Combining Parts (1) and (3)

Given: integers $a$ and $c$ with $a \equiv 4 \pmod 7$ and $c \equiv 3 \pmod 7$ . Which congruence holds for every such pair?

✅ Correct! Part (3) gives

a^2 \equiv 4^2 = 16

, and part (1) adds

c \equiv 3

(a^2 + c) \equiv 16 + 3 = 19 \pmod 7

❌ Not quite.

7 = 4 + 3

forgets to square. With

a = 4

c = 3

a^2 + c = 19

, and

19 - 7 = 12

is not a multiple of

7

❌ Not quite.

11 = 2 \cdot 4 + 3

doubles

4

instead of squaring it. With

a = 4

c = 3

19 - 11 = 8

, not a multiple of

7

❌ Not quite.

48 = 4^2 \cdot 3

multiplies where the expression adds. With

a = 4

c = 3

19 - 48 = -29

, not a multiple of

7

Show solution

From $a \equiv 4 \pmod 7$ , part (3) with $m = 2$ gives $a^2 \equiv 4^2 = 16 \pmod 7$ .

Now add this congruence to $c \equiv 3 \pmod 7$ using part (1): $(a^2 + c) \equiv (16 + 3) = 19 \pmod 7$ .

Check with $a = 11$ and $c = 10$ (since $11 - 4 = 7$ and $10 - 3 = 7$ ): $a^2 + c = 121 + 10 = 131$ , and $131 - 19 = 112 = 7 \cdot 16$ .

Problem 4 · Part (2) with c = a

Given: $a \equiv b \pmod n$ with $a = b + nk$ , $k \in \mathbb{Z}$ . Applying part (2) with $c = a$ and $d = b$ (so $q = k$ ) proves $a^2 \equiv b^2 \pmod n$ . Which integer $j$ satisfies $a^2 - b^2 = nj$ ?

✅ Correct! Substituting

d = b

q = k

into

bq + dk + nkq

gives

bk + bk + nk^2 = 2bk + nk^2

. With

a = 15

b = 3

n = 6

k = 2

6(12 + 24) = 216 = 225 - 9

❌ Not quite. Squaring the witness misses the cross terms. With

a = 15

b = 3

n = 6

k = 2

a^2 - b^2 = 216

, but

6 \cdot 4 = 24

❌ Close, but…

2bk

keeps the two cross terms but drops

nk^2

, which comes from

(nk)^2 = n \cdot nk^2

. With

15, 3, 6, 2

6 \cdot 12 = 72 \ne 216

❌ Close, but…

nk^2

is only the last term; the cross terms

bq + dk

become

bk + bk = 2bk

when

d = b

and

q = k

. With

15, 3, 6, 2

6 \cdot 24 = 144 \ne 216

Show solution

Directly: $a^2 = (b + nk)^2 = b^2 + 2bnk + n^2k^2$ , so

a^2 - b^2 = 2bnk + n^2k^2 = n(2bk + nk^2).

This is the product formula $ac - bd = n(bq + dk + nkq)$ with $c = a$ , $d = b$ , $q = k$ : $bk + bk + nk \cdot k = 2bk + nk^2$ . Since $b$ , $k$ , $n$ are integers, $2bk + nk^2$ is an integer, so $n \mid (a^2 - b^2)$ .

Check: $a = 15$ , $b = 3$ , $n = 6$ , $k = 2$ gives $225 - 9 = 216$ and $6(2 \cdot 3 \cdot 2 + 6 \cdot 4) = 6 \cdot 36 = 216$ .

Solved: 0 / 4