Discrete Math Quiz: Writing Proofs

20 questions · exam conditions

0:00

Writing ProofsQuestion 1 of 20

A student claims: "To prove $P \implies (Q \land R)$ , it suffices to prove $(P \implies Q) \land (P \implies R)$ ." Another student argues: "To prove $(P \land Q) \implies R$ , it suffices to prove $(P \implies R) \land (Q \implies R)$ ." Which assessment is correct?

Both claims are logically valid and represent equivalent proof strategies that can be used interchangeably in mathematical arguments.

The first claim is valid but the second is invalid;

(P \land Q) \implies R

requires both

P

and

Q

to be true simultaneously.

The first claim is invalid but the second is valid; proving

P \implies (Q \land R)

requires a different logical structure than suggested.

Both claims are invalid because they misrepresent the logical relationships between conjunctions and implications in formal proof structures.

← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Writing Proofs

Practice Writing Proofs 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 Writing Proofs, 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

Both claims are logically valid and represent equivalent proof strategies that can be used interchangeably in mathematical arguments.
The first claim is valid but the second is invalid; $(P \land Q) \implies R$ requires both $P$ and $Q$ to be true simultaneously. (correct answer)
The first claim is invalid but the second is valid; proving $P \implies (Q \land R)$ requires a different logical structure than suggested.
Both claims are invalid because they misrepresent the logical relationships between conjunctions and implications in formal proof structures.

Explanation: The first claim is valid: P⟹(Q∧R) is equivalent to (P⟹Q)∧(P⟹R). The second claim is invalid: (P∧Q)⟹R is not equivalent to (P⟹R)∧(Q⟹R). For example, let P='x>2', Q='x<5', R='x>0'. Then (P∧Q)⟹R is true, but Q⟹R is false when x=-1. The second requires both P and Q together to imply R, not each separately.

Question 2

Consider proving "The product of any two consecutive integers is even." A student writes: "Let the integers be $n$ and $n+1$ . Either $n$ is even or $n$ is odd. Case 1: If $n$ is even, then $n(n+1)$ is even since it's the product of an even and any integer. Case 2: If $n$ is odd, then $n+1$ is even, so $n(n+1)$ is even." What principle makes this proof structure valid?

The distributive property of multiplication over addition, which ensures that the product structure is preserved across both cases.
The principle of mathematical induction, since the proof establishes the property for all consecutive integer pairs systematically.
The law of excluded middle, which guarantees that every integer is either even or odd, with no other possibilities existing. (correct answer)
The fundamental theorem of arithmetic, which guarantees that the prime factorization determines the parity of integer products uniquely.

Explanation: When analyzing proof structures in discrete math, you need to identify the logical principles that make the reasoning valid. This student's proof uses a fundamental property of logical reasoning. The proof works because it applies the law of excluded middle, which states that for any proposition, either the proposition is true or its negation is true—there's no third option. In this case, every integer must be either even or odd; no integer can be both, and no integer can be neither. This allows the student to exhaustively cover all possibilities by examining just these two cases. The proof structure is valid because: when

n

is even,

n(n+1)

contains an even factor, making the product even. When

n

is odd, then

n+1

must be even (since consecutive integers have opposite parity), again making the product even. Since these cases cover every possible integer, the theorem is proven for all cases. Answer A is incorrect because the distributive property relates to how multiplication distributes over addition (

a(b+c) = ab + ac

), which isn't relevant to this proof's logical structure. Answer B is wrong because mathematical induction involves proving a base case and an inductive step—this proof uses case analysis, not induction. Answer D is incorrect because while the fundamental theorem of arithmetic deals with prime factorization, the proof's validity doesn't depend on unique factorization but on exhaustive case coverage. Remember: when you see proofs that split into "either this or that" cases, look for the law of excluded middle as the underlying principle ensuring completeness.

Question 3

A student attempts to prove "If $a$ and $b$ are odd integers, then $a^2 + b^2$ is even" using: "Let $a = 2m+1$ and $b = 2n+1$ where $m,n$ are integers. Then $a^2 + b^2 = (2m+1)^2 + (2n+1)^2 = 4m^2 + 4m + 1 + 4n^2 + 4n + 1 = 4(m^2 + m + n^2 + n) + 2$ ." What should the student conclude to complete the proof?

Since $m^2 + m + n^2 + n$ is an integer, $a^2 + b^2 = 4k + 2 = 2(2k + 1)$ for integer $k$ , so $a^2 + b^2$ is even.
Since $4(m^2 + m + n^2 + n) + 2 = 2[2(m^2 + m + n^2 + n) + 1]$ and the bracketed expression is an integer, $a^2 + b^2$ is even. (correct answer)
Since $m^2 + m + n^2 + n$ has the same parity as $m + n$ , we can factor out 2 from the entire expression to show evenness.
Since $4(m^2 + m + n^2 + n)$ is divisible by 4 and we add 2, the result $a^2 + b^2$ is divisible by 2, hence even.

Explanation: Choice B correctly completes the proof by factoring out 2: 4(m²+m+n²+n)+2 = 2[2(m²+m+n²+n)+1]. Since the bracketed expression is an integer, a²+b² is 2 times an integer, hence even. Choice A uses unclear notation with k. Choice C makes an irrelevant parity claim. Choice D is less rigorous about the factorization.

Question 4

A student attempts to prove " $\sqrt{6}$ is irrational" by contradiction: "Assume $\sqrt{6} = \frac{a}{b}$ where $\gcd(a,b) = 1$ . Then $6b^2 = a^2$ . Since $6 = 2 \cdot 3$ , both 2 and 3 divide $a^2$ , so both divide $a$ . Let $a = 6c$ , then $6b^2 = 36c^2$ , giving $b^2 = 6c^2$ ." What error occurs in this reasoning?

The conclusion that both 2 and 3 divide $a$ is correct, but writing $a = 6c$ incorrectly assumes these are the only prime factors of $a$ .
The step from $6b^2 = a^2$ to concluding that 2 and 3 both divide $a^2$ is invalid without first establishing that 6 divides $a^2$ .
The reasoning is actually correct up to this point, and the student should continue by showing that 6 divides $b$ , contradicting $\gcd(a,b) = 1$ . (correct answer)
The factorization $6 = 2 \cdot 3$ is insufficient because it doesn't account for the multiplicative structure needed in the irrationality proof framework.

Question 5

Consider this proof attempt for " $\sqrt{3}$ is irrational": "Suppose $\sqrt{3} = \frac{p}{q}$ in lowest terms. Then $3q^2 = p^2$ , so 3 divides $p^2$ . Since 3 is prime, 3 divides $p$ . Let $p = 3r$ , then $3q^2 = 9r^2$ , so $q^2 = 3r^2$ . Therefore 3 divides $q^2$ , and since 3 is prime, 3 divides $q$ . But this contradicts $\gcd(p,q) = 1$ ." What key theorem justifies the step "since 3 is prime, 3 divides $p$ "?

Euclid's lemma: if a prime $p$ divides a product $ab$ , then $p$ divides $a$ or $p$ divides $b$ , applied with $p^2 = p \cdot p$ . (correct answer)
The fundamental theorem of arithmetic: every integer has a unique prime factorization, ensuring that prime divisors are preserved in powers.
The division algorithm: for integers $a$ and $b$ with $b > 0$ , there exist unique integers $q$ and $r$ with $a = bq + r$ .
Bézout's identity: for integers $a$ and $b$ , there exist integers $x$ and $y$ such that $ax + by = \gcd(a,b)$ .

Explanation: This step uses Euclid's lemma. Since 3 divides p² and p² = p·p, Euclid's lemma states that 3 must divide at least one factor p, hence 3 divides p. Choice B (fundamental theorem) is related but not the direct justification. Choice C (division algorithm) is unrelated to this step. Choice D (Bézout's identity) is also unrelated.

Question 6

Consider the statement: "For all integers $n \geq 2$ , if $n$ is prime, then $n^2 + 1$ is composite." Which of the following represents the most significant logical flaw in attempting to prove this statement by contradiction?

Assuming $n$ is prime and $n^2 + 1$ is prime leads to no contradiction since both conditions can be satisfied simultaneously for certain values. (correct answer)
The negation of the statement requires proving that there exists a prime $n$ such that $n^2 + 1$ is also prime, not composite.
The statement cannot be proven by contradiction because it requires direct verification for infinitely many prime numbers.
The assumption phase incorrectly negates " $n$ is prime" rather than negating the entire conditional statement structure.

Explanation: The statement is actually false. For n=2 (which is prime), n²+1=5, which is also prime. This counterexample shows that assuming n is prime and n²+1 is prime leads to no contradiction - both can be true simultaneously. Choice B incorrectly describes proof by contradiction setup. Choice C misunderstands the method. Choice D incorrectly describes how to negate a conditional.

Question 7

Consider proving "For all integers $n \geq 1$ , the sum $1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}$ " by induction. In the inductive step, after assuming the formula holds for $k$ , a student writes: "For $n = k+1$ : $\sum_{i=1}^{k+1} i^2 = \sum_{i=1}^k i^2 + (k+1)^2 = \frac{k(k+1)(2k+1)}{6} + (k+1)^2$ ." What is the most challenging aspect of completing this proof?

Verifying that the base case $n = 1$ satisfies the formula, since substitution into the general expression requires careful arithmetic verification.
Algebraically manipulating $\frac{k(k+1)(2k+1)}{6} + (k+1)^2$ to show it equals $\frac{(k+1)(k+2)(2k+3)}{6}$ without computational errors. (correct answer)
Establishing that the inductive hypothesis can be validly applied, since the summation index shift requires justification of the recursive structure.
Proving that the formula is well-defined for all positive integers, since the denominator 6 might not always divide the numerator expression.

Explanation: The most challenging step is the algebra. You need to manipulate (k(k+1)(2k+1))/6 + (k+1)² to get ((k+1)(k+2)(2k+3))/6, which involves factoring out (k+1), finding a common denominator, and expanding/simplifying. Choice A is straightforward. Choice C misunderstands induction mechanics. Choice D is wrong - the numerator is always divisible by 6.

Question 8

A student claims to prove that " $\sqrt{2}$ is irrational" using the following approach: "Assume $\sqrt{2} = \frac{p}{q}$ where $p$ and $q$ are integers with $\gcd(p,q) = 1$ . Then $2q^2 = p^2$ , so $p^2$ is even, which means $p$ is even. Let $p = 2k$ , then $2q^2 = 4k^2$ , so $q^2 = 2k^2$ ." What is the most critical error in the student's reasoning at this point?

The student failed to establish that $q$ must also be even, which would contradict the assumption that $\gcd(p,q) = 1$ . (correct answer)
The student incorrectly concluded that $p$ is even from $p^2$ being even, since odd squares can also be even in modular arithmetic.
The student made an algebraic error when dividing $2q^2 = 4k^2$ by 2, which should yield $q^2 = k^2$ rather than $q^2 = 2k^2$ .
The student should have used strong induction on the denominator $q$ rather than assuming a specific form for the rational representation.

Explanation: The student's work is actually correct up to this point, but incomplete. The critical next step is to show that q² = 2k² implies q² is even, therefore q is even. This would mean both p and q are even, contradicting gcd(p,q) = 1. Choice B is wrong - if p² is even, then p must be even. Choice C is wrong - the algebra is correct. Choice D suggests an unnecessary approach.

Question 9

Consider the following attempted proof that "the sum of any two rational numbers is rational": "Let $r$ and $s$ be rational numbers. Then $r = \frac{a}{b}$ and $s = \frac{c}{d}$ where $a,b,c,d$ are integers with $b,d \neq 0$ . Thus $r + s = \frac{a}{b} + \frac{c}{d} = \frac{ad + bc}{bd}$ . Since $ad + bc$ and $bd$ are integers with $bd \neq 0$ , we have $r + s$ is rational." What enhancement would make this proof more rigorous?

Verify that $\gcd(ad + bc, bd) = 1$ to ensure the fraction is in lowest terms, as required by the definition of rational numbers.
Explicitly demonstrate that $bd \neq 0$ by showing that the product of two nonzero integers is nonzero, rather than assuming this property.
Include verification that $ad + bc$ and $bd$ are indeed integers by citing closure properties of integer arithmetic operations explicitly.
The proof is already sufficiently rigorous for the given statement and requires no additional justification or enhancement steps. (correct answer)

Explanation: The proof is already rigorous and complete. Rational numbers are defined as quotients of integers (not necessarily in lowest terms), so Choice A is unnecessary. The fact that bd ≠ 0 follows obviously from b,d ≠ 0, making Choice B excessive. Choice C over-explains basic integer arithmetic. The proof correctly demonstrates that the sum has the required form.

Question 10

A student proves "If $n$ is divisible by 6, then $n$ is divisible by both 2 and 3" using: "Assume $n$ is divisible by 6. Then $n = 6k$ for some integer $k$ . Since $6 = 2 \cdot 3$ , we have $n = 2 \cdot 3 \cdot k = 2(3k)$ . Since $3k$ is an integer, $n$ is divisible by 2. Similarly, $n = 3(2k)$ , so $n$ is divisible by 3." Which statement best evaluates this proof?

The proof is logically sound but could be enhanced by explicitly invoking the transitivity property of divisibility relationships.
The proof contains a subtle error because it assumes $6 = 2 \cdot 3$ without justifying that this factorization is unique or well-defined.
The proof is incomplete because it fails to demonstrate that $3k$ and $2k$ are necessarily integers when $k$ is an integer.
The proof is correct and complete, clearly demonstrating both divisibility conditions through valid algebraic manipulation and logical reasoning. (correct answer)

Explanation: The proof is correct and complete. It properly uses the definition of divisibility, correctly factors 6, and shows that n can be written as 2 times an integer and as 3 times an integer. Choice A suggests unnecessary complexity. Choice B incorrectly questions basic arithmetic facts. Choice C questions the obvious fact that products of integers are integers.

Question 11

A student attempts to prove "For all real numbers $x$ , if $x^2 - 5x + 6 = 0$ , then $x = 2$ or $x = 3$ " by writing: "Assume $x^2 - 5x + 6 = 0$ . Factoring gives $(x-2)(x-3) = 0$ . By the zero product property, either $x-2 = 0$ or $x-3 = 0$ , so $x = 2$ or $x = 3$ ." What is the primary issue with this argument structure?

The proof correctly establishes the forward direction but fails to prove the converse, making it an incomplete biconditional argument.
The factorization step assumes the conclusion by presupposing that the quadratic has exactly the roots we're trying to prove exist.
The zero product property applies only to polynomials over integers, not arbitrary real numbers, invalidating the logical step.
The proof structure is actually valid and complete for the given conditional statement, with no significant logical flaws present. (correct answer)

Explanation: The proof is actually correct and complete. The statement is a conditional (if-then), not a biconditional, so proving the forward direction is sufficient. The factorization is valid (can be verified by expansion), and the zero product property applies to real numbers. Choice A incorrectly assumes a biconditional was intended. Choice B misunderstands factorization verification. Choice C incorrectly limits the zero product property.

Question 12

Consider the attempted proof: "Every prime number greater than 2 is odd. Proof: Assume $p$ is a prime number greater than 2. If $p$ were even, then $p = 2k$ for some integer $k > 1$ . This means $p$ has 2 as a factor other than 1 and itself, contradicting the definition of prime. Therefore $p$ must be odd." Which aspect of this argument requires the most careful justification?

The application of the law of excluded middle to conclude $p$ is odd, since the dichotomy between even and odd requires explicit justification.
The conclusion that having 2 as a factor contradicts primality, since this relies on the precise definition of prime numbers and divisibility.
The assumption that $k > 1$ when $p = 2k$ , since this requires proving that $k$ cannot equal 1 for primes greater than 2. (correct answer)
The entire argument structure is sufficiently rigorous and requires no additional justification beyond what is explicitly provided in the proof.

Explanation: When analyzing proof techniques, you need to examine each logical step to identify where assumptions might be hidden or where additional justification is required. The proof uses proof by contradiction effectively: it assumes

p

is even, writes

p = 2k

, then claims this contradicts primality. The critical gap lies in the assumption that

k > 1

. If

p

is a prime greater than 2 and

p = 2k

, why must

k > 1

? This isn't immediately obvious and requires justification. Since

p > 2

and

p = 2k

, we get

k = p/2 > 2/2 = 1

. Without establishing

k > 1

, the contradiction fails—if

k = 1

, then

p = 2

, which contradicts our assumption that

p > 2

. Option A incorrectly suggests the even/odd dichotomy needs justification, but this is a fundamental property of integers that's typically accepted without proof. Option B misidentifies the issue—the connection between having factor 2 and contradicting primality is straightforward once we know

k > 1

. Option D is wrong because the proof does have a logical gap that needs addressing. The answer is C because proving

k > 1

is the missing piece that makes the entire argument work. Without it, the contradiction isn't established. When evaluating proofs, always trace through each logical step carefully. Look for unstated assumptions, especially in algebraic manipulations or when conclusions seem to jump ahead without sufficient justification.

Question 13

A student proves "For any integer $n$ , if $n^2$ is divisible by 4, then $n$ is even" as follows: "If $n$ is odd, then $n = 2k+1$ for some integer $k$ . Then $n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 4k(k+1) + 1$ . Since $k(k+1)$ is an integer, $n^2$ leaves remainder 1 when divided by 4, so $n^2$ is not divisible by 4. This contradicts our assumption." What logical structure does this proof employ?

Direct proof, since the student directly shows that odd integers have squares not divisible by 4, establishing the required conditional statement.
Proof by contrapositive, since the student proves the equivalent statement "if $n$ is odd, then $n^2$ is not divisible by 4." (correct answer)
Proof by contradiction, since the student assumes the negation of the conclusion and derives a contradiction from the given hypothesis.
Proof by cases, since the student implicitly considers the cases where $n$ is odd versus even to establish the complete logical framework.

Explanation: This is proof by contrapositive. The original statement is "if n² is divisible by 4, then n is even." The contrapositive is "if n is odd, then n² is not divisible by 4," which is exactly what the student proved. Choice A misidentifies the method. Choice C is wrong - there's no assumption of negation leading to contradiction. Choice D is wrong - only one case is considered.

Question 14

A student proves "Every tree with $n$ vertices has exactly $n-1$ edges" using induction. The inductive step assumes the statement holds for all trees with $k$ vertices, then considers a tree $T$ with $k+1$ vertices. The student removes an arbitrary vertex $v$ and claims this creates a forest of trees, each with fewer than $k+1$ vertices, so the inductive hypothesis applies. What is the main weakness in this approach?

Removing vertex $v$ may disconnect the tree into multiple components, and the student must account for how the number of edges changes across all components. (correct answer)
The argument fails to ensure that removing $v$ actually produces trees rather than general graphs, since connectivity might be lost in unexpected ways.
The proof doesn't specify whether $v$ is a leaf or internal vertex, and these cases may require different applications of the inductive hypothesis.
The student assumes without justification that each resulting component has exactly $k$ vertices, when the components could have various sizes all less than $k+1$ .

Explanation: The key issue is that when vertex

v

is removed from tree

T

, it takes with it all edges incident to

v

. If

v

has degree

d

, then

d

edges are removed, creating

d

separate tree components. The student must carefully count: if the components have

n_1, n_2, \ldots, n_d

vertices respectively, then by induction they have

(n_1-1) + (n_2-1) + \cdots + (n_d-1)

edges total. Adding back the

d

edges to

v

gives the correct count, but this requires explicit accounting. Choice B is wrong because removing a vertex from a tree always leaves trees. Choice C misses the main issue. Choice D incorrectly focuses on component sizes rather than edge counting.

Question 15

A student attempts to prove " $\sqrt{2}$ is irrational" using the following outline: (1) Assume $\sqrt{2} = \frac{p}{q}$ where $p, q$ are integers with $\gcd(p,q) = 1$ , (2) Show this leads to both $p$ and $q$ being even, (3) Conclude this contradicts $\gcd(p,q) = 1$ . What is the most critical gap in this reasoning structure?

The argument lacks a clear explanation of why showing $p$ and $q$ are both even is sufficient, rather than showing some other common factor.
The proof requires justification for why we can assume $\gcd(p,q) = 1$ without loss of generality when representing any rational number.
The student needs to prove that squaring both sides of $\sqrt{2} = \frac{p}{q}$ is a valid algebraic manipulation that preserves the equality.
The student must explicitly show that if both $p$ and $q$ are even, then $\gcd(p,q) \geq 2$ , which contradicts the assumption that $\gcd(p,q) = 1$ . (correct answer)

Explanation: When analyzing proof by contradiction, you need to identify where logical gaps might undermine the argument's validity. The structure here follows the classic approach for proving

\sqrt{2}

is irrational, but contains a subtle yet critical missing step. The correct answer is D because the student assumes that showing "both

p

and

q

are even" automatically creates a contradiction with "

\gcd(p,q) = 1

" without explicitly connecting these facts. While it may seem obvious that two even numbers share a common factor, rigorous mathematical proof requires stating this connection clearly. The student must demonstrate that if both

p

and

q

are even, then each is divisible by 2, making

\gcd(p,q) \geq 2

, which directly contradicts the assumption that

\gcd(p,q) = 1

. Choice A misses the point—showing both numbers are even is indeed sufficient, and the reasoning structure correctly targets this property. Choice B is incorrect because assuming

\gcd(p,q) = 1

is standard and valid; any rational number can be expressed in lowest terms. Choice C represents unnecessary concern; squaring both sides of an equation is a fundamental algebraic operation that doesn't require special justification in this context. The gap isn't about the overall proof strategy or algebraic manipulations—it's about making the logical connection explicit. In mathematical proofs, each step must be clearly justified, even when the reasoning seems obvious. Study tip: In proof analysis questions, look for missing logical bridges between statements, especially when conclusions seem to "jump" from one idea to another without clear justification.

Question 16

Consider the following attempted proof of "If $f: A \to B$ is surjective and $g: B \to C$ is surjective, then $g \circ f: A \to C$ is surjective": "Since $f$ is surjective, for any $c \in C$ , there exists $a \in A$ such that $f(a) \in B$ . Since $g$ is surjective, $g(f(a)) = c$ for some choice of $a$ . Therefore $g \circ f$ is surjective." What makes this argument insufficient?

The proof incorrectly assumes that the same element $a \in A$ that works for surjectivity of $f$ will also work for the composition $g \circ f$ .
The argument fails to properly connect the surjectivity of $g$ to the existence of a specific $a$ such that $(g \circ f)(a) = c$ for arbitrary $c \in C$ . (correct answer)
The proof does not establish that $f(a) \in B$ is the correct intermediate element needed for $g$ to map to the desired $c \in C$ .
The logical structure reverses the order of quantifiers, starting with the conclusion rather than an arbitrary element $c \in C$ as required for surjectivity.

Explanation: The proof has the right intuition but fails to construct the proper logical chain. To prove

g \circ f

is surjective, we need: for any

c \in C

, there exists

a \in A

such that

(g \circ f)(a) = c

. The correct approach: given

c \in C

, use surjectivity of

g

to find

b \in B

with

g(b) = c

, then use surjectivity of

f

to find

a \in A

with

f(a) = b

. The student's proof doesn't properly establish this connection—it vaguely asserts that these elements exist without showing how to construct them. Choice A misidentifies the error. Choice C is too narrow. Choice D incorrectly describes the quantifier issue.

Question 17

In proving set equality $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ , a student writes: "Let $x \in A \cap (B \cup C)$ . Then $x \in A$ and $x \in B \cup C$ . Since $x \in B \cup C$ , we have $x \in B$ and $x \in C$ . Therefore $x \in A \cap B$ and $x \in A \cap C$ , so $x \in (A \cap B) \cup (A \cap C)$ ." What is the fundamental error in this reasoning?

The student assumes without justification that $x \in A \cap B$ and $x \in A \cap C$ simultaneously, rather than using the disjunctive property of unions.
The proof only shows one direction of the set equality and fails to prove that $(A \cap B) \cup (A \cap C) \subseteq A \cap (B \cup C)$ .
The student incorrectly interprets $x \in B \cup C$ as meaning $x$ is in both $B$ and $C$ , when it means $x$ is in at least one of them. (correct answer)
The logical structure fails to properly distribute the intersection operation over the union, requiring a more careful case-by-case analysis of membership.

Explanation: When proving set equality using element membership, you need to be extremely careful about the logical meaning of set operations. The fundamental issue here lies in how unions are interpreted. The student's error occurs in the third sentence: "Since

x \in B \cup C

, we have

x \in B

and

x \in C

." This is logically incorrect. When

x \in B \cup C

, it means

x

belongs to at least one of the sets

B

C

(or both). The union symbol

\cup

represents "or" in logic, not "and." So

x \in B \cup C

means

x \in B

x \in C

(or both), not

x \in B

AND

x \in C

. This misinterpretation makes the rest of the proof invalid because you cannot conclude that

x

is simultaneously in both

A \cap B

and

A \cap C

. Looking at the wrong answers: (A) incorrectly identifies the error as being about simultaneous membership rather than the misinterpretation of union. (B) points to a completeness issue, but the fundamental logical error occurs much earlier in the proof. (D) suggests the error is about distribution mechanics, but the real problem is basic misunderstanding of union notation. The correct answer is (C) because it precisely identifies the logical error: confusing "or" (union) with "and" (intersection). Study tip: Remember that

\cup

means "or" and

\cap

means "and." When you see

x \in B \cup C

, think "

x

is in

B

C

(possibly both)" — never assume it's in both sets.

Question 18

To prove "For all positive integers $n \geq 2$ , the number $2^n + 1$ has at least one prime factor greater than $n$ ," which proof strategy addresses the most significant challenge in this statement?

Use strong induction with careful attention to how the prime factorization of $2^{n+1} + 1$ relates to the factorization of $2^n + 1$ .
Apply proof by contradiction: assume $2^n + 1$ has only prime factors $\leq n$ , then show this leads to a bound contradiction on the size of $2^n + 1$ . (correct answer)
Use direct proof by systematically factoring $2^n + 1$ for small values of $n$ and establishing a pattern for the largest prime factor.
Employ the Chinese Remainder Theorem to analyze the residues of $2^n + 1$ modulo small primes and derive constraints on possible factorizations.

Explanation: This statement requires showing that

2^n + 1

cannot be completely factored using only primes

\leq n

. Proof by contradiction is most effective: assume all prime factors are

\leq n

, then the product of all primes

\leq n

gives an upper bound, but

2^n + 1

grows exponentially and eventually exceeds this bound. Choice A fails because

2^{n+1} + 1

and

2^n + 1

don't have a simple inductive relationship. Choice C only works for small

n

and doesn't establish the general pattern. Choice D is unnecessarily complex and doesn't directly address the size constraint that makes this statement true.

Question 19

A student claims: "For any integers $a$ and $b$ , if $a^2 + b^2$ is even, then both $a$ and $b$ must be even." To disprove this claim, which approach provides the most efficient counterargument?

Show that when $a$ and $b$ are both odd, $a^2 + b^2$ is even, providing a direct counterexample to the claimed implication. (correct answer)
Prove that $a^2 + b^2$ is even if and only if $a$ and $b$ have the same parity, then note this contradicts the claim.
Use proof by contradiction assuming the claim is false and derive that $a^2 + b^2$ must be odd when both are even.
Demonstrate through exhaustive case analysis that exactly three of the four parity combinations make $a^2 + b^2$ even.

Explanation: To disprove a universal claim, a single counterexample suffices. The claim states that if

a^2 + b^2

is even, then both

a

and

b

are even. A counterexample shows the hypothesis true but conclusion false. When

a = 1, b = 3

(both odd), we get

a^2 + b^2 = 1 + 9 = 10

, which is even, but both numbers are odd, not even. This directly contradicts the claim. Choice B is correct but unnecessarily complex for disproof. Choice C misapplies proof by contradiction. Choice D is overly elaborate when one counterexample suffices.

Question 20

In proving that "the sum of any three consecutive integers is divisible by 3," a student writes: "Let the integers be $n-1$ , $n$ , and $n+1$ . Their sum is $3n$ , which is clearly divisible by 3." What is the primary issue with this proof?

The proof assumes $n$ is the middle integer without justifying why this representation covers all possible consecutive integer triples. (correct answer)
The proof fails to consider negative integers, which might behave differently under the divisibility rule for 3.
The student should have used mathematical induction rather than direct proof for this type of number theory statement.
The calculation is incorrect because $(n-1) + n + (n+1) = 3n + 2$ , not $3n$ , invalidating the entire argument.

Explanation: The student's arithmetic is correct:

(n-1) + n + (n+1) = 3n

, which is indeed divisible by 3. However, the proof structure has a subtle flaw. While representing three consecutive integers as

n-1, n, n+1

is valid and does cover all cases (since

n

can be any integer), a rigorous proof should briefly justify this representation. The student jumps directly to the calculation without explaining why this parameterization is complete. Choice B is wrong because divisibility by 3 works the same for negative integers. Choice C is incorrect because direct proof is perfectly appropriate here. Choice D contains an arithmetic error.