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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.