Self-Assessment Quiz: Modular Arithmetic

Twenty questions to check your understanding. Answer before opening the key. Aim for 16+.

Question 1

The statement $a \equiv b \pmod n$ means, by definition:

A) $a$ and $b$ are both less than $n$ B) $n \mid (a - b)$ C) $a \bmod n = b$ D) $a$ and $b$ are both prime

Question 2

Which is the operator that produces a single number in $\{0, \dots, n-1\}$?

A) $a \equiv b \pmod n$ B) $a \bmod n$ C) $n \mid a$ D) $\gcd(a, n)$

Question 3

The residue $(-7) \bmod 3$, using the non-negative convention of §23.1, is:

A) $-1$ B) $0$ C) $1$ D) $2$

Question 4

Theorem 23.2 lets you transfer which operations from integers to residue classes?

A) addition, subtraction, multiplication B) addition and division only C) all four arithmetic operations including division D) only multiplication

Question 5

From $6 \equiv 0 \pmod 6$ you cannot validly conclude $3 \equiv 0 \pmod 6$ because:

A) $6$ is even B) cancellation requires the cancelled factor ($2$) to be invertible modulo $6$, and it is not C) $0$ has no residue class D) the congruence is false

Question 6

The integer $a$ has an inverse modulo $n$ if and only if:

A) $a < n$ B) $a$ is prime C) $\gcd(a, n) = 1$ D) $n$ is prime

Question 7

Which Chapter 22 result is used to construct the modular inverse when $\gcd(a, n) = 1$?

A) the Fundamental Theorem of Arithmetic B) Bézout's identity (via the extended Euclidean algorithm) C) the sieve of Eratosthenes D) the well-ordering principle

Question 8

The congruence $4x \equiv 3 \pmod 6$ has how many solutions modulo $6$?

A) $0$ B) $1$ C) $2$ D) $6$

Question 9

The congruence $6x \equiv 4 \pmod 8$ has how many solutions modulo $8$? (Recall $g = \gcd(6,8) = 2$ and $2 \mid 4$.)

A) $0$ B) $1$ C) $2$ D) $8$

Question 10

The Chinese Remainder Theorem (Theorem 23.5) guarantees a unique solution modulo $N = \prod n_i$ provided the moduli are:

A) all prime B) all even C) pairwise coprime D) consecutive integers

Question 11

In the CRT construction $x = \sum_i a_i N_i M_i$ with $N_i = N / n_i$, the number $M_i$ is:

A) the residue $a_i$ B) the inverse of $N_i$ modulo $n_i$ C) the product of all moduli D) the totient of $n_i$

Question 12

Square-and-multiply computes $b^e \bmod n$ in how many multiplications?

A) $O(e)$ B) $O(e^2)$ C) $O(\log e)$ D) $O(\sqrt{e})$

Question 13

In mod_pow, the most important habit for keeping intermediate numbers small is to:

A) compute the full $b^e$ first, then take % n B) reduce modulo $n$ after every squaring and every multiply C) only reduce at the very end D) avoid the modulus entirely

Question 14

Fermat's little theorem states that if $p$ is prime and $p \nmid a$, then:

A) $a^p \equiv 1 \pmod p$ B) $a^{p-1} \equiv 1 \pmod p$ C) $a^{p} \equiv 0 \pmod p$ D) $a^{p+1} \equiv a \pmod p$

Question 15

Euler's totient $\phi(n)$ counts:

A) the prime factors of $n$ B) the integers in $\{1, \dots, n\}$ coprime to $n$ (the units modulo $n$) C) the divisors of $n$ D) the residues equal to their own inverse

Question 16

For distinct primes $p$ and $q$, the value $\phi(pq)$ — the number RSA's key generation uses — is:

A) $pq$ B) $p + q$ C) $(p-1)(q-1)$ D) $pq - 1$

Question 17

Euler's theorem says that if $\gcd(a, n) = 1$, then:

A) $a^{n} \equiv 1 \pmod n$ B) $a^{\phi(n)} \equiv 1 \pmod n$ C) $a^{n-1} \equiv 1 \pmod n$ D) $a^{\phi(n)} \equiv 0 \pmod n$

Question 18 (True/False, justify)

True or false: If you know $x \bmod 6$ and $x \bmod 4$, the CRT lets you determine $x \bmod 24$. Justify in one sentence.

Question 19 (True/False, justify)

True or false: In RSA, the private exponent $d$ satisfies $ed \equiv 1 \pmod{\phi(n)}$, so $d$ is a modular inverse. Justify in one sentence, naming the operation used to compute $d$.

Question 20 (Short answer)

Explain in one or two sentences why Euler's theorem makes RSA decryption recover the message exactly — i.e., why $m^{ed} \equiv m \pmod n$ when $ed \equiv 1 \pmod{\phi(n)}$.

Answer Key

Topics to review by question