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.