# Problem of the Day

Which of the following integers cannot be expressed as the product of two distinct prime numbers?

A. 29,966
B. 34,571
C. 56,124
D. 67,994
E. 82,919

C. 56,124

See the Solution

### Solution

Note that 56,124 must be divisible by 4. Every multiple of 100 is divisible by 4, and 56,100 is a multiple of 100 (561*100). 4 also divides 24 evenly, so 4 must divide 56,100+24, which is just 56,124.

However, no number that is divisible by 4 could possibly be the product of two distinct prime numbers. The reason stems from the fact that 2 is the only even prime number.

If you don’t see the connection, think about it for a while, and then consider the following:

When two numbers are multiplied together, the product contains all of the factors of the original numbers. For example, 9*4=36. 9=3*3 and 4=2*2. 36=2*2*3*3. The product of 4 and 9, 36, received its two factors of 2 from 4 and its two factors of 3 from 9.

When we say that a number is divisible by n, that is equivalent to saying that the number is a multiple of n, or that nÂ is a factor of the number. So, if a number is divisible by 4, it must contain 4 as a factor, which means it contains two factors of 2. However, there is no way that two distinct prime numbers could contribute two factors of 2. At most they could contribute one if 2 is one of the prime numbers. Thus, no number that is divisible by 4 can possibly be written as the product of two distinct primes.