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.