Discrete Math Quiz: Proof By Contradiction

What this quiz covers

This quiz focuses on Proof By Contradiction, 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.

Question 1

1. 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. (correct answer)
2. Computing $n^2 = (2k + 1)^2 = 4k^2 + 2k + 1$, which cannot be factored as $2m$ for any integer $m$, contradicting the definition of even numbers.
3. Computing $n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = (2k)^2 + 4k + 1$, which shows that $n^2$ has both even and odd components, creating a logical impossibility.
4. Computing $n^2 = (2k + 1)^2 = 2k^2 + 4k + 1$, which simplifies to an expression that is neither clearly even nor clearly odd, contradicting the law of excluded middle.

Question 2

1. Use calculus to show the function $f(x) = x^2 - 2x + 5$ has a minimum value of 4, which is always positive.
2. Apply the quadratic formula to get $x = \frac{2 \pm \sqrt{-16}}{2}$, which involves the square root of a negative number.
3. Rearrange to $x^2 = 2x - 5$ and show that the left side is always non-negative while the right side can be negative.
4. Complete the square to get $(x-1)^2 + 4 = 0$, which implies $(x-1)^2 = -4$ and contradicts the non-negativity of squares. (correct answer)

Question 3

1. Consider $\sqrt{2}^{\sqrt{2}}$. If irrational, we're done. If rational, then $(\sqrt{2}^{\sqrt{2}})^{\sqrt{2}} = \sqrt{2}^2 = 2$ is rational, giving our counterexample.
2. 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. (correct answer)
3. Consider $\sqrt{2} + \sqrt{2}$. This equals $2\sqrt{2}$, which is irrational, contradicting our assumption about sums of irrationals.
4. Consider $e^{\pi}$. Since both $e$ and $\pi$ are irrational, our assumption says $e^{\pi}$ must be irrational, but this contradicts known results.

Question 4

1. Show that $\frac{M}{2}$ is an integer and $M < 2M$, contradicting the assumption that $M$ is largest.
2. Show that $M - 2$ is also even and $M - 2 < M$, contradicting the assumption that $M$ exists.
3. Show that $M^2$ is also even and $M^2 > M$ for $M \geq 3$, contradicting the maximality of $M$.
4. Show that $M + 2$ is also even and $M + 2 > M$, contradicting the assumption that $M$ is largest. (correct answer)

Question 5

1. $2 = r^2 + 3 - 2r\sqrt{3}$, which can be rearranged to $\sqrt{3} = \frac{r^2 - 1}{2r}$, showing $\sqrt{3}$ is rational.
2. $2 = r^2 - 2r\sqrt{3} + 3$, which can be rearranged to $\sqrt{3} = \frac{r^2 + 1}{2r}$, showing $\sqrt{3}$ is rational. (correct answer)
3. $4 = r^2 - 2r\sqrt{3} + 3$, which can be rearranged to $\sqrt{3} = \frac{r^2 - 1}{2r}$, showing $\sqrt{3}$ is rational.
4. $2 = r^2 - 2r\sqrt{3} + 3$, which can be rearranged to $\sqrt{3} = \frac{r^2 - 1}{2r}$, showing $\sqrt{3}$ is rational.

Question 6

1. Show that $a$ must be divisible by 3, then show $b$ must also be divisible by 3, contradicting $\gcd(a,b) = 1$. (correct answer)
2. Show that $b$ must be divisible by 3, then show $a$ must also be divisible by 3, contradicting $\gcd(a,b) = 1$.
3. Show that both $a$ and $b$ must be even numbers, which contradicts the assumption that $\sqrt{3}$ is rational.
4. Show that $3b^2 = a^2$ implies $a = b$, which contradicts the assumption that $\gcd(a,b) = 1$.

Question 7

1. $n^2 = 4k^2 + 4k + 1$, showing $n^2$ is always odd and therefore cannot be divisible by 4.
2. $n^2 = 4k^2 + 4k + 1 = 4(k^2 + k + 1) - 3$, showing $n^2$ leaves remainder 3 when divided by 4.
3. $n^2 = 4k^2 + 4k + 1 = 4(k^2 + k) + 1$, showing $n^2$ leaves remainder 1 when divided by 4. (correct answer)
4. $n^2 = (2k + 1)^2 = 2k(2k + 1) + 1$, showing $n^2$ is one more than an even number.

Question 8

1. $N$ must have a prime divisor not in the list $\{p_1, p_2, \ldots, p_k\}$, contradicting the assumption of finitely many primes. (correct answer)
2. $N$ must be composite since it's larger than all primes in the list, contradicting the fundamental theorem of arithmetic.
3. $N$ must be divisible by each prime $p_i$, contradicting the fact that $N \equiv 1 \pmod{p_i}$ for each $i$.
4. $N$ must be prime itself and larger than $p_k$, contradicting the assumption that $p_k$ is the largest prime.

Question 9

1. $2^p = 3^q$, which leads to $p \log 2 = q \log 3$ after taking natural logarithms of both sides.
2. $3^{p/q} = 2$, which leads to $3^p = 2^q$ after raising both sides to the $q$-th power.
3. $2^{p/q} = 3$, which leads to $2^p = 3^q$ after raising both sides to the $q$-th power. (correct answer)
4. $\frac{p}{q} = \frac{\log 3}{\log 2}$, which leads to $p \log 2 = q \log 3$ by cross multiplication.

Question 10

1. Subtracting the equations gives $0 = -1$, which is impossible, so no solution can exist for this system.
2. From the assumed solution: $x_0 + y_0 = 1$ and $x_0 + y_0 = 2$, so $1 = 2$ by transitivity of equality. (correct answer)
3. Adding the equations gives $2(x_0 + y_0) = 3$, so $x_0 + y_0 = \frac{3}{2}$, contradicting both original equations.
4. The first equation gives $y_0 = 1 - x_0$ and the second gives $y_0 = 2 - x_0$, so $1 - x_0 = 2 - x_0$, implying $1 = 2$.

Question 11

1. The equation $10^p = 2^q$ implies that $10^p$ is a power of 2, but since $10 = 2 \times 5$ and 5 is not a power of 2, no positive integer power of 10 can equal a power of 2.
2. Since $10^p = 2^q$, taking logarithms of both sides gives $p \log 10 = q \log 2$, so $\frac{p}{q} = \frac{\log 2}{\log 10} = \log_{10} 2$. This returns us to our original assumption, creating circular reasoning.
3. 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$. (correct answer)
4. From $10^p = 2^q$, we get $(2 \cdot 5)^p = 2^q$, which expands to $2^p \cdot 5^p = 2^q$. Dividing both sides by $2^p$ gives $5^p = 2^{q-p}$. Since the left side is odd and the right side is even for $q > p$, we have a contradiction.

Question 12

1. 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$. (correct answer)
2. Since $a^2 = 3b^2$, we know that $a^2$ is divisible by $3$, which means $a$ must be divisible by $9$. This contradicts the assumption that $\gcd(a,b) = 1$ since $9$ and $b$ cannot be coprime.
3. The equation $3b^2 = a^2$ implies that $a^2$ is odd since $3$ is odd, but $b^2$ must be even to make $3b^2$ divisible by an even number. This parity contradiction shows our assumption was false.
4. From $3b^2 = a^2$, we can write $\sqrt{3} = \frac{a}{b} = \frac{\sqrt{3b^2}}{b} = \sqrt{3}$, which is a circular statement that contradicts the original assumption that $\sqrt{3}$ can be written as a ratio.

Question 13

1. The number $N$ must be prime, but $N > p_k$, which contradicts the assumption that $p_k$ is the largest prime number in our finite list.
2. 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. (correct answer)
3. The number $N$ is both even and odd simultaneously, since adding 1 to an even product gives an odd result, but $N$ must also be even to have any prime factors.
4. The number $N$ equals 1 when divided by each prime in our list, but this means $N$ has remainder 1 with respect to every integer, which is impossible for numbers greater than 1.

Question 14

1. Raising both sides to the power $q$ gives $2^p = 3^q$. Since the left side is even and the right side is odd for any positive integers $p$ and $q$, we have a contradiction.
2. Raising both sides to the power $q$ gives $2^p = 3^q$. Since $2^p$ has only 2 as a prime factor and $3^q$ has only 3 as a prime factor, the Fundamental Theorem of Arithmetic guarantees these cannot be equal. (correct answer)
3. Taking logarithms of both sides of $2^{p/q} = 3$ gives $\frac{p}{q} \log 2 = \log 3$, which rearranges to our original assumption, creating circular reasoning and thus a contradiction.
4. Since $2 < 3 < 4 = 2^2$, we have $1 < \log_2 3 < 2$, which means $\frac{p}{q}$ must satisfy $1 < \frac{p}{q} < 2$. But this forces $q > p$, contradicting the requirement that $\gcd(p,q) = 1$.

Question 15

1. Since $a$ and $b$ are rational, $a + b\sqrt{2}$ can be written as $\frac{p}{q} + \frac{m}{n}\sqrt{2}$ where all variables are integers. Setting this equal to $\frac{r}{s}$ gives a contradiction because the left side has an irrational part while the right side doesn't.
2. Squaring both sides gives $a^2 + 2ab\sqrt{2} + 2b^2 = \frac{r^2}{s^2}$. Rearranging: $2ab\sqrt{2} = \frac{r^2}{s^2} - a^2 - 2b^2$. The left side is irrational while the right side is rational, giving a contradiction.
3. From $a + b\sqrt{2} = \frac{r}{s}$, multiplying by the conjugate $a - b\sqrt{2}$ gives $(a + b\sqrt{2})(a - b\sqrt{2}) = \frac{r}{s}(a - b\sqrt{2})$, which simplifies to $a^2 - 2b^2 = \frac{r(a - b\sqrt{2})}{s}$. This makes the left side rational and right side irrational.
4. 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. (correct answer)

Question 16

1. Since $a^3 = 2b^3$, the number $a^3$ has exactly one factor of 2 in its prime factorization. But if $a$ has $k$ factors of 2, then $a^3$ has $3k$ factors of 2. Setting $3k = 1$ gives $k = \frac{1}{3}$, which is impossible since $k$ must be an integer.
2. From $2b^3 = a^3$, we see that $a^3$ is even, which means $a$ is even. So $a = 2m$ and $2b^3 = (2m)^3 = 8m^3$, giving $b^3 = 4m^3$. Since 4 divides $b^3$, we have 4 divides $b$, so $b = 4n$. But then $\gcd(a,b) = \gcd(2m, 4n) \geq 2$, contradicting our assumption.
3. The equation $2b^3 = a^3$ implies $\frac{a^3}{b^3} = 2$, so $\left(\frac{a}{b}\right)^3 = 2$. Taking cube roots gives $\frac{a}{b} = \sqrt[3]{2}$, which is exactly our original assumption, creating circular reasoning and thus a contradiction.
4. 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$. (correct answer)

Question 17

1. If $n^2 \equiv 2 \pmod{3}$, then $n^2 - 2 \equiv 0 \pmod{3}$, meaning 3 divides $n^2 - 2$. But $n^2 - 2 = (n-\sqrt{2})(n+\sqrt{2})$, and since $\sqrt{2}$ is irrational, this factorization cannot involve integers, creating a contradiction.
2. Since $n^2 \equiv 2 \pmod{3}$, we have $n^2 = 3k + 2$ for some integer $k$. Taking this equation modulo 9 gives $n^2 \equiv 2 \pmod{9}$, but squares modulo 9 can only be 0, 1, 4, or 7, never 2.
3. 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}$. (correct answer)
4. Assuming $n^2 \equiv 2 \pmod{3}$ means $n^2 + 1 \equiv 0 \pmod{3}$, so 3 divides $n^2 + 1$. But $n^2 + 1$ is always even when $n$ is odd and always odd when $n$ is even, while 3 is odd, creating a parity contradiction.

Question 18

1. 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$. (correct answer)
2. If $N$ is the largest even integer, then $2N$ is also even. Since $N > 0$ (as the largest even integer must be positive), we have $2N > N$, contradicting the maximality of $N$.
3. If $N$ is the largest even integer, then all integers greater than $N$ must be odd. But this means there are infinitely many odd integers greater than $N$, which contradicts the finite nature of our assumption.
4. If $N$ is the largest even integer, consider $N^2$. Since $N$ is even, $N^2$ is also even, and $N^2 \geq N^2 > N$ for $N > 1$, giving us an even integer larger than $N$.

Question 19

1. 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. (correct answer)
2. Since $x$ and $y$ are integers, $x^2 \geq 0$ and $y^2 \geq 0$. The only way to get $x^2 + y^2 = 3$ is if one square is 0 and the other is 3, but 3 is not a perfect square.
3. Working modulo 4, if $x$ is even then $x^2 \equiv 0 \pmod{4}$, and if $x$ is odd then $x^2 \equiv 1 \pmod{4}$. The same holds for $y^2$. Since $3 \equiv -1 \pmod{4}$, we need $x^2 + y^2 \equiv -1 \pmod{4}$, which is impossible.
4. Since $3 < 4$, we must have $\max(|x|, |y|) = 1$. Checking all cases: $(\pm 1)^2 + 0^2 = 1 \neq 3$ and $0^2 + (\pm 1)^2 = 1 \neq 3$, giving our contradiction.