Associated Topics || Dr. Math Home || Search Dr. Math

### 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
factor.

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

- Doctor Peterson, The Math Forum
http://mathforum.org/dr.math/
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search