Proof by Contradiction (A Level only) (OCR A Level Maths: Pure)

Prove by contradiction that if is odd, then must be odd.

When a number is rational, it can be written in the form .

Write down the condition that and must satisfy.

Write down a further condition on .

Two numbers can be written in the form   and such that   meet the necessary conditions so that the two numbers are rational.

Prove that the product of these numbers is also rational.

Prove by contradiction that there are an infinite number of even numbers.

A student is attempting to answer the following exam question:

“Prove by contradiction that  is an irrational number. You may use without proof the fact that if a number is even, then n must also be even.”

The student’s proof proceeds as follows:

Line 1:	Assume  is a rational number.  Therefore, it can be written in the form , where  are integers with , and where and may be assumed to have no common factors.
Line 2:	Squaring both sides:
Line 3:
Line 4:
Line 5:	Therefore , for some integer
Line 6:	Then,
Line 7:
Line 8:
Line 9:	So is even and therefore is also even.
Line 10:	It has been shown that both and are even, so they share a common factor of 2.
Line 11:	This is a contradiction of the assumption that and have no common factors.
Line 12:	Therefore,  is irrational.

There is an error within the first three lines of the proof.

State what the error is and write the correct line down.

Line 4 of the proof is missing.

Write down the missing line of the proof.

A composite number can be written uniquely as the product of its prime factors.i.e., any composite number N can be written uniquely as , where  are the prime factors of N.

Show that a composite number N may be written in the form , where  is an integer and is a prime factor of N.

By expressing in terms of the prime factors of N, be sure to explain why  must be an integer.

Prove by contradiction that a triangle cannot have more than one obtuse angle.

Prove by contradiction that if is odd, then must be odd.

Prove that the product of two rational numbers is rational.

Prove by contradiction that there are an infinite number of powers of 2.

Prove by contradiction that  is an irrational number.  You may use without proof the fact that if is a multiple of 11, then is a multiple of 11.

Below is a proof by contradiction that there is no largest multiple of 7.

Line 1:	Assume there is a number, S, say, that is the largest multiple of 7.
Line 2:
Line 3:	Consider the number .
Line 4:
Line 5:
Line 6:	So  is a multiple of 7.
Line 7:	This is a contradiction to the assumption that S is the largest multiple of 7.
Line 8:	Therefore, there is no largest multiple of 7.

The proof contains two omissions in its argument.

Identify both omissions and correct them.

If a positive integer greater than 1 is not a prime number, then it is called a composite number.  Prove by contradiction that any composite integer N has a prime factor less than or equal to .

Prove by contradiction that if  is odd, where is a positive integer, then must be odd.

Prove that the difference between two rational numbers is rational.

Prove by contradiction that there are an infinite number of prime numbers.

Prove by contradiction that , where  is a prime number, is an irrational number.  You may use without proof the fact that any positive integer may be written uniquely as a product of its prime factors.

Below is a proof by contradiction that  is irrational.

Line 1:	Assume is a rational number.  Therefore it can be written in the form , where a and b are integers, and .  As , we may assume as well that .
Line 2:
Line 3:
Line 4:
Line 5:	No power of 2 (all even) is equal to a power of 7 (all odd).
Line 6:	unless  but this is a contradiction of the original assumption.
Line 7:	is irrational

The proof contains one mathematical error and one logical error.

Identify both errors and correct them.

Prove by contradiction that the solutions to the equation    cannot be written in the form   where  and  are both odd integers.

Prove by contradiction that, if are rational numbers and  is a positive non-square integer, then

implies that and .  You may use without proof the fact that for any positive non-square integer ,  is irrational.