Math for CS: Section 8.4 Review

Question 1

State the formal definition of \(a \equiv b \pmod n\).

Answer 1

\(a \equiv b \pmod n\) if and only if \(n\) divides \((a - b)\), written as: \[n \mid (a - b)\] This is equivalent to saying \(a\) and \(b\) have the same remainder when divided by \(n\).

Question 2

Calculate \(17 \pmod 5\) and \(-17 \pmod 5\).

Answer 2

• \(17 = 3 \times 5 + 2\), so \(17 \equiv \mathbf{2} \pmod 5\).
• \(-17 = -4 \times 5 + 3\), so \(-17 \equiv \mathbf{3} \pmod 5\). (Note: In math, the result is the non-negative remainder \(0 \le r < n\).)

Question 3

True or False: If \(a \equiv b \pmod n\), then \(a^k \equiv b^k \pmod n\) for any positive integer \(k\).

Answer 3

True. Modular arithmetic is compatible with exponentiation. This property is fundamental for algorithms like RSA encryption.

Question 4

Solve for \(x\): \(3x \equiv 1 \pmod 7\).

Answer 4

We are looking for the modular multiplicative inverse of 3 modulo 7. Testing values:

• \(3(1) = 3\).
• \(3(2) = 6\).
• \(3(3) = 9 \equiv 2\).
• \(3(4) = 12 \equiv 5\).
• \(3(5) = 15 \equiv 1 \pmod 7\).
  So, \(x = 5\).

Question 5

What is the set \(\mathbb{Z}_n\)?

Answer 5

\(\mathbb{Z}_n\) is the set of equivalence classes of integers modulo \(n\), usually represented by the remainders: \[\mathbb{Z}_n = \{0, 1, 2, \dots, n-1\}\]

Question 6

Calculate \((45 + 38) \pmod{10}\) using modular properties.

Answer 6

\[(45 \pmod{10} + 38 \pmod{10}) \pmod{10}\]

\[(5 + 8) \pmod{10} = 13 \pmod{10} = \mathbf{3}\]

Question 7

True or False: In \(\mathbb{Z}_n\), if \(ab \equiv 0 \pmod n\), then either \(a \equiv 0\) or \(b \equiv 0\).

Answer 7

False. This only holds if \(n\) is prime. Counterexample in \(\mathbb{Z}_6\): \(2 \times 3 = 6 \equiv 0 \pmod 6\), but neither \(2\) nor \(3\) is \(0 \pmod 6\). These are called zero divisors.

Question 8

Evaluate \(2^{10} \pmod 3\).

Answer 8

Since \(2 \equiv -1 \pmod 3\): \[2^{10} \equiv (-1)^{10} \pmod 3\] \[(-1)^{10} = 1\] So, \(2^{10} \equiv 1 \pmod 3\).

Question 9

How is the “clock” analogy used to explain modular arithmetic?

Answer 10

A clock is \(\mathbb{Z}_{12}\) (or \(\mathbb{Z}_{24}\)). When you add 5 hours to 10:00, you don’t get 15:00 in 12-hour time; you get \(15 \pmod{12} = 3:00\). The number line “wraps around” a circle of size \(n\).

Question 10

Does \(2x \equiv 1 \pmod 4\) have a solution? Why or why not?

Answer 10

No. \(2x\) will always be even. Any number \(y \equiv 1 \pmod 4\) must be odd (of the form \(4k+1\)). An even number can never equal an odd number.

Question 11

If today is Monday (Day 1), what day of the week will it be in 100 days? (Use \(\mathbb{Z}_7\) where Sunday=0).

Answer 11

Calculate \((1 + 100) \pmod 7\).

\(101 = (14 \times 7) + 3\).

\(101 \equiv 3 \pmod 7\).

Day 3 is Wednesday.

Question 12

What is the remainder when \(10^{100}\) is divided by \(9\)?

Answer 12

\(10 \equiv 1 \pmod 9\). Therefore, \(10^{100} \equiv 1^{100} \pmod 9\). The remainder is 1.