2008 八月 « Mathematics in HKCEE, HKAL, and Beyond

Archive for 八月, 2008

HKAL 2008 problem

八月 31, 2008

Here is a pure math problem in HKAL 2008:

證明方程 $x^4 - 8x^3 + 22x^2 - 24x + 10 = 0$ 沒有實根.

This is discussed in the mathdb blog:

http://mathdb.blogspot.com/2008/06/blog-post_27.html

The usual solution uses calculus, while I gave a one line solution:

$x^4 - 8x^3 + 22x^2 - 24x + 10 = (x^2 - 4x + 3)^2 + 1$ , which is clearly positive, and hence the equation has no real roots.

In fact, the following is true: Let $f(x)$ be a monic quartic polynomial with real coefficients. If $f(x)$ has no real roots, then $f(x)$ can be written as a sum of two squares. (i.e. $f(x) = [g(x)]^2 + [h(x)]^2$ for some polynomials $g$ and $h.$ )

Here is a simple proof: Suppose $f(x)$ has no reals roots. We have $f(x) = (x - \alpha)(x - \overline{\alpha})(x - \beta)(x - \overline{\beta}).$

Writing $\alpha = a + bi, \beta = c + di$ , we have $(x - \alpha)(x - \overline{\alpha}) = (x-a)^2 + b^2.$

We have $f(x) = ((x - a)^2 + b^2)((x - c)^2 + d^2) = [(x - a)(x - c) + bd]^2 + [(x - a)d - (x - b)c]^2.$ [Here, basically I used the identity: $(a^2 + b^2)(c^2 + d^2) = (ac + bd)^2 + (ad - bc)^2.$ ] We are done.

Hence, if a student see this kind of problem again, calculus is usually not the best way. It is perhaps better to try to write the expression as a sum of two squares.

Posted in HKAL, Pure Mathematics | Tagged HKAL, Polynomial, Pure Mathematics, Quartic, Squares | 2 意見»

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.