Discrete Math Quiz: Primes And Factorization

12 questions · exam conditions

0:00

Primes And FactorizationQuestion 1 of 12

The Fundamental Theorem of Arithmetic guarantees unique prime factorization. However, if we worked in a different number system where $\sqrt{-5}$ was allowed, we could write $6 = 2 \cdot 3 = (1 + \sqrt{-5})(1 - \sqrt{-5})$ . What property do the integers possess that this extended system lacks?

The extended system lacks closure under multiplication, while integers are closed

The extended system lacks unique factorization because it doesn't have enough prime elements

The extended system lacks the property that every non-unit can be written as a product of irreducibles

The extended system lacks unique factorization because some irreducible elements are not prime elements

← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Primes And Factorization

Practice Primes And Factorization in Discrete Math with focused quiz questions that help you check what you know, review explanations, and build confidence with test-style prompts.

What this quiz covers

This quiz focuses on Primes And Factorization, giving you a quick way to practice the rules, question types, and explanations that matter most for Discrete Math.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

All questions

Question 1

The extended system lacks closure under multiplication, while integers are closed
The extended system lacks unique factorization because it doesn't have enough prime elements
The extended system lacks the property that every non-unit can be written as a product of irreducibles
The extended system lacks unique factorization because some irreducible elements are not prime elements (correct answer)

Explanation: In the ring

\mathbb{Z}[\sqrt{-5}]

, we have two different factorizations of 6. The elements

1 + \sqrt{-5}

and

1 - \sqrt{-5}

are irreducible (cannot be factored further in this system), but they are not prime elements. A prime element

p

has the property that if

p

divides

ab

, then

p

divides

a

p

divides

b

. In this system, irreducible elements exist but don't satisfy this prime property, leading to non-unique factorization. The integers form a unique factorization domain where irreducible and prime are equivalent concepts. Choice A is wrong because the system is closed under multiplication. Choice B is wrong because irreducibles exist. Choice C is wrong because factorization into irreducibles is still possible.

Question 2

A factorization algorithm tests whether integers of the form $2^{2^n} + 1$ (Fermat numbers) are prime. For $F_4 = 2^{16} + 1 = 65537$ , the algorithm needs to check divisibility by primes up to $\sqrt{F_4}$ . If the algorithm uses a sieve to pre-compute primes, what is the largest prime it needs to include in its sieve?

The largest prime $\leq 256$ , since we need primes up to the next integer above $\sqrt{65537}$
The largest prime $\leq 255$ , since $\sqrt{65537} \approx 255.8$ (correct answer)
The largest prime $\leq 257$ , since trial division requires testing through the ceiling of $\sqrt{65537}$
The largest prime $\leq 181$ , since optimized algorithms only need primes up to $\sqrt[4]{65537}$

Explanation: When testing whether large numbers are prime, you need to check divisibility by all primes up to the square root of that number. This is because if a composite number

n

has a factor greater than

\sqrt{n}

, it must also have a corresponding factor less than

\sqrt{n}

. For

F_4 = 65537

, you first calculate

\sqrt{65537} \approx 255.8

. Since you only need to test primes up to this value, the largest prime your sieve needs is the largest prime

\leq 255

. This gives you the answer: choice B is correct. Let's examine why the other options miss the mark. Choice A suggests including primes up to 256, but since

\sqrt{65537} < 256

, testing divisibility by primes between 255.8 and 256 is unnecessary—no such primes exist anyway since 256 is not prime. Choice C recommends going up to 257, which extends beyond

\sqrt{65537}

and includes unnecessary computation. While 257 happens to be prime, testing it provides no additional information since any factor of 65537 greater than 255.8 would require a corresponding factor less than 255.8. Choice D mentions using

\sqrt[4]{65537} \approx 16

, but this reflects a misunderstanding—no standard primality test uses the fourth root as a bound. Remember this key principle: for primality testing, you never need to check beyond

\sqrt{n}

. Calculate this bound carefully and include all primes up to (but not necessarily beyond) this value in your sieve.

Question 3

The Miller-Rabin primality test uses the fact that for odd prime $p$ and integer $a$ with $\gcd(a,p) = 1$ , if we write $p-1 = 2^s \cdot d$ where $d$ is odd, then either $a^d \equiv 1 \pmod{p}$ or $a^{2^j \cdot d} \equiv -1 \pmod{p}$ for some $0 \leq j \leq s-1$ . For $n = 341$ and base $a = 2$ , what happens when we apply this test?

The test correctly identifies 341 as composite because $2^{85} \not\equiv \pm 1 \pmod{341}$
The test fails to detect compositeness because 341 is a strong pseudoprime to base 2
The test correctly identifies 341 as composite because $2^{340} \equiv 1 \pmod{341}$ but violates the Miller-Rabin conditions (correct answer)
The test is inconclusive because 341 satisfies some but not all of the Miller-Rabin conditions for base 2

Explanation: First, note that

341 = 11 \times 31

is composite. We have

340 = 341 - 1 = 2^2 \times 85

, so

s = 2

and

d = 85

. For the Miller-Rabin test with base

a = 2

, we need to check: (1)

2^{85} \equiv 1 \pmod{341}

, or (2)

2^{85} \equiv -1 \pmod{341}

, or (3)

2^{170} \equiv -1 \pmod{341}

. Let's compute:

2^{85} \bmod 341

. Since

341 = 11 \times 31

, by Chinese Remainder Theorem:

2^{85} \equiv 2^{85 \bmod 10} = 2^5 = 32 \equiv 10 \pmod{11}

and

2^{85} \equiv 2^{85 \bmod 30} = 2^{25} \equiv 1 \pmod{31}

(since

2^5 = 32 \equiv 1 \pmod{31}

). Using CRT:

2^{85} \equiv 32 \pmod{341}

. Since

32 \not\equiv \pm 1 \pmod{341}

, we check

2^{170} \equiv 32^2 = 1024 \equiv 1024 - 3 \times 341 = 1 \pmod{341}

. Since

2^{170} \equiv 1 \not\equiv -1 \pmod{341}

, the Miller-Rabin test detects 341 as composite.

Question 4

In modular arithmetic, if $p$ is an odd prime and $a$ is not divisible by $p$ , then $a^{(p-1)/2} \equiv \pm 1 \pmod{p}$ . For the prime $p = 17$ , how many integers $a$ with $1 \leq a \leq 16$ satisfy $a^8 \equiv 1 \pmod{17}$ ?

Exactly 8 values, representing half of the non-zero residues modulo 17 (correct answer)
Exactly 4 values, since these correspond to the quadratic residues modulo 17
Exactly 12 values, since most non-zero elements satisfy this congruence condition
Exactly 16 values, since Fermat's Little Theorem guarantees this for all non-zero residues

Explanation: This is about quadratic residues. By Euler's criterion, for odd prime

p

and

\gcd(a,p) = 1

, we have

a^{(p-1)/2} \equiv 1 \pmod{p}

if and only if

a

is a quadratic residue modulo

p

. For

p = 17

, we have

(p-1)/2 = 8

, so we're asking how many

a

satisfy

a^8 \equiv 1 \pmod{17}

. These are exactly the quadratic residues modulo 17. For any odd prime

p

, there are exactly

(p-1)/2

quadratic residues among

\{1, 2, \ldots, p-1\}

. For

p = 17

, this gives

(17-1)/2 = 8

quadratic residues. We can verify: the quadratic residues mod 17 are

\{1^2, 2^2, \ldots, 8^2\} \bmod 17 = \{1, 4, 9, 16, 8, 2, 15, 13\}

. Choice B confuses this with a different count. Choice C and D give incorrect counts for quadratic residues.

Question 5

Consider the polynomial $f(x) = x^4 + x^3 + x^2 + x + 1$ . This polynomial has a special relationship to factorization over the integers. What is the key property that makes this polynomial important in number theory?

It factors completely into linear terms over any field of prime characteristic
It is irreducible over the rationals and its roots generate the 5th cyclotomic field (correct answer)
It has exactly four prime factors when evaluated at any prime number input
It represents the minimal polynomial for primitive elements in finite field extensions

Explanation: When you encounter a polynomial like

f(x) = x^4 + x^3 + x^2 + x + 1

, recognize it as a cyclotomic polynomial. This specific form is the 5th cyclotomic polynomial

\Phi_5(x)

, which arises from factoring

x^5 - 1

. The key insight is that

x^5 - 1 = (x-1)(x^4 + x^3 + x^2 + x + 1)

, so the roots of

f(x)

are the primitive 5th roots of unity—complex numbers

\omega

where

\omega^5 = 1

but

\omega^k \neq 1

for

1 \leq k < 5

. These roots are

e^{2\pi i k/5}

for

k = 1,2,3,4

. This polynomial is irreducible over

\mathbb{Q}

(cannot be factored into lower-degree polynomials with rational coefficients), and its roots generate the 5th cyclotomic field

\mathbb{Q}(\omega)

, making answer B correct. Answer A is wrong because cyclotomic polynomials don't necessarily factor completely into linear terms over every field of prime characteristic—their factorization depends on the specific prime. Answer C is incorrect because there's no guarantee about exactly four prime factors when evaluating at prime inputs. Answer D confuses cyclotomic polynomials with minimal polynomials of primitive elements in finite fields, which are different concepts. Study tip: Memorize that polynomials of the form

1 + x + x^2 + \cdots + x^{p-1}

for prime

p

are cyclotomic polynomials. They're always irreducible over

\mathbb{Q}

and connect directly to roots of unity—a fundamental bridge between algebra and number theory.

Question 6

In the RSA encryption algorithm, if the public key is $(n, e) = (77, 13)$ where $n = pq$ with $p$ and $q$ distinct primes, what is the private key exponent $d$ such that $ed \equiv 1 \pmod{\phi(n)}$ ?

37 (correct answer)
45
53
61

Explanation: First,

77 = 7 \times 11

, so

\phi(77) = (7-1)(11-1) = 6 \times 10 = 60

. We need

13d \equiv 1 \pmod{60}

, which means finding the multiplicative inverse of 13 modulo 60. Using the extended Euclidean algorithm:

60 = 4 \times 13 + 8

13 = 1 \times 8 + 5

8 = 1 \times 5 + 3

5 = 1 \times 3 + 2

3 = 1 \times 2 + 1

. Working backwards:

1 = 3 - 1 \times 2 = 3 - (5 - 3) = 2 \times 3 - 5 = 2(8 - 5) - 5 = 2 \times 8 - 3 \times 5 = 2 \times 8 - 3(13 - 8) = 5 \times 8 - 3 \times 13 = 5(60 - 4 \times 13) - 3 \times 13 = 5 \times 60 - 23 \times 13

. So

-23 \times 13 \equiv 1 \pmod{60}

, which means

d \equiv -23 \equiv 37 \pmod{60}

Question 7

Let $p$ be a prime number greater than 3. If $p^2 + 2$ is also prime, what is the remainder when $p$ is divided by 6?

Either 1 or 5
3
5
1 (correct answer)

Explanation: When you encounter problems about primes and divisibility, think systematically about the possible remainders and use modular arithmetic to eliminate cases. Since

p

is prime and greater than 3, we know

p

is odd and not divisible by 3. When any integer is divided by 6, the possible remainders are 0, 1, 2, 3, 4, or 5. Since

p

is odd, remainders 0, 2, and 4 are impossible. Since

p

isn't divisible by 3, remainder 3 is also impossible. This leaves only remainders 1 and 5 as possibilities. Let's test both cases by examining when

p^2 + 2

could be prime: If

p \equiv 1 \pmod{6}

, then

p^2 \equiv 1 \pmod{6}

, so

p^2 + 2 \equiv 3 \pmod{6}

. This means

p^2 + 2

is divisible by 3. For

p^2 + 2

to be prime, it must equal 3, which happens when

p^2 = 1

, giving

p = 1

. But 1 isn't prime, so this is impossible. If

p \equiv 5 \pmod{6}

, then

p^2 \equiv 25 \equiv 1 \pmod{6}

, so again

p^2 + 2 \equiv 3 \pmod{6}

. The same reasoning applies—

p^2 + 2

would be divisible by 3 and greater than 3, making it composite. Wait—let me recalculate. If

p \equiv 5 \pmod{6}

, then

p^2 \equiv 1 \pmod{6}

, so

p^2 + 2 \equiv 0 \pmod{3}

. Actually, testing

p = 5

p^2 + 2 = 27

, which is

3^3

, not prime. The answer is D) 1, as only

p \equiv 1 \pmod{6}

can potentially work. For modular arithmetic problems, systematically check all possible remainders and use divisibility tests to eliminate impossible cases.

Question 8

Let $S$ be the set of all positive integers $n$ such that $2n + 1$ and $3n + 1$ are both prime. The largest element in $S$ that is less than 20 is:

6
10
14 (correct answer)
18

Explanation: We need both

2n + 1

and

3n + 1

to be prime. Let's check values: For

n = 6

2(6) + 1 = 13

(prime),

3(6) + 1 = 19

(prime) ✓. For

n = 10

2(10) + 1 = 21 = 3 \times 7

(not prime). For

n = 14

2(14) + 1 = 29

(prime),

3(14) + 1 = 43

(prime) ✓. For

n = 18

2(18) + 1 = 37

(prime),

3(18) + 1 = 55 = 5 \times 11

(not prime). Checking other values less than 20:

n = 16

2(16) + 1 = 33 = 3 \times 11

(not prime). So among the given choices, both 6 and 14 work, with 14 being larger.

Question 9

Consider the sequence defined by $a_n = n! + 1$ for $n \geq 1$ . Which statement about the prime factorization of terms in this sequence is correct?

All terms $a_n$ are prime for $n \leq 10$
No term $a_n$ can be divisible by any prime $p \leq n$ (correct answer)
Every term $a_n$ with $n \geq 5$ has at least two distinct prime factors
The greatest common divisor of $a_n$ and $a_{n+1}$ is always 1

Explanation: For any prime

p \leq n

, we have

p | n!

, so

n! \equiv 0 \pmod{p}

. Therefore

a_n = n! + 1 \equiv 1 \pmod{p}

, meaning

p

does not divide

a_n

. Choice A is false (

a_4 = 25 = 5^2

). Choice C is false (

a_4 = 25

has only one distinct prime factor). Choice D is false (we can find counterexamples where

\gcd(a_n, a_{n+1}) > 1

Question 10

Consider integers of the form $6k + r$ where $k \geq 1$ and $0 \leq r \leq 5$ . For which values of $r$ can $6k + r$ potentially be prime for some value of $k$ ?

$r = 1$ and $r = 5$ only, since these avoid all small prime divisors (correct answer)
$r = 1, 3, 5$ only, since these give odd numbers not divisible by 2
$r = 0, 1, 2, 3, 4, 5$ all work, depending on the specific value of $k$
$r = 1, 2, 3, 5$ only, since $r = 0$ and $r = 4$ create composite patterns

Explanation: Let's analyze each case: For

r = 0

6k = 6k

is always divisible by 6, so never prime when

k \geq 1

. For

r = 2

6k + 2 = 2(3k + 1)

is always even and greater than 2, so never prime. For

r = 3

6k + 3 = 3(2k + 1)

is always divisible by 3 and greater than 3, so never prime. For

r = 4

6k + 4 = 2(3k + 2)

is always even and greater than 2, so never prime. For

r = 1

6k + 1

can be prime (e.g.,

k = 1

gives 7,

k = 2

gives 13). For

r = 5

6k + 5

can be prime (e.g.,

k = 1

gives 11,

k = 2

gives 17). Choice B includes

r = 3

which always gives multiples of 3. Choice C incorrectly includes even values. Choice D incorrectly includes

r = 2, 3

Question 11

Consider the sequence of numbers $a_n = 2^n - 1$ for $n \geq 1$ . Which statement about the prime factorization properties of this sequence is correct?

If $n$ is composite, then $a_n$ is always composite, but prime $n$ gives no information about $a_n$ (correct answer)
If $n$ is prime, then $a_n$ is always prime, making this a reliable prime-generating formula
The sequence generates infinitely many primes, but the distribution follows no predictable pattern based on $n$
If $\gcd(m,n) = 1$ , then $\gcd(a_m, a_n) = 1$ , ensuring the sequence values share no common prime factors

Explanation: If

n = ab

where

a, b > 1

, then

2^n - 1 = 2^{ab} - 1 = (2^a)^b - 1

. Using the factorization

x^b - 1 = (x-1)(x^{b-1} + x^{b-2} + \cdots + 1)

, we get

2^n - 1 = (2^a - 1)((2^a)^{b-1} + \cdots + 1)

. Since

a > 1

, we have

2^a - 1 > 1

, and since

b > 1

, the second factor is greater than 1, so

2^n - 1

is composite. However, prime

n

doesn't guarantee

2^n - 1

is prime:

2^{11} - 1 = 2047 = 23 \times 89

. Choice B is wrong because

2^{11} - 1

is composite. Choice C makes unprovable claims about infinite distribution. Choice D is wrong because

\gcd(2^3 - 1, 2^6 - 1) = \gcd(7, 63) = 7 \neq 1

Question 12

Let $N = 2^{12} \cdot 3^8 \cdot 5^4$ . The number of positive divisors of $N^2$ that are perfect squares is:

135 (correct answer)
245
315
420

Explanation: We have

N^2 = 2^{24} \cdot 3^{16} \cdot 5^8

. A divisor of

N^2

has the form

2^a \cdot 3^b \cdot 5^c

where

0 \leq a \leq 24

0 \leq b \leq 16

, and

0 \leq c \leq 8

. For this divisor to be a perfect square, all exponents

a

b

, and

c

must be even. So

a \in \{0, 2, 4, \ldots, 24\}

(13 choices),

b \in \{0, 2, 4, \ldots, 16\}

(9 choices), and

c \in \{0, 2, 4, 6, 8\}

(5 choices). Total:

13 \times 9 \times 5 = 585

. Wait, this exceeds our options. Let me recalculate: we have

13 \times 9 \times 5 = 585

, but checking our choices suggests

9 \times 3 \times 5 = 135