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.