Proof by contrapositive - Discrete Math

A student attempts to prove by contrapositive that "If $f(x) = x^3 + 2x$ , then $f$ is one-to-one." The student writes: "Assume $f$ is not one-to-one. Then there exist $a \neq b$ such that $f(a) = f(b)$ . This means $a^3 + 2a = b^3 + 2b$ , so $a^3 - b^3 = 2b - 2a = 2(b - a)$ ." What should the student do next to complete the proof?
Answer: Factor $a^3 - b^3$ as $(a-b)(a^2 + ab + b^2)$ and show this leads to $a^2 + ab + b^2 = -2$ , which is impossible for real numbers. In a proof by contrapositive, we assume the negation of the conclusion and derive the negation of the hypothesis. The student correctly assumed $f$ is not one-to-one and derived $a^3 - b^3 = 2(b - a)$ . Factoring the left side gives $(a-b)(a^2 + ab + b^2) = -2(a-b)$ . Since $a \neq b$ , we can divide by $(a-b)$ to get $a^2 + ab + b^2 = -2$ . But $a^2 + ab + b^2 = (a + \frac{b}{2})^2 + \frac{3b^2}{4} \geq 0$ for real numbers, so it cannot equal $-2$ . This contradiction shows our assumption was false. Choice B misunderstands the proof structure. Choice C attempts proof by contradiction rather than contrapositive. Choice D is not a valid proof technique for this general statement.
Consider proving "If $\gcd(a,12) = 1$ , then $\gcd(a,8) = 1$ and $\gcd(a,3) = 1$ " by contrapositive. Which assumption leads to the most direct proof path?
Answer: Assume $\gcd(a,8) > 1$ or $\gcd(a,3) > 1$ , then show that $a$ shares a common factor with either 8 or 3, both of which divide 12. When proving an implication by contrapositive, you need to prove the logically equivalent statement: "not Q implies not P." Here, the contrapositive of "If $\gcd(a,12) = 1$ , then $\gcd(a,8) = 1$ and $\gcd(a,3) = 1$ " is "If $\gcd(a,8) \neq 1$ or $\gcd(a,3) \neq 1$ , then $\gcd(a,12) \neq 1$ ." Option C correctly identifies this contrapositive assumption and provides the most direct proof path. When $\gcd(a,8) > 1$ , then $a$ and 8 share a common factor greater than 1. Since $8 = 2^3$ divides $12 = 2^2 \cdot 3$ , any common factor of $a$ and 8 is also a common factor of $a$ and 12, making $\gcd(a,12) > 1$ . Similarly, if $\gcd(a,3) > 1$ , then $a$ and 3 share a common factor, and since 3 divides 12, we get $\gcd(a,12) > 1$ . Option A proves the original statement directly, not by contrapositive. Option B uses the wrong logical structure—it assumes both conditions are false (AND) rather than at least one is false (OR). This misrepresents the negation of " $\gcd(a,8) = 1$ and $\gcd(a,3) = 1$ ." Option D also incorrectly assumes both conditions are false and unnecessarily invokes the Chinese Remainder Theorem with 24 instead of 12. Remember: when negating "P and Q," you get "not P or not Q," not "not P and not Q." This logical principle is crucial for setting up contrapositive proofs correctly.
A student attempts to prove "If $n^2$ is odd, then $n$ is odd" using contrapositive. They write: "Assume $n$ is even. Then $n = 2k$ for some integer $k$ . So $n^2 = 4k^2 = 2(2k^2)$ , which is even." What is the most significant issue with this proof?
Answer: The proof is actually correct and complete; no significant issues exist with the logical structure or mathematical content presented. When evaluating proofs by contrapositive, you need to check three key elements: correct logical structure, valid mathematical reasoning, and complete argumentation. The student's proof is actually mathematically sound and logically complete. They correctly identify that the contrapositive of "If $n^2$ is odd, then $n$ is odd" is "If $n$ is even, then $n^2$ is even." They assume $n$ is even, express it as $n = 2k$ , and correctly calculate $n^2 = (2k)^2 = 4k^2 = 2(2k^2)$ , showing $n^2$ is even. This proves the contrapositive, which establishes the original statement. Option A incorrectly claims an algebraic error. The calculation $4k^2 = 2(2k^2)$ is perfectly valid—factoring out 2 from $4k^2$ gives $2(2k^2)$ , not $2(k^2)$ . Both expressions show $n^2$ is even, which is what matters. Option B suggests the proof lacks clarity by not stating the contrapositive explicitly. While stating it would improve readability, this omission doesn't constitute a "significant issue" since the logical flow is still correct and followable. Option D fundamentally misunderstands contrapositive logic. The contrapositive of "If P, then Q" is "If not Q, then not P." Here, that means "If $n$ is even, then $n^2$ is even"—exactly what the student proved. Remember: when checking contrapositive proofs, verify they assume the negation of the conclusion and prove the negation of the hypothesis. Don't be distracted by minor presentation issues if the core logic is solid.
A student claims: "To prove 'If $p$ is prime and $p > 2$ , then $p$ is odd' by contrapositive, I assume $p$ is even and show $p$ is not prime or $p \leq 2$ ." What is the most significant error in this reasoning?
Answer: The reasoning is actually correct and complete; assuming $p$ is even and deriving that $p$ is either composite or equals 2 properly proves the contrapositive. The student's reasoning is actually correct. The original statement "If $p$ is prime and $p > 2$ , then $p$ is odd" has contrapositive "If $p$ is even, then $p$ is not prime or $p \leq 2$ ." The student correctly identifies this. When $p$ is even, either $p = 2$ (so $p \leq 2$ ) or $p > 2$ (making $p$ composite since it's even). Choice A suggests an incomplete approach. Choice B incorrectly dismisses contrapositive proof. Choice C misunderstands the contrapositive formation for compound hypotheses.
A theorem states: "If a graph $G$ is connected and has exactly two vertices of odd degree, then $G$ has an Eulerian path but not an Eulerian cycle." What would be the most challenging part of proving this by contrapositive?
Answer: Correctly negating the compound conclusion to get " $G$ has no Eulerian path or $G$ has an Eulerian cycle" and handling both cases systematically. The contrapositive requires negating " $G$ has an Eulerian path but not an Eulerian cycle," which becomes " $G$ has no Eulerian path OR $G$ has an Eulerian cycle." This creates two separate cases to consider, making the proof structure more complex. Choice B is incorrect - disconnected graphs can still have Eulerian paths in components. Choice C describes just one part of the proof. Choice D states a true fact but it's not directly relevant to this contrapositive proof.
Consider the statement "If $f(x) = x^2 + bx + c$ has no real roots, then $b^2 - 4c < 0$ ." To prove this by contrapositive, which approach correctly handles the inequality direction?
Answer: Assume $b^2 - 4c \geq 0$ , then the discriminant is non-negative, so $f(x)$ has at least one real root by the quadratic formula. When you encounter proof by contrapositive problems, remember that you're proving "not Q implies not P" instead of the original "P implies Q." This requires careful attention to logical negations, especially with inequalities. The original statement is: "If $f(x) = x^2 + bx + c$ has no real roots, then $b^2 - 4c < 0$ ." To prove by contrapositive, you assume the negation of the conclusion and prove the negation of the hypothesis. The negation of " $b^2 - 4c < 0$ " is " $b^2 - 4c \geq 0$ ," and the negation of "has no real roots" is "has at least one real root." Choice C correctly identifies this approach. When $b^2 - 4c \geq 0$ , the discriminant is non-negative, which means the quadratic formula $x = \frac{-b \pm \sqrt{b^2 - 4c}}{2}$ yields real solutions. Specifically, if the discriminant equals zero, there's one repeated real root; if positive, there are two distinct real roots. Either way, the quadratic has at least one real root. Choice A incorrectly assumes $b^2 - 4c \leq 0$ , which is not the proper negation of the strict inequality. Choice B uses $b^2 - 4c > 0$ , missing the boundary case where the discriminant equals zero. Choice D assumes $b^2 - 4c \neq 0$ , which excludes the critical case where the discriminant is zero and there's exactly one real root. Study tip: When negating inequalities in contrapositive proofs, remember that "< becomes ≥" and "> becomes ≤." The boundary cases often matter in mathematical arguments.
To prove "If $x$ and $y$ are rational numbers and $x + y\sqrt{2}$ is rational, then $y = 0$ " by contrapositive, a student assumes $y \neq 0$ and writes $y = \frac{p}{q}$ where $p, q$ are integers with $q \neq 0$ and $p \neq 0$ . If $x + y\sqrt{2}$ were rational, what contradiction would arise?
Answer: We could solve for $\sqrt{2} = \frac{r - x}{y}$ where $r$ is rational, making $\sqrt{2}$ rational, which contradicts the irrationality of $\sqrt{2}$ . When you encounter a proof by contrapositive, you're proving "if P then Q" by instead proving "if not Q then not P." Here, we assume $y \neq 0$ (not Q) to show that $x + y\sqrt{2}$ cannot be rational (not P). The key insight is algebraic manipulation. If we assume $x + y\sqrt{2}$ is rational (call it $r$ ), then we can rearrange: $x + y\sqrt{2} = r$ , so $y\sqrt{2} = r - x$ . Since $x$ and $r$ are both rational, their difference $r - x$ is rational. Now, since $y \neq 0$ and $y$ is rational, we can divide both sides by $y$ : $\sqrt{2} = \frac{r - x}{y}$ . This expresses $\sqrt{2}$ as a quotient of two rational numbers, making it rational—but we know $\sqrt{2}$ is irrational. This contradiction proves our assumption was wrong. Answer choice A incorrectly focuses on $y\sqrt{2}$ being simultaneously rational and irrational, but $y\sqrt{2}$ is simply irrational when $y \neq 0$ . Choice B correctly notes that $x + y\sqrt{2}$ should be irrational, but this doesn't create the contradiction we need—we assumed it was rational to derive our contradiction. Choice C vaguely mentions inability to simplify without showing the specific algebraic contradiction. Answer D correctly identifies the contradiction: we derive that $\sqrt{2}$ must be rational, contradicting its known irrationality. Study tip: In contrapositive proofs involving irrationals, look for ways to isolate the irrational term and show it must equal something rational—that's usually where your contradiction lies.
A theorem states: "If a graph $G$ is connected and has exactly two vertices of odd degree, then $G$ has an Eulerian path." Which statement would be proven in a contrapositive proof of this theorem?
Answer: If $G$ does not have an Eulerian path, then $G$ is disconnected or $G$ does not have exactly two vertices of odd degree. When you encounter questions about contrapositive proofs, remember that the contrapositive of "If P, then Q" is "If not Q, then not P." These statements are logically equivalent, so proving the contrapositive proves the original theorem. The original theorem states: "If [ $G$ is connected AND has exactly two vertices of odd degree], then [ $G$ has an Eulerian path]." To form the contrapositive, you negate both parts and reverse their order: "If [ $G$ does NOT have an Eulerian path], then [ $G$ is NOT (connected AND has exactly two vertices of odd degree)]." Using De Morgan's law, "NOT (connected AND exactly two odd vertices)" becomes "disconnected OR does not have exactly two odd vertices." This matches option D perfectly. Option A describes a different theorem about Eulerian cycles, not the contrapositive of our given statement. Option B is the converse of the original theorem (switching P and Q), which is not logically equivalent to the original. Option C attempts the contrapositive but gets the direction wrong—it negates the hypothesis instead of the conclusion first, making it an invalid contrapositive. The key insight is that D correctly negates the conclusion ("does not have an Eulerian path") and then negates the entire compound hypothesis using De Morgan's law. Study tip: For contrapositive questions, always follow this formula: "If not Q, then not P." When the hypothesis has multiple parts connected by "and," remember that negating it requires "or" between the negated parts. Practice identifying contrapositives versus converses, as these are commonly confused on discrete math exams.
Which statement best explains why contrapositive proof is sometimes preferred over direct proof for implications of the form "If $P$ , then $Q$ "?
Answer: The contrapositive $\neg Q \rightarrow \neg P$ often provides more concrete or constructive assumptions to work with, especially when $Q$ involves existence statements or complex conditions. When you encounter questions about proof strategies, focus on the practical advantages each method offers rather than their logical equivalence. Contrapositive proof works by proving $\neg Q \rightarrow \neg P$ instead of $P \rightarrow Q$ . The key insight is that negating the conclusion often gives you something concrete to work with. For example, if $Q$ states "there exists an element with property X," then $\neg Q$ means "no element has property X" — a much clearer assumption for building a proof. Similarly, when $Q$ involves complex conditions, $\neg Q$ frequently simplifies to more manageable statements that naturally lead to contradicting $P$ . Choice A is incorrect because contrapositive proof doesn't establish the converse ( $Q \rightarrow P$ ). Both direct and contrapositive proofs are logically equivalent in strength — they prove exactly the same statement. Choice C misunderstands circular reasoning. The conceptual relationship between hypothesis and conclusion doesn't create circularity in either proof method. Circular reasoning occurs when you assume what you're trying to prove, not when concepts are related. Choice D is wrong because contrapositive proofs aren't inherently shorter or more computationally efficient. The number of steps depends on the specific problem, and both methods involve the same logical complexity. Study tip: When deciding between direct and contrapositive proof, examine the conclusion carefully. If it's an existence statement, contains multiple conditions, or seems difficult to construct directly, try working backwards from its negation — you'll often find a clearer path to the contradiction you need.
Consider the statement: "If $n^2$ is even, then $n$ is even." Which of the following correctly represents a proof by contrapositive of this statement?
Answer: Assume $n$ is odd. Then $n = 2k + 1$ for some integer $k$ , so $n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$ , which is odd. Therefore, if $n$ is odd, then $n^2$ is odd. A proof by contrapositive of "If P, then Q" proves "If not Q, then not P." For the statement "If $n^2$ is even, then $n$ is even," the contrapositive is "If $n$ is odd, then $n^2$ is odd." Choice A correctly proves this contrapositive by assuming $n$ is odd and showing $n^2$ must be odd. Choice B incorrectly attempts to work backwards from $n^2$ being odd but makes an invalid inference about square roots. Choice C proves the converse, not the contrapositive. Choice D attempts proof by contradiction, not contrapositive.
A student wants to prove by contrapositive that "If $f: \mathbb{R} \to \mathbb{R}$ is differentiable at $x = a$ , then $f$ is continuous at $x = a$ ." The student begins: "Assume $f$ is not continuous at $x = a$ . Then..." What should follow to complete this proof correctly?
Answer: There exists $\epsilon > 0$ such that for all $\delta > 0$ , there exists $x$ with $|x - a| < \delta$ but $|f(x) - f(a)| \geq \epsilon$ , which prevents the derivative limit from existing. When approaching proof by contrapositive, you need to precisely negate both the hypothesis and conclusion, then show the contrapositive statement is true. The original statement is "differentiable at $a$ implies continuous at $a$ ," so the contrapositive is "not continuous at $a$ implies not differentiable at $a$ ." The correct approach uses the formal definition of continuity. If $f$ is not continuous at $a$ , then there exists some $\epsilon > 0$ such that no matter how small you make $\delta > 0$ , you can always find points $x$ within $\delta$ of $a$ where $|f(x) - f(a)| \geq \epsilon$ . This persistent "jump" of at least $\epsilon$ prevents the difference quotient $\frac{f(x) - f(a)}{x - a}$ from having a limit as $x \to a$ , since the numerator can't get arbitrarily small. Answer C correctly captures this rigorous argument. Answer A is wrong because discontinuity doesn't require unboundedness—functions can be discontinuous while remaining bounded. Answer B incorrectly assumes all discontinuities are jump discontinuities and wrongly claims the difference quotient is "undefined" rather than showing its limit doesn't exist. Answer D makes a vague connection between continuity and differentiability without establishing the crucial logical link—it doesn't explain why the failure of $\lim_{x \to a} f(x) = f(a)$ prevents the derivative limit from existing. Remember: contrapositive proofs require precise logical reasoning using formal definitions. Avoid intuitive but imprecise arguments—stick to the mathematical definitions of continuity and differentiability.
To prove "If $x + y > 10$ , then $x > 3$ or $y > 7$ " by contrapositive, which statement must be proven?
Answer: If $x \leq 3$ and $y \leq 7$ , then $x + y \leq 10$ The contrapositive of "If P, then Q" is "If not Q, then not P." Here, P is " $x + y > 10$ " and Q is " $x > 3$ or $y > 7$ ". The negation of Q is "not( $x > 3$ or $y > 7$ )" which by De Morgan's law becomes " $x \leq 3$ and $y \leq 7$ ". The negation of P is " $x + y \leq 10$ ". Therefore, the contrapositive is "If $x \leq 3$ and $y \leq 7$ , then $x + y \leq 10$ ". Choice B incorrectly negates the disjunction as a disjunction instead of a conjunction. Choice C states the converse. Choice D creates an unrelated statement.
When proving "If $n^4 + n^2 + 1$ is prime, then $n$ is even" by contrapositive, what is the key insight needed to complete the proof?
Answer: Recognizing that $n^4 + n^2 + 1 = (n^2 + n + 1)(n^2 - n + 1)$ when $n$ is odd, providing a non-trivial factorization. When approaching a proof by contrapositive, you need to prove the negation of the conclusion implies the negation of the hypothesis. Here, instead of proving "If $n^4 + n^2 + 1$ is prime, then $n$ is even," you prove "If $n$ is odd, then $n^4 + n^2 + 1$ is composite." The key insight is recognizing that when $n$ is odd, the expression $n^4 + n^2 + 1$ factors as $(n^2 + n + 1)(n^2 - n + 1)$ . You can verify this by expanding: $(n^2 + n + 1)(n^2 - n + 1) = n^4 - n^3 + n^2 + n^3 - n^2 + n + n^2 - n + 1 = n^4 + n^2 + 1$ . When $n$ is odd, both factors are integers greater than 1, proving the expression is composite. Option A discusses modular arithmetic properties but doesn't directly prove compositeness—showing an expression can't equal 2 doesn't prove it's composite for all values. Option C makes an irrelevant comparison; being greater than $n^2$ doesn't imply compositeness. Option D correctly notes the expression is always odd, but this observation alone doesn't complete the proof of compositeness. The correct answer is B because it provides the factorization that directly proves compositeness when $n$ is odd. Study tip: In contrapositive proofs involving primality, look for algebraic factorizations. When you can factor an expression into two non-trivial factors, you've immediately proven it's composite, which is often the goal in these problems.
Consider the statement: "If $n^3 + 5n$ is even, then $n$ is even." Which of the following correctly represents the contrapositive and provides the most appropriate proof strategy?
Answer: If $n$ is odd, then $n^3 + 5n$ is odd. Prove by assuming $n = 2k+1$ and showing $n^3 + 5n = 2m+1$ for some integer $m$ . The contrapositive of "If P, then Q" is "If not Q, then not P." Here, P is " $n^3 + 5n$ is even" and Q is " $n$ is even." So the contrapositive is "If $n$ is not even (odd), then $n^3 + 5n$ is not even (odd)." Choice A correctly states this and gives the right proof approach. Choice B has the wrong conclusion in the contrapositive. Choice C reverses the logic incorrectly. Choice D describes proof by contradiction, not contrapositive.
Which statement about proof by contrapositive is most accurate when comparing it to direct proof and proof by contradiction?
Answer: Contrapositive proof and proof by contradiction both assume negations, but contrapositive derives a specific conclusion while contradiction seeks any logical inconsistency. Choice D correctly identifies the key distinction: both contrapositive and contradiction involve assuming negations, but contrapositive specifically assumes ¬Q to prove ¬P (deriving a targeted conclusion), while contradiction assumes ¬(P→Q) to derive any contradiction. Choice A is wrong because contrapositive and direct proof are logically equivalent but procedurally different. Choice B incorrectly claims they're logically distinct. Choice C incorrectly describes contrapositive as a special case of contradiction.
Consider the statement: "If $n$ is a positive integer and $2^n - 1$ is prime, then $n$ is prime." In a proof by contrapositive, we assume $n$ is composite. If $n = ab$ where $1 < a, b < n$ , which factorization property allows us to conclude that $2^n - 1$ is composite?
Answer: $2^n - 1 = 2^{ab} - 1 = (2^a)^b - 1$ , and since $x^b - 1 = (x-1)(x^{b-1} + x^{b-2} + \cdots + x + 1)$ , we get a non-trivial factorization. When proving statements about prime numbers using contrapositive, you're leveraging powerful algebraic identities to show that composite exponents lead to composite results. The key insight here involves the factorization formula for expressions of the form $x^b - 1$ . When $n = ab$ with both $a$ and $b$ greater than 1, we can write $2^n - 1 = 2^{ab} - 1 = (2^a)^b - 1$ . Now applying the standard factorization $x^b - 1 = (x-1)(x^{b-1} + x^{b-2} + \cdots + x + 1)$ with $x = 2^a$ , we get $2^n - 1 = (2^a - 1)(2^{a(b-1)} + 2^{a(b-2)} + \cdots + 2^a + 1)$ . Since $a > 1$ , both factors are greater than 1, proving $2^n - 1$ is composite. This makes B correct. Option A presents an incorrect algebraic manipulation that doesn't follow from any standard factorization identity. Option C attempts a factorization but the expression $2^a(2^{b-1} - 1) + (2^a - 1)$ doesn't actually factor $2^n - 1$ into a product of two integers. Option D makes the fundamental error of assuming compositeness transfers directly through exponentiation, which isn't mathematically justified. Remember this pattern: when you see "if $f(n)$ has property P, then $n$ has property Q" in number theory, look for algebraic identities that connect the structure of $n$ to the factorization of $f(n)$ . The contrapositive approach often reveals these connections most clearly.
Consider the statement "If $S \subseteq \mathbb{R}$ is bounded above and $\sup(S)$ exists, then for every $\varepsilon > 0$ , there exists $s \in S$ such that $s > \sup(S) - \varepsilon$ ." Which contrapositive formulation captures the logical structure most precisely?
Answer: If there exists $\varepsilon > 0$ such that for all $s \in S$ , $s \leq \sup(S) - \varepsilon$ , then $S$ is not bounded above or $\sup(S)$ does not exist. When you encounter contrapositive problems in discrete math, remember that the contrapositive of "If P, then Q" is "If not Q, then not P." Both statements are logically equivalent, so finding the correct contrapositive requires careful negation of both the hypothesis and conclusion. The original statement has the structure: "If [S is bounded above AND sup(S) exists], then [for every ε > 0, there exists s ∈ S such that s > sup(S) - ε]." To form the contrapositive, you need to negate both parts. The negation of "for every ε > 0, there exists s ∈ S such that s > sup(S) - ε" is "there exists ε > 0 such that for all s ∈ S, s ≤ sup(S) - ε." The negation of "S is bounded above AND sup(S) exists" is "S is not bounded above OR sup(S) does not exist." Answer B correctly captures this logical structure with precise quantifier placement and proper negation. Answer A uses "no element satisfies" instead of the more precise "for all s ∈ S, s ≤ sup(S) - ε," making it less mathematically rigorous. Answer C incorrectly negates the quantifiers—it should be "there exists ε" not "for all ε." Answer D uses vague language like "bounded nature fails" rather than the precise logical negation, and uses s < instead of s ≤. Study tip: When forming contrapositives, write out the logical structure with quantifiers first (∀, ∃), then carefully apply negation rules: ¬(∀x P(x)) = ∃x ¬P(x) and ¬(∃x P(x)) = ∀x ¬P(x).
Consider proving by contrapositive: "If $a$ , $b$ , and $c$ are positive integers with $a^2 + b^2 = c^2$ , then at least one of $a$ or $b$ is even." The contrapositive assumes both $a$ and $b$ are odd. If $a = 2m + 1$ and $b = 2n + 1$ , what can be concluded about $a^2 + b^2$ ?
Answer: $a^2 + b^2 \equiv 2 \pmod{4}$ , but any perfect square is congruent to 0 or 1 modulo 4, so $c^2$ cannot equal $a^2 + b^2$ . When you encounter a proof by contrapositive, you're proving "If P, then Q" by showing "If not Q, then not P." Here, we assume both $a$ and $b$ are odd and seek a contradiction with $a^2 + b^2 = c^2$ . Let's work with odd integers. If $a = 2m + 1$ and $b = 2n + 1$ , then: $a^2 = (2m + 1)^2 = 4m^2 + 4m + 1$ $b^2 = (2n + 1)^2 = 4n^2 + 4n + 1$ Therefore: $a^2 + b^2 = 4m^2 + 4m + 1 + 4n^2 + 4n + 1 = 4(m^2 + m + n^2 + n) + 2$ This shows $a^2 + b^2 \equiv 2 \pmod{4}$ . However, any perfect square can only be congruent to 0 or 1 modulo 4. You can verify this: if $c$ is even, $c^2 \equiv 0 \pmod{4}$ ; if $c$ is odd, $c^2 \equiv 1 \pmod{4}$ . Since $c^2$ cannot be congruent to 2 modulo 4, we have our contradiction. Answer C captures this reasoning perfectly. Answer A contains the correct algebraic manipulation but incorrectly states the sum is "never divisible by 4" when it actually leaves remainder 2 when divided by 4. Answer B stops too early—being even doesn't create a contradiction by itself. Answer D is nonsensical since the sum of integers is always rational. Study tip: When proving statements about even/odd integers, modular arithmetic (especially mod 4) often reveals contradictions that basic even/odd analysis misses. Perfect squares have very specific patterns modulo 4.
Consider proving "If $a$ and $b$ are integers such that $ab$ is not divisible by 3, then neither $a$ nor $b$ is divisible by 3." The contrapositive approach requires assuming which condition and proving what conclusion?
Answer: Assume at least one of $a$ or $b$ is divisible by 3, then prove $ab$ is divisible by 3 using the fundamental theorem of arithmetic. The original statement is "If $ab$ is not divisible by 3, then neither $a$ nor $b$ is divisible by 3." The contrapositive is "If at least one of $a$ or $b$ is divisible by 3, then $ab$ is divisible by 3." Choice A correctly identifies this. Choice B proves the original statement directly. Choice C reverses the logic. Choice D assumes too strong a condition (both divisible by 3) rather than the correct assumption (at least one divisible by 3).
Consider the statement: "If $n$ is a positive integer and $n^2 + n + 1$ is divisible by 3, then $n$ is divisible by 3." To prove this by contrapositive, we assume $n$ is not divisible by 3. What are the possible remainders when $n^2 + n + 1$ is divided by 3?
Answer: Only remainder 1, proving the contrapositive since $n^2 + n + 1$ is never divisible by 3 when $n$ is not divisible by 3. If $n$ is not divisible by 3, then $n \equiv 1 \pmod{3}$ or $n \equiv 2 \pmod{3}$ . Case 1: If $n \equiv 1 \pmod{3}$ , then $n^2 \equiv 1 \pmod{3}$ and $n^2 + n + 1 \equiv 1 + 1 + 1 \equiv 0 \equiv 1 \pmod{3}$ . Case 2: If $n \equiv 2 \pmod{3}$ , then $n^2 \equiv 4 \equiv 1 \pmod{3}$ and $n^2 + n + 1 \equiv 1 + 2 + 1 \equiv 4 \equiv 1 \pmod{3}$ . In both cases, $n^2 + n + 1$ has remainder 1 when divided by 3, so it's never divisible by 3. This proves the contrapositive. Choice B is incorrect about the remainder. Choice C incorrectly claims both remainders 1 and 2 are possible. Choice D misunderstands that finding only remainder 1 actually strengthens the proof.

Start this quiz