SMC 2013 Q16
16. Andrew states that every composite number of the form \(8n + 3\), where \(n\) is an integer, has a prime factor of the same form. Which of these numbers is an example showing that Andrew's statement is false?
- A 19
- B 33
- C 85
- D 91
- E 99
Senior Mathematical Challenge 2013, Question 16. © UK Mathematics Trust. Original paper on ukmt.org.uk
Answer: D 91
By the Fundamental Theorem of Arithmetic, every positive integer greater than 1 is either prime or a product of two or more primes. A number that is the product of two or more primes is called a composite number.
We are looking to choose, from the options provided, a composite number which is of the form \(8n + 3\) but does not have a prime factor of the form \(8n + 3\).
Option A is prime, so is not possible. Options B and C are not of the form \(8n + 3\).
Option E is \(8 \times 12 + 3 = 99\). The number 99, when expressed as a product of its prime factors, is \(3 \times 3 \times 11\) and the factor 11 is of the required form as \(11 = 8 \times 1 + 3\).
However, option D is of the form \(8n + 3\) as \(8 \times 11 + 3 = 91\) but neither of the prime factors of 91, which are 7 and 13, are of the form \(8n + 3\).
Solution © UK Mathematics Trust, from the SMC 2013 solutions. Longer versions with investigations: Solutions and investigations (PDF).