Archive for the ‘Mathematics’ Category

h1

Sum of Squares (1)

九月 4, 2008

It is a well known theorem by Fermat that any prime of the form p = 4k + 1 can be written as a sum of two squares. 

One question is, in how many ways can we write a prime of the form p = 4k + 1 into sum of two squares? 

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

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

Posted in Mathematics, Number Theory | Tagged , | Leave a Comment »

h1

Leibniz’s identity and beyond (1)

九月 2, 2008

We start with the following well-known identity:

1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + \dots = \frac{\pi}{4}.

Let’s give a proof of this identity:

Note that \frac{1}{2n + 1} = \int_{0}^{1} x^{2n} dx, we may rewrite the series as:

\sum_{n = 0}^{\infty} \frac{(-1)^n}{2n + 1} = \sum_{n = 0}^{\infty} \int_{0}^{1} (-1)^nx^{2n} dx = \sum_{n = 0}^{\infty} (-x^2)^n dx.

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]

\sum_{n = 0}^{\infty} \frac{(-1)^n}{2n + 1} = \int_{0}^{1} \sum_{n = 0}^{\infty} (-x^2)^n dx = \int_{0}^{1} \frac{1}{1 + x^2} dx.

This last integral equals: \arctan{1} - \arctan{0} = \frac{\pi}{4}, which finishes the proof.

Consider a similar sum:

S = 1 - \frac{1}{2} + \frac{1}{4} - \frac{1}{5} + \frac{1}{7} - \frac{1}{8} + \dots + \frac{1}{3k + 1} - \frac{1}{3k + 2} + \dots

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

S = \int_{0}^{1} \sum_{k = 0}^{\infty} x^{3k} - x^{3k + 1} dx = \int_{0}^{1} \frac{1}{1 - x^3} - \frac{x}{1 - x^3} dx = \int_{0}^{1} \frac{1}{1 + x + x^2} dx.

This last integral can be computed by completing squares and trigonometric substitutions. We get the sum S equals S = \frac{2}{\sqrt{3}}(\arctan{\frac{3}{\sqrt{3}}} - \arctan{\frac{1}{\sqrt{3}}}) = \frac{2}{\sqrt{3}}\arctan{\frac{1}{\sqrt{3}}} = \frac{2}{\sqrt{3}}\frac{\pi}{6} = \frac{\pi}{3\sqrt{3}}. [The last few equalities would be excellent exercises for those students preparing for HKCEE.]

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

S_2 = 1 - \frac{1}{2} + \frac{1}{3} - \frac{1}{4} + \dots = \log{2}. [Note that this is the natural log, i.e. log base e.]

The nest question would be, why does \pi 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 S_2 = \log{2}.

Posted in Mathematics, Number Theory, Pure Mathematics | Tagged , , , , | Leave a Comment »

h1

Generating Function and Tiling Problems

九月 1, 2008

Consider the following classic: Suppose one deletes two opposite corners from a standard 8 by 8 checkerboard (or chessboard). Prove that it cannot be tiled by 31 two by one dominos.

One solution is to put the standard coloring on the board, and argue that the number of black squares and the number of white squares are different. Hence such tiling is not possible.

Here I give a different solution using generating function. To do this, we place the board on a coordinate system. Say the lower left corner is (0, 0), and the top right corner is (8, 8). From now on, we use the coordinate of the lower left corner to represent each square. i.e. the square at the top right corner is represented by (7, 7).

Now for each (a, b), we associate a monomial x^a y^b. Therefore, a horizontal domino is represented by the polynomial: x^a y^b (1 + x), and a vertical domino is represented by the polynomial x^a y^b (1 + y).

Suppose a tiling using these dominos is possible, we must have the following identity:

(\sum_{a = 0}^{7}\sum_{b = 0}^{7}x^a y^b) - 1 - x^7 y^7 = f(x, y)(1 + x) + g(x, y)(1 + y), for some polynomials f(x, y) and g(x, y).

i.e. \frac{x^8 - 1}{x - 1}\frac{y^8 - 1}{y - 1} - 1 - x^7y^7 = f(x, y)(1 + x) + g(x, y)(1 + y).

Since this is an identity, we may let x = y = -1. The left hand sides gives -2, while the right hand side gives 0 . Therefore, such tiling is not possible and we are done.

Challenge: Suppose we have 21 three by one domino. (or tri-mino?) Which square in a 8 by 8 checkerboard must be removed in order for these tri-minos to tile the board?

Posted in Mathematics | Tagged , , | 3 意見»

h1

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 , , , | Leave a Comment »

h1

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 qth 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 qth 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 , , , , | Leave a Comment »