IMO phase II training Homework Solution

Here is my solution to the following problem given in IMO phase II training for the basic group:

Problem(1): Find all positive integer solutions to:

Pigeonhole Principle (1)

When you place three apples into two boxes, then one of the boxes must contain at least two apples. You may say that this is trivial. Indeed, it is a very simple observation and it is perhaps the simplest form of what is called the “Pigeonhole Principle.”

There are many ways to state the Pigeonhole Principle. One of the easiest ways is the following:

When you place balls into boxes, one of the boxes must contain at least two balls.

I remember I first learn the Pigeonhole principle in

Diophatine Equation (1)

The following is a classical problem, which seems to be unknown to a lot of students, including the ones in the advanced IMO training session.

Prove that has no integer solutions.

Proof: First consider the parity of . If is even then we have , which is absurd. Hence is odd.

If , then , which is absurd and thus

Now write the equation as: Since There exists a prime and divides This implies and this has no solution since is a square mod iff Therefore the original equation has no solution in integers.

IMO 2008 Problem 3

Prove that there are infinitely many positive integers  such that  has a prime divisor greater than

Many of you probably knew the elementary solution already. If not, it is included in the appendix. 

I want to discuss about the problem and tell you some of the major theorems related to the problem. 

Conjecture: There are infinitely many such that is a prime number. 

Theorem (Iwaniec): There are infinitely many such that is either a prime or a product of two primes. 

Reference: 

H. Iwaniec, “Almost-primes represented by quadratic polynomials,” Inventiones Mathematicae, 47 (1978), 171-188. 

While this theorem is the closest thing to the conjecture, it doesn’t help with the IMO problem at all. The most it can say is that there are infinitely many such that the largest prime divisor of is at least  

Here are two theorems, that would “second-kill” the problem. 

Theorem (Deshouillers, Iwaniec) There exist infinitely many integers  such that the greatest prime factor of  is at least

Reference: 

Deshouillers, Iwaniec, “On the greatest prime factor of “. Annales de l’institut Fourier, 32 no. 4 (1982), p. 1-11

Knowing this, this IMO problem is a piece of cake. Hopefully, knowing this would help the contestants with the forth coming IMOs. 

Appendix: Here is a sketch of elementary proof of the problem. Using your favorite method, argue that we may take . (using Iwaniec’s theorem for example…though this is kind of over killing) Since , we may also assume Write .  Since divides  . This implies Hence we have , which implies We thus have . By choosing a sufficiently big ,  we have , and hence , which implies and we are done. 

Challenge: Imporve the bound in the theorem of Deshouillersand Iwaniec. (this is really a real challenge…)

Coming up: My teaching philosophy. 

 

Sum of Squares (1)

It is a well known theorem by Fermat that any prime of the form can be written as a sum of two squares. 

One question is, in how many ways can we write a prime of the form into sum of two squares? 

More generally, given an integer .  In how many ways can we write as a sum of two squares? 

Perhaps I will let the reader to think for a momenrt, I will discuss more of this tomorrow.

Leibniz’s identity and beyond (1)

We start with the following well-known identity:

Let’s give a proof of this identity:

Note that we may rewrite the series as:

Next, we switch the order of integration and summation: [For those of you who do not know why we can do that, you will learn it later]

This last integral equals: which finishes the proof.

Consider a similar sum:

To compute the sum, we may proceed similarly as before, which yields:

This last integral can be computed by completing squares and trigonometric substitutions. We get the sum S equals [The last few equalities would be excellent exercises for those students preparing for HKCEE.]

Hm…notice that mysterious number shows up again… one might wonder, does shows up ALL the time?  The answer is no, because we have the following:

[Note that this is the natural log, i.e. log base e.]

The nest question would be, why does show up, and why?

The problem turns out to be ultimately related to number theory via something called the Dirichlet’s L-function, and we shall talk about it more in a later post.

Exercise: Prove that

HKIMO 2009 Selection Test 1 problem 2

Here is the problem:

Solve the following system of equations mod 37:

At a glance, this really looks like a nasty set of equations. One can solve it using a case by case analysis. For example, consider the cases b = 0 and b not congruent to 0 respectively.

However, here is the motivation of the problem, the system of equations is really the following equation:

where

The extra condition, says that is invertible. Therefore, we may multiply on both sides to get , the identity matrix. This yields is the unique answer.

Challenge: Try to answer the same question without the assumption (i.e. simply remove this equation from the system of equations.)

Hong Kong Selection Test 1 Problem 6 for IMO 2009

The following question appeared in the selection test 1 for IMO 2009:

For the equation:

Show that the equation is solvable mod p for all primes p < 100.

Before answering the question, let’s discuss how did I come up with this question. The numbers 3 and 37 are completely artificial. I chose the number 11 to eliminate the possibility that there could be a trivial or simple-to-fine “global” solution. (i.e. an integer solution to the equation)

I had the mindset to kill the people who like to brute force. I chose the number 100 because there was vaguely a “false hope” for brute force to work. (after all, there are “only” 25 primes to check.) However, the brute-force-group should ran into trouble after a while (i.e. after the first 10 primes or so…I mean, compute the 37th power of a number mod a prime p is really not that easy.)

Anyways, so what is the key to this problem?

The key to this problem is the so called “qth power lemma” in my number theory notes. Let me first state the theorem:

Theorem (qth power lemma)
Suppose p and q are primes. The map:

is an automorphism if

Of course, this theorem is phrased in a group theorectic language. In elementary terms, it simply means that everything is a th power mod if

Proof: Suppose Then there exists integers such that

Therefore, by Fermat’s little theorem.  Hence is a th power and we are done.

Now using this theorem, we can solve the problem in a few lines.

Solution: If or , then the cubing lemma and the 37th power lemma says the equation is solvable since everything is either a cube or a 37th power. Therefore, we only need to check primes p that are congruent to 1 mod 3 and 37. i.e. However, there is no such prime less than 100. We are done.

Remark 1: the converse of qth power lemma is also true. Interested reader should try to prove it yourself.

Remark 2: one can replace the number 11 by any integer and the result is still true.