Q: Understanding Answer of 2012 AMC 8 - #18

1k Views Asked by At

The problem is: "What is the smallest positive integer that is neither prime nor square and that has no prime factor less than 50?".

The solution for this problem goes like this: "Since the integer is neither prime nor square, it is divisible either by two distinct primes or by the cube of a prime. The smallest prime numbers not less than 50 are 53 and 59. Since 53×59 = 3127 < 53^3, the smallest number satisfying this description is 3127."

Is there a theorem or property that justifies the first statement: "Since the integer is neither prime nor square, it is divisible either by two distinct primes or by the cube of a prime"?

1

There are 1 best solutions below

0
On BEST ANSWER

Well, it has at least two prime factors (counting multiplicity) because it's not prime. If they're distinct, you're done, if not then you have the square of a prime, but it's not a square, so you must either have

a) another prime factor not equal to the square, in which case that number times one copy of the prime would produce a smaller number (contradiction)

or

b) the same factor, hence a cube of a prime (any more factors would be larger, which would give rise to another contradiction to smallest)