Modular arithmetic — definition, addition, multiplication, congruence: Exercises

This is the practice deck for the parent topic. Work each problem before opening its solution. The problems climb five levels: L1 Recognition (can you spot it?), L2 Application (can you run the rule?), L3 Analysis (can you break it apart?), L4 Synthesis (can you combine ideas?), L5 Mastery (can you invent the route?).

Everything here uses only three ideas from the parent note, so let's re-anchor them in one breath before we start.

Whenever we say "reduce $x (mod n)$ " we mean: divide $x$ by $n$ , throw away the quotient, keep the remainder. That remainder is guaranteed to sit in ${0, \dots, n - 1}$ — this is exactly the Division Algorithm.

Figure — Modular arithmetic — definition, addition, multiplication, congruence

Level 1 — Recognition

Exercise 1.1

Is $47 \equiv 12 (mod 7)$ ? Answer yes/no and say why.

Recall Solution 1.1

What we do: check whether the difference is a multiple of $7$ — that is the raw definition. $47 - 12 = 35 = 5 \times 7.$ What it looks like: on a $7$ -hour clock, starting at $12$ and walking $35$ steps means walking exactly $5$ full laps, landing back on the same mark as $12$ . Since $35$ is a multiple of $7$ , yes, $47 \equiv 12 (mod 7)$ . ✓ (Cross-check with remainders: $47 = 6 \cdot 7 + 5$ and $12 = 1 \cdot 7 + 5$ — both remainder $5$ .)

Exercise 1.2

Which of these are congruent to $3 (mod 5)$ ? $8, 13, 19, - 2, 23.$

Recall Solution 1.2

What we do: reduce each number mod $5$ and keep the ones whose remainder is $3$ .

$8 = 1 \cdot 5 + 3 \Rightarrow 3$ ✓
$13 = 2 \cdot 5 + 3 \Rightarrow 3$ ✓
$19 = 3 \cdot 5 + 4 \Rightarrow 4$ ✗
$- 2$ : add $5$ to climb into range, $- 2 + 5 = 3 \Rightarrow 3$ ✓
$23 = 4 \cdot 5 + 3 \Rightarrow 3$ ✓

Congruent to $3$ : $8, 13, - 2, 23$ . The odd one out is $19$ .

Exercise 1.3

Find the standard-form value of $- 17 (mod 6)$ (an answer in ${0, 1, 2, 3, 4, 5}$ ).

Recall Solution 1.3

Why we can't stop at $- 17$ : standard form must land in ${0, \dots, 5}$ , and $- 17$ is negative — it points behind zero on the clock. We add laps of $6$ until we're inside the range. $- 17 + 6 = - 11 \to - 11 + 6 = - 5 \to - 5 + 6 = 1.$ What it looks like: three forward laps of $6$ ( $+ 18$ total) undo the negative and drop us on mark $1$ . Answer: $- 17 \equiv 1 (mod 6)$ . ✓ (Check: $- 17 - 1 = - 18 = - 3 \times 6$ .)

Level 2 — Application

Exercise 2.1

Compute $(58 + 46) mod 9$ using reduce-then-add.

Recall Solution 2.1

Why reduce first: the addition rule lets us swap each number for its remainder before adding, keeping numbers small.

$58 = 6 \cdot 9 + 4 \Rightarrow 58 \equiv 4$
$46 = 5 \cdot 9 + 1 \Rightarrow 46 \equiv 1$

Add the small ones: $4 + 1 = 5$ , which already lies in ${0, \dots, 8}$ . Answer: $(58 + 46) mod 9 = 5$ . ✓ (Direct check: $58 + 46 = 104 = 11 \cdot 9 + 5$ .)

Exercise 2.2

Compute $(14 \times 11) mod 6$ .

Recall Solution 2.2

Reduce each factor (multiplication rule):

$14 = 2 \cdot 6 + 2 \Rightarrow 14 \equiv 2$
$11 = 1 \cdot 6 + 5 \Rightarrow 11 \equiv 5$

Multiply the small ones: $2 \times 5 = 10$ . Now $10$ is bigger than $5$ , so reduce once more: $10 = 1 \cdot 6 + 4 \Rightarrow 10 \equiv 4.$ Answer: $(14 \times 11) mod 6 = 4$ . ✓ (Direct: $154 = 25 \cdot 6 + 4$ .)

Exercise 2.3

Compute $3^{20} mod 4$ by reducing the base first.

Recall Solution 2.3

Why look at the base: if the base collapses to something tiny, the power rule makes the whole thing trivial. $3 \equiv - 1 (mod 4) (since 3 - (- 1) = 4) .$ By the power rule $3^{20} \equiv (- 1)^{20} (mod 4)$ . An even power of $- 1$ is $+ 1$ : $(- 1)^{20} = 1.$ Answer: $3^{20} \equiv 1 (mod 4)$ . ✓

Level 3 — Analysis

Exercise 3.1

Find the last digit of $7^{2024}$ .

Recall Solution 3.1

Reframe: "last digit" $=$ value $mod 10$ . So we want $7^{2024} mod 10$ . Find the cycle of powers of $7 (mod 10)$ : $7^{1} \equiv 7, 7^{2} \equiv 9, 7^{3} \equiv 3, 7^{4} \equiv 1 (mod 10) .$ Once we hit $1$ , the pattern repeats every $4$ steps: $7, 9, 3, 1, 7, 9, 3, 1, \dots$ What it looks like: a $4$ -step merry-go-round of last digits (see figure below). Land the exponent on the wheel: $2024 = 4 \cdot 506 + 0$ , so $2024$ is a multiple of $4$ , i.e. it lands on the same slot as $7^{4}$ , which is $1$ . Answer: last digit of $7^{2024}$ is $1$ . ✓

Exercise 3.2

Solve $2 x \equiv 3 (mod 5)$ for $x$ in standard form.

Recall Solution 3.2

Why we're allowed to divide here: we may divide by $2$ only if $g cd (2, 5) = 1$ . It is $1$ (GCD and LCM), so a modular inverse of $2$ exists. Find the inverse of $2$ mod $5$ : the number $u$ with $2 u \equiv 1$ . Test $u = 3$ : $2 \cdot 3 = 6 \equiv 1$ . ✓ So $2^{- 1} \equiv 3$ . Multiply both sides by $3$ : $3 \cdot 2 x \equiv 3 \cdot 3 \Rightarrow 1 \cdot x \equiv 9 \equiv 4 (mod 5) .$ Answer: $x \equiv 4 (mod 5)$ . Check: $2 \cdot 4 = 8 = 1 \cdot 5 + 3 \equiv 3$ . ✓

Exercise 3.3

Show that $1 0^{n} \equiv 1 (mod 9)$ for every $n \geq 0$ , and use it to explain the "digit-sum" divisibility rule for $9$ .

Recall Solution 3.3

Base fact: $10 = 1 \cdot 9 + 1$ , so $10 \equiv 1 (mod 9)$ . Power rule: $1 0^{n} \equiv 1^{n} = 1 (mod 9)$ for every $n \geq 0$ . Consequence: write any number by its digits $d_{k} \dots d_{1} d_{0}$ : $N = \sum_{i} d_{i} 1 0^{i} \equiv \sum_{i} d_{i} \cdot 1 = \sum_{i} d_{i} (mod 9) .$ So $N$ and its digit sum are congruent mod $9$ . Therefore $N$ is divisible by $9$ exactly when its digit sum is. Example: $N = 738$ , digit sum $7 + 3 + 8 = 18$ , and $18$ is a multiple of $9$ , so $738$ is too ( $738 = 82 \cdot 9$ ). ✓

Level 4 — Synthesis

Exercise 4.1

Compute $2^{100} mod 7$ .

Recall Solution 4.1

Strategy: find the shortest power of $2$ that hits $1$ mod $7$ , then jump in strides of that length. $2^{1} \equiv 2, 2^{2} \equiv 4, 2^{3} = 8 \equiv 1 (mod 7) .$ So the powers cycle with period $3$ : $2, 4, 1, 2, 4, 1, \dots$ Land the exponent: $100 = 3 \cdot 33 + 1$ , remainder $1$ . So $2^{100}$ sits in the same slot as $2^{1}$ : $2^{100} = (2^{3})^{33} \cdot 2^{1} \equiv 1^{33} \cdot 2 = 2 (mod 7) .$ Answer: $2^{100} \equiv 2 (mod 7)$ . ✓ (This is exactly the mechanism behind Fermats Little Theorem: since $7$ is prime, $2^{6} \equiv 1$ ; here a shorter period $3$ appears, which divides $6$ .)

Exercise 4.2

Find a number $x$ with $x \equiv 2 (mod 3)$ and $x \equiv 3 (mod 5)$ , in the range ${0, \dots, 14}$ .

Recall Solution 4.2

Why range $15$ : the two clocks (period $3$ and period $5$ ) only re-sync after $lcm (3, 5) = 15$ steps, so there is exactly one answer mod $15$ — this is the Chinese Remainder Theorem. Search the class of the second condition: numbers that are $3 (mod 5)$ : $3, 8, 13, \dots$ . Test each against $\equiv 2 (mod 3)$ :

$3 mod 3 = 0$ ✗
$8 mod 3 = 2$ ✓

Answer: $x = 8$ . Check: $8 = 2 \cdot 3 + 2$ (good) and $8 = 1 \cdot 5 + 3$ (good). ✓

Exercise 4.3

Compute $1 2^{34} mod 5$ using two reductions (base, then a power cycle).

Recall Solution 4.3

Reduce the base: $12 = 2 \cdot 5 + 2 \Rightarrow 12 \equiv 2$ , so $1 2^{34} \equiv 2^{34} (mod 5)$ . Find the cycle of $2 (mod 5)$ : $2, 4, 3, 1$ then repeats — period $4$ . Land the exponent: $34 = 4 \cdot 8 + 2$ , remainder $2$ , so $2^{34}$ sits where $2^{2}$ sits, namely $4$ . Answer: $1 2^{34} \equiv 4 (mod 5)$ . ✓

Level 5 — Mastery

Exercise 5.1

Compute $9^{50} mod 11$ , then use it to find $9^{50} mod 11$ 's relationship to $(- 2)^{50}$ .

Recall Solution 5.1

Smart base rewrite: $9 \equiv - 2 (mod 11)$ (since $9 - (- 2) = 11$ ). Negative representatives are legal and often smaller in size. $9^{50} \equiv (- 2)^{50} = 2^{50} (mod 11) (even power kills the sign) .$ Cycle of $2 (mod 11)$ : $2, 4, 8, 16 \equiv 5, 10, 20 \equiv 9, 18 \equiv 7, 14 \equiv 3, 6, 12 \equiv 1.$ That's period $10$ (matching Fermats Little Theorem for prime $11$ : $2^{10} \equiv 1$ ). Land the exponent: $50 = 10 \cdot 5 + 0$ , a multiple of $10$ , so $2^{50} \equiv (2^{10})^{5} \equiv 1^{5} = 1$ . Answer: $9^{50} \equiv 1 (mod 11)$ , and it equals $(- 2)^{50} mod 11$ because $9 \equiv - 2$ . ✓

Exercise 5.2

An RSA-style toy: with modulus $n = 15$ , encryption exponent $e = 3$ , the ciphertext of a message $m$ is $c \equiv m^{3} (mod 15)$ . If the message is $m = 2$ , find $c$ . Then verify decryption with $d = 3$ recovers $m$ (i.e. check $c^{3} \equiv 2 (mod 15)$ ).

Recall Solution 5.2

Encrypt: $c \equiv 2^{3} = 8 (mod 15)$ . So $c = 8$ . Decrypt: compute $c^{3} = 8^{3} = 512 (mod 15)$ . Reduce smartly: $8^{2} = 64 = 4 \cdot 15 + 4 \equiv 4$ , so $8^{3} = 8^{2} \cdot 8 \equiv 4 \cdot 8 = 32 \equiv 2 (mod 15)$ . Result: $c^{3} \equiv 2 = m$ . ✓ Decryption recovers the message — the round-trip works because $3 \cdot 3 = 9$ and $m^{9} \equiv m$ for these keys. Answer: $c = 8$ , and $c^{3} \equiv 2 (mod 15)$ .

Exercise 5.3

Prove: if $a \equiv b (mod n)$ , then $g cd (a, n) = g cd (b, n)$ . Then use it to explain why $6$ has no inverse mod $15$ but $7$ does.

Recall Solution 5.3

Proof. $a \equiv b (mod n)$ means $a = b + k n$ for an integer $k$ . Any common divisor $g$ of $b$ and $n$ divides $b + k n = a$ , so $g$ divides $a$ and $n$ too. The argument runs symmetrically (write $b = a - k n$ ). Hence the set of common divisors of $(a, n)$ equals that of $(b, n)$ , so their greatest members match: $g cd (a, n) = g cd (b, n) . ■$ Application. An inverse of $a$ mod $n$ exists iff $g cd (a, n) = 1$ (Modular Inverses).

$g cd (6, 15) = 3 \neq = 1$ → no inverse: $6$ shares the factor $3$ with $15$ , so $6 x$ can never land on $1$ .
$g cd (7, 15) = 1$ → inverse exists. Find it: $7 \cdot 13 = 91 = 6 \cdot 15 + 1 \equiv 1$ , so $7^{- 1} \equiv 13 (mod 15)$ . ✓

Recall Self-test: state the answers out loud

$47 \equiv 12 (mod 7)$ ? ::: Yes ( $47 - 12 = 35 = 5 \cdot 7$ ). $- 17 (mod 6)$ in standard form ::: $1$ $(58 + 46) mod 9$ ::: $5$ Last digit of $7^{2024}$ ::: $1$ Solve $2 x \equiv 3 (mod 5)$ ::: $x \equiv 4$ $2^{100} mod 7$ ::: $2$ $x \equiv 2 (mod 3), x \equiv 3 (mod 5)$ in ${0..14}$ ::: $8$ $1 2^{34} mod 5$ ::: $4$ $9^{50} mod 11$ ::: $1$ Toy RSA $c$ for $m = 2$ ::: $8$ Does $6$ have an inverse mod $15$ ? ::: No, $g cd (6, 15) = 3$ .