AMC 12 Mock Exam 2 Problem 20

Since $a,b\ge2$, $\log_ab>0$. If $\log_ab=\frac pq$ in lowest terms, then $a^p=b^q$. Comparing prime factorizations, every exponent in $a$ is a multiple of $q$ and every exponent in $b$ is a multiple of $p$, so $a=c^q$ and $b=c^p$ for some integer $c\ge2$. Conversely, if $a=c^m$ and $b=c^n$ then $\log_ab=\frac nm$ is rational.

Call $c\ge2$ primitive if it is not a perfect power. Every integer $\ge2$ is a power of exactly one primitive number, and $a,b$ have rational $\log_ab$ exactly when they are powers of the same primitive $c$. If $c$ has $k_c$ powers in $[2,100]$, it contributes $k_c^2$ ordered pairs.

• $c=2$: $2,4,8,16,32,64$ ($k=6$); $c=3$: $3,9,27,81$ ($k=4$); $c=5,6,7,10$: $k=2$ each.
• The perfect powers in $[2,100]$ are $4,8,9,16,25,27,32,36,49,64,81,100$ (twelve numbers), so there are $99-12=87$ primitive numbers. Apart from the six listed above, the other $81$ have $k=1$.

The total is $36+16+4\cdot4+81=\boxed{149}$.