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 , such that
I had to solve it. But little did I know…
The redemption begins: The first thing you see is that is a solution. You look at the equation for a bit longer and you start trying out other numbers. Like and (hmm, what is ). 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?
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 It is exactly what the name suggests: The largest whole number (integer) that divides both and . For example, if and , then . But, if and , then , since and 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 and be two different prime numbers. Then the divisors of are and , while the divisors of are and . Since , the only common divisor of and 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 , the numbers and are relatively prime.
The proof of the above statement is simpler than you think. But, let’s see an example first: Take and . Then, and . 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 of that is greater than 1. Guess what… you have a contradiction. Why? Because you have found a number greater than which divides both and . What is that number? It is . Booyah.
But wait, there is more!
Lemma 2: If are relatively prime numbers and is a number greater than , then the equation implies that
Again, the proof is simple. Clearly is smaller than since and it is a divisor of (obviously, from the equation). But, is also the largest divisor of itself, so . This completes the proof, since , by assumption. Don’t you just love math…
Back to solving The Redeemer…
Let and write . We can rewrite the equation as , which implies (after dividing both sides by ). Believe it or not, we have made amazing progress towards the solution already. Recall that and are relatively prime (by Lemma 1). If , then Lemma 2 and implies and . 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 be relatively prime numbers. Then, for any the numbers 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 and – 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 are relatively prime numbers, can any of the prime factors of (say ), be equal to a prime factor of (say )? No! Otherwise, that prime would be a common divisor of and , a contradiction! So, has no common factors with either (the two numbers still have totally different prime factors; only the exponents changed). Tada!
To recap, we have the equation and we are exploring the case , which implies and . 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.
Pingback: One, two, three, four, five… | Quantum Frontiers
Pingback: The million dollar conjecture you’ve never heard of… | Quantum Frontiers