We love to talk about prime numbers and their various properties for GMAT preparation, but composite numbers usually aren’t mentioned. Composite numbers are often viewed as whatever is leftover after prime numbers are removed from a set of positive integers (except 1 because 1 is neither prime, nor composite), but it is important to understand how these numbers are made, what makes them special and what should come to mind when we read “composite numbers.”
Principle: Every composite number is made up of 2 or more prime numbers. The prime numbers could be the same or they could be distinct.
2*2 = 4 (Composite number)
2*3*11 = 66 (Composite number)
5*23 = 115 (Composite number)
and so on…
Look at any composite number. You will always be able to split it into 2 or more prime numbers (not necessarily distinct). For example:
72 = 2*2*2*3*3
140 = 2*2*5*7
166 = 2*83
and so on…
This principle does look quite simple and intuitive at first, but when tested, we could face problems because we don’t think much about it. Let’s look at it with the help of one of our 700+ level GMAT questions:
x is the smallest integer greater than 1000 that is not prime and that has only one factor in common with 30!. What is x?
(E) 50! + 1
If we start with the answer choices, the way we often do when dealing with prime/composite numbers, we will get stuck. If we were looking for a prime number, we would use the method of elimination – we would find factors of all other numbers and the number that was left over would be the prime number.
But in this question, we are instead looking for a composite number – a specific composite number – and some of the answer choices are probably prime. Try as we might, we will not find a factor for them, and by the time we realize that it is prime, we will have wasted a lot of precious time. Let’s start from the question stem, instead.
We need a composite number that has only one factor in common with 30!. Every positive integer will have 1 as a factor, as will 30!, hence the only factor our answer and 30! will have in common is 1.
30! = 1*2*3*…*28*29*30
30! is the product of all integers from 1 to 30, so all prime numbers less than 30 are factors of 30!.
To make a composite number which has no prime factor in common with 30!, we must use prime numbers greater than 30. The first prime number greater than 30 is 31.
(As an aside, note that if we were looking for the smallest number with no factor other than 1 in common with 31!, we would skip to 37. All integers between 31 and 37 are composite and hence, would have factors lying between 1 and 31. Similarly, if we were looking for the smallest number with no factor other than 1 in common with 50!, 53 would be the answer.)
Let’s get back to our question. If we want to make a composite number without using any primes until 30, we must use two or more prime numbers greater than 30, and the smallest prime greater than 30 is 31. If we use two 31’s to get the smallest composite number, we get 31*31 = 961 But 961 is not greater than 1000, so it cannot be our answer.
So, let’s find the next prime number after 31 – it is 37. Multiplying 31 and 37, we get 31*37 = 1147. This is the smallest composite number greater than 1000 with no prime factors in common with 30! – the only factor it has in common with 30! is 1. Therefore, our answer is (C).
Karishma, a Computer Engineer with a keen interest in alternative Mathematical approaches, has mentored students in the continents of Asia, Europe and North America. She teaches the GMAT for Veritas Prep and regularly participates in content development projects such as this blog!