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.

This entry was posted in The expert's corner by spiros. Bookmark the permalink.

About spiros

Spyridon Michalakis does research on quantum many-body physics and topological quantum order at Caltech's Institute for Quantum Information and Matter, where he is also the manager for outreach activities.

2 thoughts on “Redemption: Part I

  1. Pingback: One, two, three, four, five… | Quantum Frontiers

  2. Pingback: The million dollar conjecture you’ve never heard of… | Quantum Frontiers

Your thoughts here.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s