Worked question 9 - Pure: Proof
Answer and mark scheme
Question 9
| Credit | Answer or working |
|---|---|
| B1 | (a) states, for contradiction, that there are only finitely many primes, p1, p2, ..., pk, and that this is a complete list of every prime, oe |
| B1 | (b) states that each pi divides the product p1 x p2 x ... x pk exactly, so N leaves remainder 1 when divided by any pi, oe |
| B1 | (b) states that this holds for every i from 1 to k, so no prime in the list divides N, cso |
| B1 | (c) states that N>1, so N must have at least one prime factor, since every integer greater than 1 has a prime factor |
| B1 | (c) states that this prime factor cannot be any of p1, ..., pk (by part (b)), so it is a prime missing from the original list, contradicting the assumption that the list was complete, cso, ft |
| B1 | (d) states that the assumption of finitely many primes is false, so there are infinitely many primes, cso, ft |
| M1 | (e) calculates N=2x3x5+1=31 |
| A1 | (e) verifies 31 is not divisible by 2, 3 or 5 (e.g. remainder 1 in each case) |
| A1 | (e) identifies that 31 is itself prime, a prime not in the original list {2, 3, 5}, cao |
| B1 | (f) calculates N=2x3x5x7x11x13+1=30031, and notes 30031=59x509 is composite |
| B1 | (f) states that neither 59 nor 509 is in the original list {2,3,5,7,11,13}, so N still has a prime factor missing from the list, confirming the argument holds whether or not N is prime, cso |
- (a) Answer: Assume there is a complete finite list of primes p1, p2, ..., pk
- (b) Answer: N leaves remainder 1 on division by each pi, so no pi divides N
- (c) Answer: N has a prime factor not in the original list, contradicting completeness of the list
- (d) Answer: There are infinitely many primes
- (e) Answer: N=31, which is prime and not in {2, 3, 5}
- (f) Answer: N=30031=59x509; both 59 and 509 are new primes not in the original list







