# Redemption: Part II

Last week, a journey began to find the solution to a problem I could not solve as a seventeen year-old boy. That problem became an obsession of mine during the last days of the International Math Olympiad of 1997, the days when I also met the first girl I ever kissed. At the time, I did not have the heart to tell the girl that I had traveled across the Atlantic to compete with the best and brightest and had come up short. I told her that I had solved the problem, but that the page with my answer had been lost. I told my parents the same thing and to everyone at school who would ask me why I did not return with a medal from the Math Olympics. The lie became so powerful that I did not look at that problem again until now. So, you may be wondering why a blog about Quantum Information Science at Caltech includes posts on problems from Math Olympiads. And why I would open the book on the page with that one problem after fifteen years…

When I was in grad school, I spent 4 hours listening to a student who was struggling with a math class because he was uncomfortable with very small numbers (micronumerophobia). Together, we addressed his anxiety and he went on to become one of the top students in the class. In other words, don’t count on me letting go until you get to your Eureka! moment, even if your biggest obstacle is of the I-am-not-smart-enough variety. With time, this feeling will pass and will be replaced by a vibrant clarity of mind. Now, before going any further, go back and read Redemption: Part I. You will see how natural numbers, which encode the universal language of mathematics, are like molecules that are made up of atomic elements (prime numbers) on the periodic table. You will also learn about relatively prime numbers, which correspond to molecules that share no common elements, like $H_2 O$ (water) and $NaCl$ (salt). Finally, you will meet the greatest common divisor, a number whose importance you have to witness in action to appreciate.

Redemption rebooted…

The challenge: Find all pairs of positive integers $a,b \ge 1$, such that $a^{b^2} = b^a.$

The biggest progress we made so far in solving this problem came from extracting in Part I the greatest common divisor (gcd) from the numbers $a,b$ in the above equation. The new equation became:

$d^{b^2-a} a_1^{b^2} = b_1^a,$

where $d=gcd(a,b)$ and the numbers $a_1 = a/d, \, b_1=b/d$ are relatively prime (i.e. strangers in the night). Looking at the above equation, we decided to break it into three cases (because if the power to which $d$ is raised is negative, the equation must be turned on its head to avoid equating apples to oranges – whole numbers on one side with fractions on the other side):

1. $b^2 > a,$
2. $b^2 = a,$ and
3. $b^2 < a.$

Case 1 was considered already in Part I and led to the equation: $b_1 = d^{db_1^2-1}$. Now we try different values for $d$ and see what we get. Starting with $d=1$, we have $b_1 = 1$ (since 1 raised to any power is always 1). And this is precisely the case which yields the solution we already knew: $a=1,b=1$. Or is it? Remember clarity of mind? Which case are we considering again? Case 1: $b^2 > a$. In other words, $1^2 > 1$ in this case, so we get a contradiction and $d$ cannot be 1. So we keep going: $d \ge 2$ yields $b_1 = d^{db_1^2-1} \ge 2^{2b_1^2-1},$ and squaring both sides gives: $b_1^2 \ge 2^{2(2b_1^2-1)}$, which becomes $(2b_1)^2 \ge 2^{(2b_1)^2}$ after a quick rearrangement (ask me how in the comments). And we have reached a very important milestone in your journey: The day you learn about mathematical induction.

Mathematical induction is so important, that I will not even give you the definition here. I will illustrate it by showing you that the inequality $(2b_1)^2 \ge 2^{(2b_1)^2}$ has no solutions in the natural numbers $b_1 \ge 1$. That’s right. In two lines, I will prove to you that no value of $b_1$ (and there are infinite of them to consider) satisfies both sides of this inequality. We will prove that the inequality should be reversed from $(2b_1)^2 \ge 2^{(2b_1)^2}$ to $(2b_1)^2 < 2^{(2b_1)^2}$:

1. Test the simplest case: $b_1=1$ yields $2^2 < 2^{(2^2)} = 16$. Check.
2. Set $s=(2b_1)^2$ and check that $s+1 < 2^{s+1}$ whenever $s < 2^s$: $s+1 < 2^s + 1 \le 2^s + 2^s = 2^{s+1}$, where I used $2^s \ge 1$, for all $s \ge 0$.
3. BAM!

What kind of sorcery is this?!? Well, let’s play it back in slow motion… First, we do a sanity check in Step 1, to make sure we are not about to prove the wrong thing! This is called the base case, which obviously refers to the foundation upon which we will build the rest of our argument. Next comes magic. And like all great magic tricks, the sense of wonder only increases once the truth is revealed. And the trick is simple: If you can show that your guess works for the number $s+1$, assuming that it works for the number $s$, then you are done. Because $s+2$ is to $s+1$, as $s+1$ is to $s$. Good stuff, right? Right. So, back to the one-liner above: $s < 2^s$ implies $s+1 < 2^s+1$ (just add one on both sides) and $2^s \ge 1$, for all positive exponents $s$ (check out this Khan Academy video on exponents). The rest follows from $2^s+1 \le 2^s+2^s = 2^1\cdot 2^s = 2^{1+s}$ (again, check out the video on exponent rules). That line of inequalities we just saw is the famous inductive step (up there with the dubstep) and the assumption we made (the guess) that $s < 2^s$ (for some fixed number $s$) is the equally famous inductive hypothesis (if you haven’t heard of it, it’s because we run in different circles).

But words are like leaves, and where they most abound, much fruit of sense beneath is rarely found.

So forget about inductive steps and hypotheses and remember only the feeling of satisfaction from realizing that in two lines, we showed that Case 1 is a dud. No numbers $a,b \ge 1$ can satisfy both $b^2 > a$ and $a^{b^2} = b^a$. And let’s be honest; Case 2 is looking pretty easy. If $b^2=a$, then the exponent of $d$ is 0 and the equation $d^{b^2-a} a_1^{b^2} = b_1^a$ reduces to $a_1^{b^2} = b_1^a$. But the numbers $a_1, b_1$ are relatively prime (and as we proved in Part I, so are their powers). Now, how can it be that two molecules with no common atomic elements can be equal? It can’t be! Unless $a_1 = b_1 = 1$, which yields $a=b=d$. Is this consistent with $b^2=a$? Yes, as long as $d^2=d$, which implies $d=1$ (since $d\ge 1$). Finally, we have a solution: $a=b=1$! The obvious solution we already knew about… But in the process, you learned about mathematical induction. And this is up there with learning how to add two numbers.

Life-changing stuff.

What about Case 3: $b^2 < a$? All you need to know, you have already been taught in these two parts. So, you’ve got to ask yourself one question: Do I feel lucky? Well, do ya?

## 5 thoughts on “Redemption: Part II”

1. Thanks for the incredibly ‘open’ post. Especially the part about lying to the girl and your peers — it takes guts to admit something like that.

As a reference for curious aspiring mathematicians reading this post, I originally learned about induction, the pigeon-hole principle, invariants and other problem solving tricks from Loren C. Larson’s “Problem Solving Through Problems.” It’s a fantastic book that I couldn’t recommend more highly.

2. I liked this post. After some work, I think I have a solution to $a^(b^n) =b^a$ for integer n. I will post it or reply by email if you wish. Jim Graber

• Dear James, please post your answer below! You may use $latex … for equations in tex. If you need a reference, Google “latex wordpress”. • Sorry to be so late in responding.$a^(b^n) = b^a$for n an integer, although it may not be necessary for n to be an integer. Solution is:$a=b^bb = n+1$Examples:$4^2=2^4(27^ (3^2)) = 27^9=3^27(256 ^(4^3)) = 256^64 = 4^256\$
etc.

3. Both sides of the equation equal (n+1)^((n+1)^(n+1)).