Properties of Exponentiation

Question

I am a Computer Programmer and this Question might be too trivial to true practitioners of pure Mathematics.

I recently came across a programming puzzle (Project Euler #29). I have to find out the distinct numbers formed by the expression a^b when 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100.

I know that the maximum possible is less than 99 X 99 = 9801.

So I tried to count the Numbers which are equal, for example 2⁴ = 4² and subtract this count from 9801.

So my question is under what circumstances a^b = c^d ? Provided a ≠ c and b ≠ d.

I used the following check, c MOD a = 0 and b MOD d = 0. But I got incorrect results.
Then I checked if c = a^m and b = dⁿ, for m ≥ 1 and n ≥ 1. This again proved an insufficient check as numbers like 2⁴ and 4⁴ where found equal.

More over I can not find the actual values of a^b as it requires calculating numbers as large as 100¹⁰⁰ (Not in a Mathematical way, I mean Programming wise because no data type might be large enough to hold such results). So what I require is to check whether a^b = c^d without calculating either a^b or c^d. Is it possible? If possible what are the checking criteria?

If there are some problems with the question format please post a comment I will update the Question.

Any help will be highly appreciated. Thanks in Advance.

Answer 1

If you factor out $a^b$ into prime powers $p_1^{k1}p_2^{k2}...p_n^{kn}$ this would mean that b devides all $k_i$.
So for every divisor $d$ such that $d$ devides all $k_i$
$$c = p_1^{\frac{k1}{t}}p_2^{\frac{k2}{t}}...p_n^{\frac{kn}{t}} \in \mathbb{Z}$$ To this algorithmically you shold compute factor out $a^b$ find the GCD(k1,k2,...,kn)(greatest common devisor) = G. Then for every possible devisor of G there exist such numbers. You might want to look at algorithms how to find the GCD and the number of possible devisors of a number.