Proof by contradictionEdexcel International A Level Maths: Subtopic test

1. 1
   A student begins a proof by contradiction that $\sqrt2$ is irrational.

   (a)

   Which assumption should the proof begin with?

   [1 mark]

   • A$\sqrt2$ is irrational
   • B$\sqrt2=\frac{p}{q}$, where $p$ and $q$ are integers with no common factor other than 1 and $q\neq0$
   • C$\sqrt2$ is an integer
   • D$\sqrt2=\frac{p}{q}$, where $p$ and $q$ are both even

   (b)

   The assumption leads to $p^2=2q^2$. Which deduction follows directly?

   [1 mark]

   • A$p$ is a prime number
   • B$q$ is even and $p$ is odd
   • C$p$ and $q$ are both odd
   • D$p^2$ is even, so $p$ is even

   (c)

   Given that $p^2=2q^2$ and so $p$ is even, complete the proof.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   Euclid's proof that there are infinitely many primes begins by assuming that there are only finitely many primes, $p_1,p_2,\ldots,p_n$. Let $N=p_1p_2\cdots p_n+1$.

   (a)

   What is the remainder when $N$ is divided by any one of the primes $p_i$?

   [1 mark]

   • A$1$
   • B$0$
   • C$p_i$
   • D$2$

   (b)

   Which conclusion completes the argument?

   [1 mark]

   • A$N$ must itself be prime
   • B$N$ is divisible by every $p_i$
   • C$N$ has a prime factor that is not in the list, contradicting the assumption that the list contains every prime
   • D$N=1$

   (c)

   A student takes the first six primes, $2,3,5,7,11,13$, so $N=30031$. Show that $N$ is not prime, and state what this shows about Euclid's argument.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   In a proof by contradiction you assume that the statement is false and show that this leads to an impossible result.

   (a)

   Prove by contradiction that there are no integers $m$ and $n$ such that $14m+21n=1$.

   [3 marks]

   (b)

   Prove by contradiction that $\log_23$ is irrational.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   Use proof by contradiction in each part. You may use the fact that $\sqrt2$ is irrational.

   (a)

   Prove that $\sqrt2+\sqrt3$ is irrational.

   [6 marks]

   (b)

   Prove that the equation $x^2-y^2=2$ has no solutions in which $x$ and $y$ are both integers.

   [6 marks]

   Total for question 4: 12 marks

End of questions