How to quickly identify perfect powers

Question

In a test I'll take there may be a question such as the following:

A perfect power is an integer that can be written as $a^b$, $a$ and $b$ being integers greater or equal to 2.

One of the following numbers is not a perfect power, which one is it?

• 125
• 216
• 1000
• 500
• 2500

The first three (125, 216, 1000) are simply primeNumber^something, but the last two aren't.

Keeping in mind that I can't use a calculator and should spend on average only 1 minute per question, I was wondering what's the best method I can use to resolve such questions or more difficult ones (where there are less obvious wrong solutions, such as 1000).

Answer 1

Note that if you know the powers of two, then you don't need to know the powers of four, eight, etc. Generally, you need to only learn/become acquainted with the powers of prime numbers.

Even then, the exponent is generally not even going to be very big - assuming that the numbers you're given are going to be not larger than a few thousand. It would probably be a good idea to just look at primes up to $\approx50$ and their first few powers.

It might also help to note that if you have an odd $a^2$, then $a$ is going to be odd as well. If $a^2$ is even, then $a$ is even. There are other such multiplicative/divisive tricks you can use for speed, but I think that if you're reasonably well acquainted with low primes and their powers, you should be okay.

Answer 2

You have done the first part: quickly eliminate which ones are not the answer. Since you know that the first three can be written as an integer to an integer power you can eliminate those and focus on 4 and 5. Now, from here perhaps a factor tree can point you in the right direction. Try quickly factoring 500 and if all factors are repeated more than once it is a perfect power. If not, you found your answer.

Answer 3

The best way would be to factor the integer. You already know this for the first three. You should have noticed that $125=5 \times 5 \times 5$ so $125=5^3$. This method is very easy when the number is a power of a prime.

Now what about when a number isn't a prime power? Take the number $2500$.

$$2500=2^2 5^4$$

We want this to be a single number raised to a single power. So notice that the power of $2$ is $2$. So we need all the other powers to be raised to the $2$ power. Then notice that $5^4=(5^2)^2=(25)^2$. So we could have written $2500$ as

$$2500=2^25^4=2^2(25)^2=(2 \times 25)^2=50^2$$

Therefore, in general factor the integer and look for the lowest power. You all the "factors" to be written to the same power, as above. You will notice that for the number $500$, you can't do this.

Answer 4

Once you are down to $500$ and $2500$, you can note that each has a factor of $10^2=2^25^2$ and no more factors of $2$. This tells you the power must be a square. Then you can just ask which of $5$ and $25$ is a square.

Answer 5

Hint: If $n=p_1^{k_1} ...p_i^{k_i}$ then you can prove that $n$ is a perfect power if and only if $k_1,..,k_i$ have a common divisor $ b >1$.

This is the same as asking $gcd(k_1,..,k_i) \neq 1$.