Redemption: Part I

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 $latex gcd(a,b)?$ It is exactly what the name suggests: The largest whole number (integer) that divides both $latex a$ and $latex b$. For example, if $latex a=12$ and $latex b=21$, then $latex gcd(a,b)=3$. But, if $latex a=12$ and $latex b=25$, then $latex gcd(a,b)=1$, since $latex 12=2times 2times 3$ and $latex 25=5times 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 $latex a$ and $latex b$ be two different prime numbers. Then the divisors of $latex a$ are $latex 1$ and $latex a$, while the divisors of $latex b$ are $latex 1$ and $latex b$. Since $latex aneq b$, the only common divisor of $latex a$ and $latex 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 $latex a,b$, the numbers $latex a_1=a/gcd(a,b)$ and $latex 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 $latex a=12$ and $latex b=21$. Then, $latex a_1 = 12/3=4$ and $latex 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 $latex d_1$ of $latex a_1,b_1$ that is greater than 1. Guess what… you have a contradiction. Why? Because you have found a number greater than $latex gcd(a,b)$ which divides both $latex a$ and $latex b$. What is that number? It is $latex d_1cdot gcd(a,b)$. Booyah.

But wait, there is more!

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

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

Back to solving The Redeemer…

Let $latex d=gcd(a,b)$ and write $latex a=dcdot a_1, b=dcdot b_1$. We can rewrite the equation $latex a^{(b^2)}=b^a$ as $latex d^{(b^2)}cdot a_1^{(b^2)} = d^{a}cdot b_1^{a}$, which implies $latex d^{(b^2-a)}cdot a_1^{(b^2)} = b_1^{a}$ (after dividing both sides by $latex d^a$). Believe it or not, we have made amazing progress towards the solution already. Recall that $latex a_1$ and $latex b_1$ are relatively prime (by Lemma 1). If $latex b^2 > a$, then Lemma 2 and $latex d^{b^2-a}cdot a_1^{b^2} = b_1^{a}$ implies $latex a_1 = 1$ and $latex 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 $latex a,b$ be relatively prime numbers. Then, for any $latex m,n ge 1$ the numbers $latex 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 $latex a,b:$ $latex a= p_1^{k_1}cdot p_2^{k_2} cdots p_s^{k_s}$ and $latex 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 $latex a,b$ are relatively prime numbers, can any of the prime factors of $latex a$ (say $latex p_1$), be equal to a prime factor of $latex b$ (say $latex q_3$)? No! Otherwise, that prime would be a common divisor of $latex a,b$ and $latex gcd(a,b) neq 1$, a contradiction! So, $latex a^m = p_1^{m cdot k_1}cdot p_2^{mcdot k_2} cdots p_s^{mcdot k_s}$ has no common factors with $latex b^n= q_1^{ncdot 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 $latex d^{b^2-a}cdot a_1^{b^2} = b_1^a$ and we are exploring the case $latex b^2 > a$, which implies $latex a=d$ and $latex b_1 = d^{(d^2cdot b_1^2 – d)/d} = d^{dcdot 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.