Math Olympiads #1

I’ve been obsessed with Math Olympiads and other kinds of competitive math for a loong time now. Although I should be doing more serious mathematics now that can actually get me a job, I shall ignore good sense and start my series of posts on Math Olympiad problems!

The first problem that I want to write about is a relatively easy one from IMO (International Math Olympiad) 1974. I think it was a long-listed problem, and didn’t actually make it to the test. It asks to prove the fact that

\displaystyle 343|2^{147}-1

(that 343 divides 2^{147}-1)

The important thing in this problem is to figure out that 343=7^3 and 147=3.7^2. Hence, we’re being asked to prove that 7^3|2^{3.7^2}-1.

We have the following theorem for reference: If a and b are co-prime, then a^{\phi(b)}\equiv 1\pmod b, where \phi(b) is the number of natural numbers that are co-prime with b. Fermat’s Little Theorem is a special case of this.

Now on to the calculations and number crunching. We have fleshed out the main idea that we’ll use to attack the problem. We can see that \phi(7^3)=7^3-7^3/7=6.7^2. Hence, as 2 is co-prime with 7^3, 2^{6.7^2}-1\equiv 0\pmod {7^3}. We can factorize this as (2^{3.7^2}+1)(2^{3.7^2}-1)\equiv 0\pmod {7^3}. Now we have to prove that 7^3 does not have any factors in common with 2^{3.7^2}+1. As 2^3\equiv 1\pmod 7, 2^{3.7^2}\equiv 1\pmod 7 too. Hence, 2^{3.7^2}+1\equiv 2\pmod 7. This shows that 2^{3.7^2}+1 does not have any factors in common with 7^3, and leads us to conclude that 7^3|(2^{3.7^2}-1), or 343|2^{147}-1. Hence proved.

I realize that the formatting is pretty spotty. I shall try and re-edit this in the near future to make it more readable.