Integer Root Checking

Date: 02/18/2003 at 01:01:19
From: Killian
Subject: Check if a number has roots that are whole numbers

Is there a quick way to check whether a number has any roots that are 
whole numbers?

For example, 256 has a square root 16, 4th root 4 and 8th root 2. All 
of those are whole numbers. How would I be able to quickly check any 
number to find any/all the different whole roots that it may have?

I'm making a computer program to calculate and store all the whole 
roots of every number up to a certain point (the limit is processing 
power).

Date: 02/18/2003 at 09:10:07
From: Doctor Peterson
Subject: Re: Check if a number has roots that are whole numbers

Hi, Killian.

Interesting question!

To find all whole roots of a given number, you have to find the prime 
factorization of the number, and take the greatest common divisor of 
the exponents. This will give the greatest power that is a root of 
your number; and any divisor of this exponent will determine an 
additional root. That's hard to say clearly, so I'll give an example. 
Say our number is

    129600 = 2^6 * 3^4 * 5^2

The GCD of 6, 4, and 2 is 2, so we can write this number as a square:

    129600 = (2^3 * 3^2 * 5)^2 = 360^2

Since 2 is a prime, we can't take any further roots.

For another example, take

    64 = 2^6

Since we just have one prime, the GCD is 6 itself, and of course we 
have already written 64 as a 6th power. But 6 can be factored, and we 
can write 64 as each of those powers (2, 3, 6):

    64 = (2^1)^6 = 2^6

    64 = (2^2)^3 = 4^3

    64 = (2^3)^2 = 8^2

For your computer program, since you want to do this for every number 
within some range, it will probably be much more efficient to reverse 
the process: for each root (that is, each whole number up to a limit), 
find all of its powers and store the fact that each of those powers 
has this root. This is similar to the sieve of Eratosthenes (discussed 
in our FAQ on prime numbers), which finds primes not by testing all 
numbers for primality, but by finding all products of each possible 
factor.

If you have any further questions, feel free to write back.

- Doctor Peterson, The Math Forum
  http://mathforum.org/dr.math/