Proof by contradiction - Discrete Math

1. In attempting to prove by contradiction that $\log_2 3$ is irrational, a student assumes $\log_2 3 = \frac{p}{q}$ where $p$ and $q$ are integers with $q \neq 0$ and $\gcd(p,q) = 1$. After converting to exponential form, which equation should the student obtain?
   Answer: $2^{p/q} = 3$, which leads to $2^p = 3^q$ after raising both sides to the $q$-th power. When proving irrationality by contradiction, you assume the number is rational and show this leads to an impossible conclusion. For logarithms, this means assuming $\log_2 3 = \frac{p}{q}$ where $p$ and $q$ are integers in lowest terms. The key step is converting from logarithmic to exponential form using the definition: if $\log_b x = y$, then $b^y = x$. Applying this to $\log_2 3 = \frac{p}{q}$, you get $2^{p/q} = 3$. To eliminate the fraction in the exponent, raise both sides to the $q$-th power: $(2^{p/q})^q = 3^q$, which simplifies to $2^p = 3^q$. Answer C correctly captures this process: starting with $2^{p/q} = 3$ and obtaining $2^p = 3^q$ after raising both sides to the $q$-th power. Answer A has the right final equation $2^p = 3^q$ but doesn't show how to derive it from the logarithmic assumption. Answer B incorrectly starts with $3^{p/q} = 2$, which would come from assuming $\log_3 2 = \frac{p}{q}$, not $\log_2 3 = \frac{p}{q}$. Answer D uses the change of base formula but skips the crucial step of converting to exponential form, which is essential for this type of proof. Study tip: In logarithm irrationality proofs, always convert to exponential form first using $\log_b x = y \iff b^y = x$. This transforms the problem into showing that powers of different primes cannot be equal.
2. A proof by contradiction aims to show that the equation $x^2 - 2x + 5 = 0$ has no real solutions. The proof begins by assuming there exists a real number $x$ such that $x^2 - 2x + 5 = 0$. Which manipulation most directly leads to the desired contradiction?
   Answer: Complete the square to get $(x-1)^2 + 4 = 0$, which implies $(x-1)^2 = -4$ and contradicts the non-negativity of squares. When you encounter a proof by contradiction problem, you're looking for the most direct path from your assumption to an impossible conclusion. The key is finding which algebraic manipulation immediately reveals something that cannot be true in the real numbers. Starting with the assumption that there exists a real number $x$ satisfying $x^2 - 2x + 5 = 0$, option D provides the cleanest contradiction. Completing the square transforms this equation into $(x-1)^2 + 4 = 0$, which rearranges to $(x-1)^2 = -4$. This directly contradicts a fundamental property of real numbers: squares are always non-negative. Since no real number squared can equal $-4$, we've reached our contradiction in just two steps. Option A uses calculus concepts that, while valid, go beyond basic algebraic manipulation and aren't necessary for this proof. Option B applies the quadratic formula correctly and does reveal complex solutions, but the question asks for the most direct contradiction from the algebraic assumption, not a formula application. Option C attempts to compare signs but is flawed—when $x = 1$, both sides equal 1, and the right side $2x - 5$ isn't always negative, so this doesn't create a reliable contradiction. For proof by contradiction problems involving quadratic equations, completing the square is often your best strategy. It directly exposes contradictions by isolating perfect squares and revealing when they would need to equal negative values, which is impossible for real numbers.
3. A student wants to prove by contradiction that if $n$ is an integer and $n^2$ is divisible by 4, then $n$ is even. They assume $n$ is odd and $n^2$ is divisible by 4. Writing $n = 2k + 1$ for some integer $k$, what form does $n^2$ take that reveals the contradiction?
   Answer: $n^2 = 4k^2 + 4k + 1 = 4(k^2 + k) + 1$, showing $n^2$ leaves remainder 1 when divided by 4. Proof by contradiction is a powerful technique where you assume the opposite of what you want to prove and show this leads to an impossibility. Here, we're assuming $n$ is odd (opposite of even) while $n^2$ is divisible by 4, then looking for a contradiction. When $n$ is odd, we can write $n = 2k + 1$ for some integer $k$. Squaring this gives us: $n^2 = (2k + 1)^2 = 4k^2 + 4k + 1$ The key insight is recognizing how to rewrite this expression to reveal the remainder when divided by 4. We can factor out 4 from the first two terms: $n^2 = 4k^2 + 4k + 1 = 4(k^2 + k) + 1$ Since $k^2 + k$ is an integer, this shows $n^2$ has the form "4 times an integer plus 1," meaning $n^2$ leaves remainder 1 when divided by 4. But we assumed $n^2$ is divisible by 4 (remainder 0). This contradiction proves our assumption was wrong. Choice A incorrectly focuses on $n^2$ being odd, but odd numbers can sometimes be divisible by 4 conceptually - this misses the key point about remainders. Choice B makes an algebraic error: $4(k^2 + k + 1) - 3 = 4k^2 + 4k + 4 - 3 = 4k^2 + 4k + 1$, but the factoring is wrong. Choice D gives a correct but less useful form that doesn't clearly show the remainder when dividing by 4. Study tip: In modular arithmetic proofs, always try to express your result in the form "multiple of n plus remainder" to make divisibility contradictions crystal clear.
4. To prove by contradiction that there are infinitely many prime numbers, Euclid's argument assumes there are only finitely many primes $p_1, p_2, \ldots, p_k$. The proof then considers the number $N = p_1 \cdot p_2 \cdot \ldots \cdot p_k + 1$. What property of $N$ leads to the contradiction?
   Answer: $N$ must have a prime divisor not in the list $\{p_1, p_2, \ldots, p_k\}$, contradicting the assumption of finitely many primes. The key insight is that N must have at least one prime divisor (since N > 1). However, N leaves remainder 1 when divided by any of the supposedly complete list of primes p₁, p₂, ..., pₖ. Therefore, N cannot be divisible by any prime in our finite list, so there must exist a prime divisor of N that's not in the list. This contradicts our assumption that the list contains all primes. Choice B incorrectly assumes N must be composite. Choice C misunderstands the divisibility relationship. Choice D incorrectly assumes N itself must be prime.
5. A student wants to prove by contradiction that there are infinitely many prime numbers. They assume there are only finitely many primes $p_1, p_2, \ldots, p_k$ and consider the number $N = p_1 \cdot p_2 \cdot \ldots \cdot p_k + 1$. Which statement most accurately describes what the student must show to complete the contradiction?
   Answer: The number $N$ cannot be divisible by any prime in our list, yet every integer greater than 1 has a prime divisor, so $N$ must have a prime divisor not in our supposedly complete list. Choice B correctly identifies the key insight. Since $N = p_1 \cdot p_2 \cdot \ldots \cdot p_k + 1$, when we divide $N$ by any prime $p_i$ in our list, we get remainder 1, so none of the primes $p_1, p_2, \ldots, p_k$ divide $N$. However, by the Fundamental Theorem of Arithmetic, $N > 1$ must have at least one prime divisor. This prime divisor cannot be any of $p_1, p_2, \ldots, p_k$, contradicting our assumption that these were all the primes. Choice A incorrectly assumes $N$ must be prime (it might be composite with prime factors not in our list). Choice C makes an invalid parity argument. Choice D misunderstands what 'remainder 1' means in this context.
6. To prove that $\sqrt[3]{2}$ is irrational, a student assumes $\sqrt[3]{2} = \frac{a}{b}$ where $a$ and $b$ are positive integers with $\gcd(a,b) = 1$. After cubing both sides, they get $2 = \frac{a^3}{b^3}$, so $2b^3 = a^3$. Which of the following correctly identifies why this leads to a contradiction?
   Answer: Since $2b^3 = a^3$ and 2 is prime, we know 2 divides $a^3$. This means 2 divides $a$, so $a = 2k$. Substituting: $2b^3 = 8k^3$, giving $b^3 = 4k^3$. Since $4 = 2^2$, we have $2^2$ divides $b^3$, so 2 divides $b$. Thus $\gcd(a,b) \geq 2$, contradicting $\gcd(a,b) = 1$. When you encounter an irrationality proof, you're typically using proof by contradiction: assume the number is rational, then show this assumption leads to an impossible situation. The correct reasoning follows option D. Starting from $2b^3 = a^3$, since 2 is prime and divides $a^3$, it must also divide $a$. So we can write $a = 2k$ for some integer $k$. Substituting this back: $2b^3 = (2k)^3 = 8k^3$, which simplifies to $b^3 = 4k^3$. Since $4 = 2^2$ divides $b^3$, we know 2 must divide $b$. But now both $a$ and $b$ are divisible by 2, so $\gcd(a,b) \geq 2$, contradicting our assumption that $\gcd(a,b) = 1$. Option A uses correct prime factorization logic but makes an error in reasoning. The equation $a^3 = 2b^3$ doesn't mean $a^3$ has exactly one factor of 2—it could have more factors of 2 from $b^3$. Option B starts correctly but makes a logical leap, claiming that since 4 divides $b^3$, then 4 must divide $b$. This isn't necessarily true—if 4 divides $b^3$, only 2 needs to divide $b$. Option C misunderstands proof by contradiction entirely. The fact that we arrive back at our assumption isn't circular reasoning—it's exactly what we expect before finding the actual contradiction. Remember: in irrationality proofs, look for the moment when you can show both numerator and denominator share a common factor, violating the "lowest terms" assumption.
7. To prove that $\log_{10} 2$ is irrational, a student uses proof by contradiction. They assume $\log_{10} 2 = \frac{p}{q}$ where $p$ and $q$ are integers with $q > 0$ and $\gcd(p,q) = 1$. Converting to exponential form gives $10^{p/q} = 2$. After raising both sides to the power $q$, they obtain $10^p = 2^q$. Which statement best explains why this equation leads to a contradiction?
   Answer: The left side $10^p = (2 \cdot 5)^p = 2^p \cdot 5^p$ contains $5^p$ as a factor, while the right side $2^q$ contains no factors of 5. By unique prime factorization, these cannot be equal unless $p = 0$, but then $1 = 2^q$ implies $q = 0$, contradicting $q > 0$. When you encounter irrationality proofs by contradiction, the key insight is usually finding where fundamental mathematical principles like unique prime factorization create an impossible situation. The equation $10^p = 2^q$ leads to a contradiction through prime factorization analysis. Since $10 = 2 \times 5$, we can rewrite the left side as $(2 \cdot 5)^p = 2^p \cdot 5^p$. This gives us $2^p \cdot 5^p = 2^q$. By the Fundamental Theorem of Arithmetic, every integer has a unique prime factorization. The left side contains $5^p$ as a factor (where $p$ must be positive for equality), while the right side $2^q$ contains only powers of 2 and no factors of 5. This violates unique prime factorization unless $p = 0$, but then $10^0 = 1 = 2^q$ would require $q = 0$, contradicting our assumption that $q > 0$. Option A correctly identifies that powers of 10 and powers of 2 cannot be equal, but doesn't provide the rigorous prime factorization argument needed. Option B describes circular reasoning, but the algebra shown isn't actually circular—it's valid manipulation that doesn't create the contradiction. Option D attempts a parity argument by dividing by $2^p$, but this approach is flawed because it assumes $q > p$ without justification, and the division step doesn't preserve the integer relationship needed. Remember: In irrationality proofs, look for contradictions arising from unique prime factorization when you have equations involving different prime bases.
8. Consider proving by contradiction that there is no largest even integer. A student begins by assuming "there exists a largest even integer $M$". To complete the proof, which approach correctly leads to a contradiction?
   Answer: Show that $M + 2$ is also even and $M + 2 > M$, contradicting the assumption that $M$ is largest. When approaching proof by contradiction problems, you need to show that your assumption leads to an impossible situation. Here, you're assuming there exists a largest even integer $M$ and must demonstrate this creates a logical contradiction. The key insight is that if $M$ is truly the largest even integer, then no even integer can be greater than $M$. To contradict this, you need to construct another even integer that's larger than $M$. Answer D does exactly this: if $M$ is even, then $M + 2$ is also even (since adding 2 to any even number yields another even number), and clearly $M + 2 > M$. This directly contradicts the assumption that $M$ is the largest even integer. Answer A fails because while $\frac{M}{2}$ is indeed an integer and $M < 2M$, this doesn't create a contradiction—$2M$ isn't necessarily even, and even if it were, being larger than $M$ is expected, not contradictory. Answer B is flawed because finding a smaller even integer ($M - 2$) doesn't contradict the claim that $M$ is the largest—you'd expect smaller even integers to exist. Answer C has the right idea about finding a larger even integer, but $M^2 > M$ only holds for $M \geq 3$, making this argument incomplete for cases like $M = 2$. Remember: in contradiction proofs, you must show your assumption leads to something impossible. When dealing with "largest" or "smallest" claims about infinite sets, construct a counterexample that violates the assumed boundary.
9. To prove that the equation $x^2 + y^2 = 3$ has no integer solutions, a student uses proof by contradiction. They assume there exist integers $x$ and $y$ such that $x^2 + y^2 = 3$ and consider this equation modulo 4. Which of the following correctly completes the contradiction?
   Answer: Since squares modulo 4 can only be 0 or 1, we have $x^2 + y^2 \equiv 0, 1,$ or $2 \pmod{4}$. But $3 \equiv 3 \pmod{4}$, which is impossible, giving our contradiction. Choice A correctly applies modular arithmetic. For any integer $n$, we have $n \equiv 0, 1, 2,$ or $3 \pmod{4}$. Computing squares: $0^2 \equiv 0$, $1^2 \equiv 1$, $2^2 \equiv 0$, and $3^2 \equiv 1 \pmod{4}$. So $n^2 \equiv 0$ or $1 \pmod{4}$ for any integer $n$. Therefore $x^2 + y^2$ can only be congruent to $0 + 0 = 0$, $0 + 1 = 1$, $1 + 0 = 1$, or $1 + 1 = 2 \pmod{4}$. Since $3 \equiv 3 \pmod{4}$, the equation $x^2 + y^2 = 3$ is impossible. Choice B uses a valid but incomplete approach (doesn't check $(x,y) = (\pm 1, \pm \sqrt{2})$). Choice C incorrectly states $3 \equiv -1 \pmod{4}$ (actually $3 \equiv 3 \pmod{4}$). Choice D misses the case where both $|x|$ and $|y|$ could equal 1.
10. Consider the statement: "For all integers $n$, if $n^2$ is even, then $n$ is even." Which of the following correctly identifies the assumption made in a proof by contradiction of this statement?
    Answer: Assume there exists an integer $n$ such that $n^2$ is even and $n$ is odd, then derive a contradiction. In proof by contradiction, we assume the negation of what we want to prove. The original statement is "For all integers n, if n² is even, then n is even." Its negation is "There exists an integer n such that n² is even and n is not even (i.e., odd)." Choice A correctly states this assumption. Choice B reverses the conditions incorrectly. Choice C attempts to prove the contrapositive rather than using contradiction. Choice D also reverses the logical relationship between the hypothesis and conclusion.
11. Consider proving by contradiction that there exist irrational numbers $a$ and $b$ such that $a^b$ is rational. The proof assumes the contrary: for all irrational $a$ and $b$, $a^b$ is irrational. Which case analysis correctly establishes the contradiction?
    Answer: Consider $\sqrt{2}^{\sqrt{2}}$. If rational, we're done. If irrational, then $(\sqrt{2}^{\sqrt{2}})^{\sqrt{2}} = \sqrt{2}^2 = 2$ is rational, giving our counterexample. Proof by contradiction is a powerful technique where you assume the opposite of what you want to prove, then show this leads to a logical impossibility. Here, we want to prove irrational numbers $a$ and $b$ exist such that $a^b$ is rational, so we assume the contrary: whenever $a$ and $b$ are both irrational, $a^b$ must be irrational. The clever strategy is to consider $\sqrt{2}^{\sqrt{2}}$ and use case analysis. Since $\sqrt{2}$ is irrational, we have two possibilities for $\sqrt{2}^{\sqrt{2}}$: either it's rational or irrational. If $\sqrt{2}^{\sqrt{2}}$ is rational, we immediately have our counterexample—two irrational numbers whose power is rational, contradicting our assumption. If $\sqrt{2}^{\sqrt{2}}$ is irrational, then consider $(\sqrt{2}^{\sqrt{2}})^{\sqrt{2}} = \sqrt{2}^{\sqrt{2} \cdot \sqrt{2}} = \sqrt{2}^2 = 2$. Here we have an irrational base ($\sqrt{2}^{\sqrt{2}}$) and irrational exponent ($\sqrt{2}$) producing a rational result (2), again contradicting our assumption. Choice A reverses the logic incorrectly. Choice C discusses addition of irrationals, which is irrelevant to our exponentiation problem. Choice D mentions $e^{\pi}$ and "known results" but provides no concrete contradiction—we actually don't know whether $e^{\pi}$ is rational or irrational. Study tip: In proof by contradiction with case analysis, ensure your cases are exhaustive and that each case leads to the same contradiction. The beauty of choice B is that both possible cases for $\sqrt{2}^{\sqrt{2}}$ give us what we need.
12. Consider the statement: "For any integer $n$, if $n^2$ is even, then $n$ is even." A student attempts to prove this by contradiction, assuming $n^2$ is even but $n$ is odd. If $n$ is odd, then $n = 2k + 1$ for some integer $k$. What contradiction emerges when the student computes $n^2$?
    Answer: Computing $n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$, which shows $n^2$ is odd, contradicting the assumption that $n^2$ is even. Choice A correctly identifies the contradiction. When $n = 2k + 1$, we have $n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$. Since $2k^2 + 2k$ is an integer, this shows $n^2$ has the form $2m + 1$ where $m = 2k^2 + 2k$, meaning $n^2$ is odd. This directly contradicts our assumption that $n^2$ is even. Choice B makes an error in the expansion (missing the $4k$ term). Choice C incorrectly suggests numbers can have "both even and odd components." Choice D has an algebraic error in the expansion and misapplies the law of excluded middle.
13. A student wants to prove by contradiction that if $a$ and $b$ are rational numbers with $b \neq 0$, then $a + b\sqrt{2}$ is irrational when $a \neq 0$ or $b \neq 0$ (i.e., not both zero). They assume $a + b\sqrt{2}$ is rational and equal to some rational number $\frac{r}{s}$ where $\gcd(r,s) = 1$. Which manipulation correctly leads to a contradiction?
    Answer: From $a + b\sqrt{2} = \frac{r}{s}$, we get $\sqrt{2} = \frac{r/s - a}{b} = \frac{r - as}{sb}$. Since the right side is rational (being a quotient of integers with $sb \neq 0$) but $\sqrt{2}$ is irrational, we have a contradiction. Proof by contradiction is a powerful technique where you assume the opposite of what you want to prove and show this leads to an impossible situation. When proving that expressions involving irrational numbers like $\sqrt{2}$ are irrational, the key is isolating $\sqrt{2}$ on one side of an equation. Option D correctly identifies the winning approach. Starting from the assumption $a + b\sqrt{2} = \frac{r}{s}$, you rearrange to isolate $\sqrt{2}$: $\sqrt{2} = \frac{r/s - a}{b} = \frac{r - as}{sb}$. Since $a$ and $\frac{r}{s}$ are both rational, their difference $\frac{r}{s} - a$ is rational. Dividing by the rational number $b$ gives another rational number. But this contradicts the fact that $\sqrt{2}$ is irrational. Option A fails because it doesn't actually create a contradiction—it just restates that one form "looks irrational" without proving anything. Option B makes an error by assuming $2ab\sqrt{2}$ is necessarily irrational, but if $a = 0$, then $2ab\sqrt{2} = 0$, which is rational. Option C incorrectly claims the right side $\frac{r(a - b\sqrt{2})}{s}$ is irrational, but since we assumed $a + b\sqrt{2}$ is rational, the conjugate expression $a - b\sqrt{2}$ could also be rational. Study tip: In contradiction proofs involving $\sqrt{2}$, always try to isolate $\sqrt{2}$ and show it equals something rational. This creates the clearest, most direct contradiction since $\sqrt{2}$ is fundamentally irrational.
14. To prove by contradiction that $\sqrt{2} + \sqrt{3}$ is irrational, suppose $\sqrt{2} + \sqrt{3} = r$ for some rational number $r$. After rearranging to $\sqrt{2} = r - \sqrt{3}$ and squaring both sides, which equation results?
    Answer: $2 = r^2 - 2r\sqrt{3} + 3$, which can be rearranged to $\sqrt{3} = \frac{r^2 + 1}{2r}$, showing $\sqrt{3}$ is rational. Proof by contradiction is a powerful technique where you assume the opposite of what you want to prove, then show this leads to an impossibility. Here, we're proving $\sqrt{2} + \sqrt{3}$ is irrational by assuming it's rational and finding a contradiction. Starting with $\sqrt{2} + \sqrt{3} = r$ where $r$ is rational, we rearrange to get $\sqrt{2} = r - \sqrt{3}$. When we square both sides, we need to carefully expand the right side using the formula $(a - b)^2 = a^2 - 2ab + b^2$. So $(\sqrt{2})^2 = (r - \sqrt{3})^2$ becomes: $2 = r^2 - 2r\sqrt{3} + (\sqrt{3})^2$ $2 = r^2 - 2r\sqrt{3} + 3$ Rearranging to isolate the irrational term: $2r\sqrt{3} = r^2 + 3 - 2 = r^2 + 1$, so $\sqrt{3} = \frac{r^2 + 1}{2r}$. Since $r$ is rational, this fraction is also rational, contradicting the fact that $\sqrt{3}$ is irrational. Choice A incorrectly writes $r^2 + 3 - 2r\sqrt{3}$ instead of $r^2 - 2r\sqrt{3} + 3$, scrambling the order of terms. Choice C has the wrong left side (4 instead of 2). Choice D correctly expands the square but makes an algebraic error when rearranging, getting $\frac{r^2 - 1}{2r}$ instead of $\frac{r^2 + 1}{2r}$. The correct answer is B. Study tip: In proof by contradiction problems involving irrationals, always double-check your algebraic manipulations—small errors in expanding or rearranging can derail the entire proof structure.
15. Consider the statement: "For all real numbers $x$, if $x^3 + x + 1 > 0$, then $x > -1$." To prove this by contradiction, what should be assumed, and what type of contradiction should be sought?
    Answer: Assume there exists $x \leq -1$ such that $x^3 + x + 1 > 0$, then show this leads to a numerical contradiction. When you encounter proof by contradiction problems, you need to carefully identify what to assume and what contradiction to derive. The key is understanding that to prove an implication "if P, then Q" by contradiction, you assume P is true and Q is false, then show this leads to an impossibility. The original statement has the form: "For all real numbers $x$, if $x^3 + x + 1 > 0$, then $x > -1$." To prove this by contradiction, you assume there exists some $x$ where the hypothesis is true ($x^3 + x + 1 > 0$) but the conclusion is false ($x \leq -1$). Then you show this assumption leads to a contradiction. Option C correctly identifies this approach: assume there exists $x \leq -1$ such that $x^3 + x + 1 > 0$, then derive a numerical contradiction (likely by showing that for $x \leq -1$, we must actually have $x^3 + x + 1 \leq 0$). Option A is wrong because it assumes something about all $x \leq -1$, which isn't the proper negation of the original statement. Option B incorrectly assumes the conclusion is true while making the hypothesis false, which is backwards. Option D has the right setup but seeks the wrong type of contradiction—you want to derive a numerical impossibility, not just show the opposite inequality. Study tip: In proof by contradiction for universal statements "∀x (P(x) → Q(x))", always assume "∃x (P(x) ∧ ¬Q(x))" and derive a logical impossibility from there.
16. To prove that $\sqrt{3}$ is irrational, a student begins by assuming $\sqrt{3} = \frac{a}{b}$ where $a$ and $b$ are integers with $\gcd(a,b) = 1$. After squaring both sides and rearranging, the student obtains $3b^2 = a^2$. Which of the following correctly identifies the key contradiction that completes this proof?
    Answer: Since $3$ divides $a^2$, we have $3$ divides $a$, so $a = 3k$ for some integer $k$. Substituting gives $3b^2 = 9k^2$, so $b^2 = 3k^2$, meaning $3$ divides $b^2$ and thus $3$ divides $b$. This contradicts $\gcd(a,b) = 1$. Choice A correctly identifies the complete contradiction argument. From $3b^2 = a^2$, since 3 divides the right side, 3 must divide $a^2$. Since 3 is prime, this means 3 divides $a$, so $a = 3k$. Substituting back: $3b^2 = (3k)^2 = 9k^2$, so $b^2 = 3k^2$. This means 3 divides $b^2$, and again since 3 is prime, 3 divides $b$. But if both $a$ and $b$ are divisible by 3, then $\gcd(a,b) \geq 3$, contradicting our assumption that $\gcd(a,b) = 1$. Choice B incorrectly claims $a$ must be divisible by 9. Choice C makes an invalid parity argument. Choice D presents circular reasoning that doesn't constitute a proper contradiction.
17. Consider the statement: "There is no largest even integer." To prove this by contradiction, a student assumes there exists a largest even integer $N$. Which of the following arguments correctly derives a contradiction from this assumption?
    Answer: If $N$ is the largest even integer, then $N + 1$ is odd and $N + 2$ is even. Since $N + 2 > N$, we have found an even integer larger than the supposedly largest even integer $N$. Choice A provides the correct and most straightforward contradiction. If $N$ is even, then $N + 2$ is also even (since adding 2 to an even number yields an even number). Since $N + 2 > N$, this directly contradicts the assumption that $N$ is the largest even integer. Choice B incorrectly assumes the largest even integer must be positive - it could be negative, and even if positive, the argument about $2N$ being larger works but is unnecessarily complex. Choice C doesn't provide a proper contradiction - having infinitely many odd integers doesn't contradict having a largest even integer. Choice D has a logical error in the inequality $N^2 \geq N^2 > N$ (the first inequality is trivial equality) and fails for $N = 0$ or negative values.
18. A proof by contradiction aims to show that the system of equations $\begin{cases} x + y = 1 \\ x + y = 2 \end{cases}$ has no solution. After assuming a solution $(x_0, y_0)$ exists, which step most directly establishes the contradiction?
    Answer: From the assumed solution: $x_0 + y_0 = 1$ and $x_0 + y_0 = 2$, so $1 = 2$ by transitivity of equality. When you encounter a proof by contradiction, you're assuming the opposite of what you want to prove, then showing this assumption leads to a logical impossibility. Here, we assume a solution $(x_0, y_0)$ exists and look for the most direct path to contradiction. If $(x_0, y_0)$ is indeed a solution, it must satisfy both equations simultaneously. This means $x_0 + y_0 = 1$ (from the first equation) and $x_0 + y_0 = 2$ (from the second equation). Since both statements must be true for the same values of $x_0$ and $y_0$, we can apply the transitivity property of equality: if $A = B$ and $A = C$, then $B = C$. Therefore, $1 = 2$, which is clearly false. This direct logical contradiction proves no solution exists. Option A performs algebraic manipulation (subtracting equations) rather than working directly from the assumption of a solution's existence. While it reaches the same conclusion, it's less direct for a contradiction proof. Option C adds the equations to get $x_0 + y_0 = \frac{3}{2}$, but this creates a new constraint rather than directly showing the assumed solution leads to impossibility. Option D solves for $y_0$ in terms of $x_0$ from both equations, then equates them—this works but involves unnecessary algebraic steps. The key to contradiction proofs is finding the most direct path from your assumption to an obvious impossibility. Always look for the approach that requires the fewest intermediate steps while staying true to the logical structure of contradiction.
19. A student attempts to prove by contradiction that no integer $n$ satisfies $n^2 \equiv 2 \pmod{3}$. They assume such an $n$ exists and consider the possible remainders when $n$ is divided by 3. Which of the following correctly establishes the contradiction?
    Answer: If $n \equiv 0 \pmod{3}$, then $n^2 \equiv 0 \pmod{3}$. If $n \equiv 1 \pmod{3}$, then $n^2 \equiv 1 \pmod{3}$. If $n \equiv 2 \pmod{3}$, then $n^2 \equiv 4 \equiv 1 \pmod{3}$. In all cases, $n^2 \not\equiv 2 \pmod{3}$. When proving by contradiction that no integer satisfies a modular equation, you assume such an integer exists and show this leads to an impossibility. For modular arithmetic problems, the most systematic approach is often to check all possible remainders. Option C provides the correct proof. Since any integer $n$ must have remainder 0, 1, or 2 when divided by 3, we can check each case: If $n \equiv 0 \pmod{3}$, then $n^2 \equiv 0^2 \equiv 0 \pmod{3}$. If $n \equiv 1 \pmod{3}$, then $n^2 \equiv 1^2 \equiv 1 \pmod{3}$. If $n \equiv 2 \pmod{3}$, then $n^2 \equiv 2^2 \equiv 4 \equiv 1 \pmod{3}$. Since we've exhausted all possibilities and none yields $n^2 \equiv 2 \pmod{3}$, we have our contradiction. Option A incorrectly uses irrational numbers in a purely integer problem—the factorization with $\sqrt{2}$ is irrelevant to modular arithmetic. Option B makes an error by claiming that $n^2 \equiv 2 \pmod{3}$ implies $n^2 \equiv 2 \pmod{9}$, but this isn't necessarily true (modular properties don't work this way). Additionally, squares modulo 9 can actually be 0, 1, 4, or 7, but the reasoning chain itself is flawed. Option D creates a false parity argument—there's no meaningful connection between divisibility by 3 and the even/odd nature of expressions. Study tip: For modular contradiction proofs, systematically check all possible remainders. This exhaustive case analysis is usually the most reliable approach and avoids complex algebraic manipulations that can introduce errors.
20. A student attempts to prove by contradiction that $\sqrt{3}$ is irrational. They assume $\sqrt{3} = \frac{a}{b}$ where $a$ and $b$ are integers with $\gcd(a,b) = 1$. After squaring both sides and rearranging, they obtain $3b^2 = a^2$. What is the next crucial step to reach a contradiction?
    Answer: Show that $a$ must be divisible by 3, then show $b$ must also be divisible by 3, contradicting $\gcd(a,b) = 1$. From 3b² = a², we can conclude that 3 divides a² (since the left side is divisible by 3). Since 3 is prime, if 3 divides a², then 3 must divide a. Let a = 3k for some integer k. Substituting back: 3b² = (3k)² = 9k², so b² = 3k², which means 3 divides b² and therefore 3 divides b. This contradicts gcd(a,b) = 1. Choice B reverses the correct logical order. Choice C incorrectly focuses on even numbers rather than divisibility by 3. Choice D makes an invalid conclusion that a = b.

Start this quiz