IMO « Mathematics in HKCEE, HKAL, and Beyond

Archive for the ‘IMO’ Category

For my IMO Students (Basic and Advanced)

十月 28, 2009

Here is good problem for my IMO students.

Given a real number $R > 0$ . Find the greatest area of triangle ABC with circum-radius $R.$

Posted in IMO, Pure Mathematics, Teaching | Leave a Comment »

IMO phase II training Homework Solution

九月 27, 2009

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: $x^3 - y^3 = xy + 61.$

Read the rest of this entry ?

Posted in IMO, Number Theory, Teaching | Leave a Comment »

Diophatine Equation (1)

十月 21, 2008

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 $y^2 = x^3 + 7$ has no integer solutions.

Proof: First consider the parity of $x$ . If $x$ is even then we have $y^2 \equiv 3 \pmod{4}$ , which is absurd. Hence $x$ is odd.

If $x \equiv 3 \pmod{4}$ , then $y^2 \equiv 2 \pmod{4}$ , which is absurd and thus $x \equiv 1 \pmod{4}.$

Now write the equation as: $y^2 + 1 = x^3 + 8 = (x + 2)(x^2 - 4x + 4).$ Since $x + 2 \equiv 3 \pmod{4}$ There exists a prime $p \equiv 3 \pmod{4}$ and $p$ divides $x + 2.$ This implies $y^2 + 1 \equiv 0 \pmod{p},$ and this has no solution since $-1$ is a square mod $p$ iff $p \equiv 1 \pmod{4}$ Therefore the original equation has no solution in integers.

Posted in IMO, Number Theory | Tagged Diophatine Equation | Leave a Comment »

IMO 2008 Problem 3

九月 5, 2008

Prove that there are infinitely many positive integers $n$ such that $n^2 + 1$ has a prime divisor greater than $2n + \sqrt{2n}.$

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

I want to discuss about the $n^2 + 1$ problem and tell you some of the major theorems related to the $n^2 + 1$ problem.

Conjecture: There are infinitely many $n$ such that $n^2 + 1$ is a prime number.

Theorem (Iwaniec): There are infinitely many $n$ such that $n^2 + 1$ 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 $n$ such that the largest prime divisor of $n^2 + 1$ is at least $n.$

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

Theorem (Deshouillers, Iwaniec) There exist infinitely many integers $n$ such that the greatest prime factor of $n^2 + 1$ is at least $n^{6/5}.$

Reference:

Deshouillers, Iwaniec, “On the greatest prime factor of $n^2+1$ “. 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 $p > n$ . (using Iwaniec’s theorem for example…though this is kind of over killing) Since $p \,| \, (p - n)^2 + 1$ , we may also assume $p > 2n.$ Write $p - 2n = k > 0$ . Since $p$ divides $n^2 + 4 = (p - k)^2 + 4$ . This implies $p \, | \, k^2 + 4.$ Hence we have $p \le k^2 + 4$ , which implies $k \ge \sqrt{p - 4}.$ We thus have $p > 2n + \sqrt{p - 4}$ . By choosing a sufficiently big $p$ , we have $\sqrt{p - 4} > 4$ , and hence $p > 2n + 4$ , which implies $\sqrt{p - 4} > \sqrt{2n}$ 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.

Posted in IMO, Number Theory | Leave a Comment »

CGMO 2007 Problem 7 and Liouville’s theorem

九月 3, 2008

Let $a, b, c \in \mathbb{Z}$ such that $|a|, |b|, |c| \le 10.$

Let $f(x) = x^3 + ax^2 + bx + c.$

Suppose $|f(2 + \sqrt{3})| < 10^{-4}.$ Prove that $f(2 + \sqrt{3}) = 0.$

We first sketch a proof of the official solution:

Plugging $\alpha = 2 + \sqrt{3}$ into $f(x)$ yields: $f(\alpha) = (26 + 7a + 2b + c) + (15 + 4a + b)\sqrt{3} = m + n\sqrt{3}.$

We have $|m| < 130, |n| \le 65.$ This gives $|m - n\sqrt{3}| \le |m| + |n\sqrt{3}| < 260.$

If $f(\alpha) \not = 0$ , we have $m - n\sqrt{3} \not = 0$ , which implies $m^2 - 3n^2 \not= 0$ . Hence $|m^2 - 3n^2| \ge 1.$

Therefore, we have:

$|f(\alpha)| = |m + n\sqrt{3}| = |\frac{m^2 - 3n^2}{m - n\sqrt{3}}| \ge | \frac{1}{m - n\sqrt{3}}| > \frac{1}{260},$ which is a contradiction and we are done.

Notice that if we replace $10^{-4}$ by $10^{-2}$ , then the above solution does not work.

—————————————————————————————

Here, I give a different proof, using the following theorem of Liouville:

Theorem (Liouville) Let $\alpha$ be an algebraic number of degree $n$ . Let
$f(x) = a_nx^n + \dots + a_0 \in \mathbb{Z}[x]$ such that $f(\alpha) = 0$
and that $f$ is irreducible over $\mathbb{Q}.$ Then for all $p/q \in \mathbb{Q}$ ,
we have:

$\left| \alpha - \frac{p}{q} \right| \ge \frac{c(\alpha)}{q^n},$
where $c(\alpha) = \min\{ M, 1/|a_n|(3M)^{n-1} \}.$

Here $M = \max \{ |\alpha_i| \}$ , where $\alpha_i$ are the roots of $f.$ The proof of this theorem will be given later, let;s see how we can apply this theorem to this CGMO problem.

Proof: Let $\alpha = 2 + \sqrt{3}, \beta = 2 - \sqrt{3}.$ Let $g(x) = x^2 - 4x + 1$ , then $g(\alpha) = 0$ and $f$ is clearly irreducible. (i.e. $\alpha$ is an algebraic number of degree $2$ ) Since $\alpha^2 = 4\alpha - 1.$ We have $f(\alpha) = \alpha^3 + a\alpha^2 + b\alpha + c = (15 + 4 + b)\alpha + (c - a - 4).$ Now, suppose $f(\alpha) \not= 0,$ then we have $(15 + 4a + b)(c - a - 4) \not = 0$ since $2 + \sqrt{3}$ is not rational (this is an easy application of the rational root theorem). Write $p = |15 + 4a + b|, q = |c - a - 4|.$ Now $|\beta f(\alpha) | = |p + q\beta|$ since $\alpha \beta = 1.$ By Liouville, we have:

$\frac{|\beta| |f(\alpha)|}{q} = \left| \beta + \frac{p}{q} \right| \ge \frac{c(\beta)}{q^2}.$

Now, $c(\beta) = \min \{ M, 1/3M \} = \min\{ \alpha, 1/(3\alpha)\} = 1/(3\alpha)$ since $3\alpha^2 > 1$ .

This gives: $|f(\alpha)| \ge \frac{1}{\alpha \beta 3q} = \frac{1}{3q}.$

Finally, we have $3q \le 3|c - a - 4| \le 3(24) = 72 < 100.$
Therefore, $1/3q > 10^{-2}.$ This is a contradiction and
we are done.

—————————————————————————————

Appendix: Proof of Liouville’s theorem.

Proof: We have $|f(\alpha) - f(p/q)| = |f(p/q)| \ge 1/q^n$ since the numerator of $f(p/q)$ is a non-zero integer. Now we consider two cases:

(1) $|p/q| > 2M,$ then $|\alpha - p/q| \ge ||p/q| - |\alpha|| \ge M \ge M/q^n$ , since $q \ge 1.$

(2) $|p/q| \le 2M$ , then $|\alpha_i - p/q| \le |\alpha_i| + |p/q| \le 3M.$ We have $|a_n| \prod_{i = 1}^{n} |\alpha_i - p/q| = |f(p/q)| \ge 1/q^n.$ Let $\alpha_1 = \alpha$ , we have:

$|\alpha - \frac{p}{q}| \ge \frac{1}{|a_n| \prod_{i = 2}^{n} |\alpha_i - p/q|q^n} \ge \frac{1}{|a_n (3M)^{n-1}q^n}.$

Hence, we have $\left| \alpha - \frac{p}{q} \right| \ge \frac{c(\alpha)}{q^n}$ as claimed.

Posted in IMO | Tagged Add new tag, CGMO, Diophatine Approximations, Liouville | Leave a Comment »

HKIMO 2009 Selection Test 1 problem 2

八月 31, 2008

Here is the problem:

Solve the following system of equations mod 37:

$a^2 + bc \equiv a \pmod{37}$
$b(a + d) \equiv b \pmod{37}$
$c(a + d) \equiv c \pmod{37}$
$bc + d^2 \equiv d \pmod{37}$
$ad - bc \equiv 1 \pmod{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:

$A^2 = A,$ where

$A = \begin{pmatrix}a & b\\c & d \end{pmatrix}$

The extra condition, $ad -bc \equiv 1 \pmod{37}$ says that $A$ is invertible. Therefore, we may multiply $A^{-1}$ on both sides to get $A = I$ , the identity matrix. This yields $(a, b, c, d) = (1, 0, 0, 1)$ is the unique answer.

Challenge: Try to answer the same question without the assumption $ad - bd \equiv 1 \pmod{37}.$ (i.e. simply remove this equation from the system of equations.)

Posted in IMO, Mathematics, Number Theory | Tagged Add new tag, IMO, Mathematics, Matrix | Leave a Comment »

Hong Kong Selection Test 1 Problem 6 for IMO 2009

八月 31, 2008

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

For the equation: $y^{37} = x^{3} + 11.$

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:

$\phi: \mathbb{F}_{p}^{\times} \to \mathbb{F}_{p}^{\times}$

$x \mapsto x^q$

is an automorphism if $(p-1, q) = 1.$

Of course, this theorem is phrased in a group theorectic language. In elementary terms, it simply means that everything is a $q$ th power mod $p$ if $(p-1, q) = 1.$

Proof: Suppose $(p-1, q) = 1.$ Then there exists integers $x, y$ such that $x(p - 1) + qy = 1.$

Therefore, $a^{1} = a^{x(p-1) + qy} = a^{p(x - 1)} \times a^{qy} = a^{qy}$ by Fermat’s little theorem. Hence $a = (a^y)^q$ is a $q$ th power and we are done.

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

Solution: If $(p-1, 3) = 1$ or $(p-1, 37) = 1$ , 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. $p \equiv 1 \pmod{111}.$ 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.

Posted in IMO, Mathematics, Number Theory | Tagged Group, IMO, Mathematics, Number Theory, qth power lemma | Leave a Comment »

Mathematics in HKCEE, HKAL, and Beyond