Redemption: Part I

Back in my last post, I closed with a problem (The Redeemer) from the International Math Olympiad of 1997. Unlike the problem I posted from 1981 (Elementary, my dear Watson), I was actually walking by the time I met The Redeemer. In fact, I was in Mar del Plata, a beautiful seaside beach resort in Argentina, participating in the 38th International Math Olympiad. The Redeemer was Problem 5. I remember clearly the moment I saw it. It looked so simple, so innocent: Find all pairs of positive integers $a,b \ge 1$ , such that $a^{(b^2)} = b^a.$

I had to solve it. But little did I know…

The redemption begins: The first thing you see is that $a=1,b=1$ is a solution. You look at the equation for a bit longer and you start trying out other numbers. Like $a =2$ and $b=\ldots$ (hmm, what is $b?$ ). You are stuck. Because you know that even if you get lucky and you find another pair of numbers that works, you are just guessing! Who knows how many more pairs there are?

Because “Deliverance” sounds too dramatic.

And then something amazing happens: You realize that in order for two objects to be equal (and I mean any two objects in the multiverse, not just numbers in a math exam on July 25th, 1997), the components that make up the two objects must also be equal. So, what is a common component of two numbers? The one you learned about in high school is the greatest common divisor (gcd). What is $gcd(a,b)?$ It is exactly what the name suggests: The largest whole number (integer) that divides both $a$ and $b$ . For example, if $a=12$ and $b=21$ , then $gcd(a,b)=3$ . But, if $a=12$ and $b=25$ , then $gcd(a,b)=1$ , since $12=2\times 2\times 3$ and $25=5\times 5$ have no common divisors.

In fact, two numbers with no common divisor (apart from the number 1 that divides everything) are called relatively prime. So, 12 and 25 are relatively prime, though neither of the two numbers is a prime number (a number with exactly two divisors: itself and 1). I just wanted to clarify this, in case you were wondering. Of course, if two distinct numbers are prime (the number 1 is not a prime number), then they are also relatively prime. Here is a short proof: Let $a$ and $b$ be two different prime numbers. Then the divisors of $a$ are $1$ and $a$ , while the divisors of $b$ are $1$ and $b$ . Since $a\neq b$ , the only common divisor of $a$ and $b$ is 1, which is the definition of relatively prime numbers. So, to recap, two relatively prime numbers have no common divisor apart from 1, but relatively prime numbers don’t have to be prime numbers. Now for the most important part:

Lemma 1: For any two numbers $a,b$ , the numbers $a_1=a/gcd(a,b)$ and $b_1=b/gcd(a,b)$ are relatively prime.

The proof of the above statement is simpler than you think. But, let’s see an example first: Take $a=12$ and $b=21$ . Then, $a_1 = 12/3=4$ and $b_1=21/3=7$ . The numbers 4 and 7 are relatively prime. OK, back to the proof (by contradiction): Assume that the two numbers are not relatively prime. Then, there is a common divisor $d_1$ of $a_1,b_1$ that is greater than 1. Guess what… you have a contradiction. Why? Because you have found a number greater than $gcd(a,b)$ which divides both $a$ and $b$ . What is that number? It is $d_1\cdot gcd(a,b)$ . Booyah.

But wait, there is more!

Lemma 2: If $a,b$ are relatively prime numbers and $N$ is a number greater than $1$ , then the equation $N\cdot a = b$ implies that $a=1, b=N.$

Again, the proof is simple. Clearly $a$ is smaller than $b$ since $N >1$ and it is a divisor of $b$ (obviously, from the equation). But, $a$ is also the largest divisor of itself, so $gcd(a,b)=a$ . This completes the proof, since $gcd(a,b)=1$ , by assumption. Don’t you just love math…

Back to solving The Redeemer…

Let $d=gcd(a,b)$ and write $a=d\cdot a_1, b=d\cdot b_1$ . We can rewrite the equation $a^{(b^2)}=b^a$ as $d^{(b^2)}\cdot a_1^{(b^2)} = d^{a}\cdot b_1^{a}$ , which implies $d^{(b^2-a)}\cdot a_1^{(b^2)} = b_1^{a}$ (after dividing both sides by $d^a$ ). Believe it or not, we have made amazing progress towards the solution already. Recall that $a_1$ and $b_1$ are relatively prime (by Lemma 1). If $b^2 > a$ , then Lemma 2 and $d^{b^2-a}\cdot a_1^{b^2} = b_1^{a}$ implies $a_1 = 1$ and $b_1^a=d^{b^2-a}$ . I know what you are thinking right about now (actually, I don’t know, but it sounds cool): Why can we use Lemma 2 with powers of relatively prime numbers? Because powers of relatively prime numbers are also relatively prime numbers.

Lemma 3: Let $a,b$ be relatively prime numbers. Then, for any $m,n \ge 1$ the numbers $a^m,b^n$ are also relatively prime.

This is so obvious that it is almost impossible to prove! But the whole point of mathematical reasoning is to break down concepts into self-evident elementary truths. And this is what we need to do here. So, we write the prime number decomposition of $a,b:$ $a= p_1^{k_1}\cdot p_2^{k_2} \cdots p_s^{k_s}$ and $b= q_1^{l_1}\cdot q_2^{l_2} \cdots q_t^{l_t}$ – Hello Fundamental Theorem of Arithmetic. Thank you for the unique prime factorization of all numbers! (Can you see now why 1 is not allowed to be a prime number?) – OK, now what? Well, if $a,b$ are relatively prime numbers, can any of the prime factors of $a$ (say $p_1$ ), be equal to a prime factor of $b$ (say $q_3$ )? No! Otherwise, that prime would be a common divisor of $a,b$ and $gcd(a,b) \neq 1$ , a contradiction! So, $a^m = p_1^{m \cdot k_1}\cdot p_2^{m\cdot k_2} \cdots p_s^{m\cdot k_s}$ has no common factors with $b^n= q_1^{n\cdot l_1}\cdot q_2^{n \cdot l_2} \cdots q_t^{n \cdot l_t},$ either (the two numbers still have totally different prime factors; only the exponents changed). Tada!

To recap, we have the equation $d^{b^2-a}\cdot a_1^{b^2} = b_1^a$ and we are exploring the case $b^2 > a$ , which implies $a=d$ and $b_1 = d^{(d^2\cdot b_1^2 - d)/d} = d^{d\cdot b_1^2 - 1}$ . But, it is time to get up and stretch our legs. You have already learned so much! Go ahead, I will be back with Part II next week. Redemption takes time.