Self-Assessment Quiz: Number Theory Foundations

Twenty questions to check your grip on divisibility, primes, the Division Algorithm, gcd, Bézout, and the Fundamental Theorem of Arithmetic. Answer before opening the key. Aim for 16+.

Question 1

The statement $a \mid b$ means:

A) the fraction $a/b$ is an integer B) there exists an integer $k$ with $b = ak$ (and $a \neq 0$) C) there exists an integer $k$ with $a = bk$ D) the remainder $a \bmod b$ is zero

Question 2

Which of the following is true?

A) $a \mid b$ always implies $b \mid a$ B) $0 \mid 5$ C) $a \mid 0$ for every nonzero integer $a$ D) $1$ is prime

Question 3

By the Division Algorithm, $-17 = 5q + r$ with $0 \le r < 5$ has:

A) $q = -3,\ r = -2$ B) $q = -4,\ r = 3$ C) $q = -3,\ r = 2$ D) $q = 3,\ r = -2$

Question 4

In Python, the value of -17 % 5 is:

A) -2 B) 2 C) 3 D) -3

Question 5

The integer $1$ is excluded from the primes primarily because:

A) it has only one divisor B) it is too small to be useful C) including it would destroy the uniqueness of prime factorization D) it is even

Question 6

In the Sieve of Eratosthenes, when crossing out multiples of a prime $p$, the inner loop starts at $p^2$ rather than $2p$ because:

A) $2p$ is sometimes prime B) every multiple of $p$ below $p^2$ already carries a smaller prime factor and was crossed earlier C) starting at $p^2$ finds more primes D) it avoids crossing out $p$ itself

Question 7

Euclid's proof of the infinitude of primes concludes that the constructed number $N = p_1 p_2 \cdots p_r + 1$:

A) is itself always prime B) is always composite C) has a prime divisor not on the list $p_1, \dots, p_r$ D) equals the next prime after $p_r$

Question 8

The key lemma behind the Euclidean algorithm states that, for $a = bq + r$:

A) $\gcd(a, b) = \gcd(a, r)$ B) $\gcd(a, b) = \gcd(b, r)$ C) $\gcd(a, b) = \gcd(q, r)$ D) $\gcd(a, b) = q \cdot r$

Question 9

The Euclidean algorithm on $\gcd(48, 18)$ returns:

A) $2$ B) $3$ C) $6$ D) $9$

Question 10

Bézout's identity guarantees that, for $a, b$ not both zero, there exist integers $x, y$ with:

A) $ax + by = 1$ always B) $ax + by = \operatorname{lcm}(a, b)$ C) $ax + by = \gcd(a, b)$ D) $ax - by = ab$

Question 11

Bézout coefficients $x, y$ for $\gcd(a, b)$ are:

A) always positive B) unique C) often signed (one may be negative) and not unique D) always equal in magnitude

Question 12

Why does $\gcd(a, n) = 1$ guarantee that $a$ has a modular inverse mod $n$?

A) because $a$ is then prime B) because Bézout gives $ax + ny = 1$, so $ax \equiv 1 \pmod n$ C) because $n$ is then prime D) because $a$ and $n$ are then equal

Question 13

Euclid's Lemma says: if $p$ is prime and $p \mid ab$, then:

A) $p \mid a$ and $p \mid b$ B) $p \mid a$ or $p \mid b$ C) $p \mid (a + b)$ D) $p = ab$

Question 14

For which $m$ does the statement "$m \mid xy \Rightarrow m \mid x$ or $m \mid y$" fail?

A) $m = 2$ B) $m = 3$ C) $m = 4$ D) $m = 7$

Question 15

The uniqueness half of the Fundamental Theorem of Arithmetic relies crucially on:

A) the well-ordering principle alone B) Euclid's Lemma C) the Sieve of Eratosthenes D) Bézout's identity used directly (no lemma)

Question 16

Given $360 = 2^3 \cdot 3^2 \cdot 5$ and $84 = 2^2 \cdot 3 \cdot 7$, $\gcd(360, 84) =$

A) $6$ B) $12$ C) $24$ D) $2520$

Question 17 (True/False, justify)

True or false: The number $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1$ is prime. Justify in one sentence.

Question 18 (True/False, justify)

True or false: The worst case for the Euclidean algorithm (the most division steps relative to input size) occurs on consecutive Fibonacci numbers. Justify in one sentence.

Question 19 (Short answer)

State the three-word recipe this chapter uses for every elementary divisibility proof, and name the one rewriting move you should make the instant you see $a \mid b$.

Question 20 (Short answer)

Using $\gcd(a,b) \cdot \operatorname{lcm}(a,b) = ab$, compute $\operatorname{lcm}(252, 198)$ given that $\gcd(252, 198) = 18$. Show the arithmetic.

Answer Key

Topics to review by question