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
(that divides
)
The important thing in this problem is to figure out that and
. Hence, we’re being asked to prove that
.
We have the following theorem for reference: If and
are co-prime, then
, where
is the number of natural numbers that are co-prime with
. 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 . Hence, as
is co-prime with
,
. We can factorize this as
. Now we have to prove that
does not have any factors in common with
. As
,
too. Hence,
. This shows that
does not have any factors in common with
, and leads us to conclude that
, or
. 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.