2008年10月17日 星期五

A Nice Proof of "Infinite Primes of Form 4k+1"

Recently, I am writing a set of notes about prime numbers. Certainly I have included the most well-known fact about prime numbers in the set of notes --- there are infinitely many prime numbers. There are various proofs, including the most famous proof from Euclid.

I try to add something more into the set of notes. All prime numbers, except 2, have to be in the form of 4k+1 or 4k+3 (because all the other primes are odd). Two natural follow-up questions are, "Is there infinite number of primes of the form 4k+3?" and "Is there infinite number of primes of the form 4k+1?" The proof can be included in the set of notes as an appendix for more gifted students.

It turns out that the first question is easy to answer, by mimicking the technique from Euclid. If you have never heard this before, try to understand the proof by Euclid from the link above, and adopt the main idea to the "4k+3" question.

The second question, however, is more difficult. I am not sure if there is any simpler elementary solution, but I found a rather fascinating proof on web, using the Fermat's Little Theorem. Let me restate the proof here.

Given any integer N, consider , and p be the smallest prime factor of M.

Since 1, 2, ... , N all do not divide M, p is larger than N. Since p divides , we have



Taking -th power on both sides, we have

....(1)

On the other hand, by Fermat's Little Theorem, for a = 1, 2, ... , N, we have



Multiplying the above formula with a = 1, 2, ... , N, we get

....(2)

Comparing (1) and (2), we get



which implies is even and hence p is of the form 4k+1. As N is chosen arbitrarily, we reach the conclusion: there are infinitely many primes of the form 4k+1.

Is that too difficult for F.3 and F.4 students? I am not sure, but as it is put in the appendix, it is not demanding even I put the proof of Fermat's Last Theorem there. >.<""

2008年10月16日 星期四

0.999... = 1?

  很多人應該在不少科普叢書或網上討論區見過「0.999\cdots = 1?」這問題。我們只需簡單的極限概念(甚至幾何級數和的概念),便知道這答案是肯定的,0.999\cdots 等於 1。可是每當有人在討論區提出這問題時,答案總是似是而非,甚至出現很多不同的悖證。我不打算在這裏再證明一次這道命題,但卻想簡單闡釋以前見過的常見謬誤。

謬誤一:

  \color{red}0.999\cdots 和 1 這兩個數的寫法不相同,它們怎可能一樣?

解釋:

  我們先說明甚麼是小數。如果我們以小數形式寫成某實數 r 時,其表達式為 d_0.d_1d_2d_3\cdots,我們表示 r=\displaystyle{\sum_{n=0}^\infty\frac{d_n}{10^n}=d_0+\frac{d_1}{10}+\frac{d_2}{10^2}+\frac{d_3}{10^3}+\cdots,其中 d_0 是整數部分,而 d_n 是第 n 個小數位。這是一個無窮項的和,因此我們求這個和時其實正在求某數列的極限。這個數列是 d_0d_0.d_1d_0.d_1d_2d_0.d_1d_2d_3、……。例如,我們指 \dfrac{1}{3} = 0.333\cdots 時,其實指 \dfrac{1}{3}00.30.330.333、……這數列的極限。

  在這個定義裏,我們沒特別指明表示法是唯一的。換句話說,我們沒指出實數 r 不可以擁有兩種表達式 d_0.d_1d_2d_3\cdotse_0.e_1e_2e_3\cdots。這就好像兩個分數式 \dfrac{1}{3}\dfrac{2}{6} 的值相同一樣。既然如此,為甚麼 0.999\cdots 不可以和 1 相同?

謬誤二:

  我們不會將小數寫成以無窮個 9 結尾,因此 \color{red}0.999\cdots 這寫法根本不成立。

解釋:

  如果你接受 \dfrac(1}{3} = 0.333\cdots 可以以無窮個 3 結尾,為甚麼無窮個 9 不可以?平日人們不會將 1 寫成 \color{blue}0.999\cdots,並不代表不可以這樣寫。 

謬誤三:

  \color{red}0.999\cdots 的整數部分明明是 0,而 1 的整數部分是 1,為何它們會相同?

解釋:

  請參看謬誤一。同一個實數可以擁有超過一種表示法。

謬誤四:

  \color{red}0.999\cdots 只是非常接近 1,但不相同。

解釋:

  請參看謬誤一。無窮小數的表達式是數列的極限。籠統地說,若一個數列 x_1x_2x_3、……的極限是 L,則我們指當 n 愈來愈大時,x_n 愈來愈接近 L。(當然這說法有點瑕疪,但極限的定義本來就依賴這想法而來。我們不在此深究這句子和極限的定義的分別。)以 \frac{1}{3} 為例,因為 00.30.330.333……這數列漸漸趨近 \frac{1}{3},所以我們說 \frac{1}{3} = 0.333\cdots我們指的是數列的極限是 \color{blue}\frac{1}{3},而並非數列當中任何一項是 \color{blue}\frac{1}{3}如果你接受 \dfrac{1}{3} = 0.333\cdots,為何不接受 0.999\cdots = 1?

2008年10月11日 星期六

數學講座

日期:2008 年 11 月 4 日(星期二)
時間:下午 6 時 15 分至 8 時
地點:教育局九龍塘教育服務中心西座四樓演講廳
講者:岑嘉評教授
講題:常見的不等式及奧數解題範例

有關其他詳情及報名方法,可瀏覽 http://www.hkage.org.hk/big5/new/Students/081104mo/info_c.pdf

2008年10月3日 星期五

咁都輸得?

不要以為讀博士生(其實我是在讀碩士的……)的學生都是天生的讀書狂。平時我們在office除了讀書看paper外,最喜歡就是吹水(可以一吹就幾粒鐘)、打機(PSP、網上的minigames等)。有時遇著不需要甚麼background的難題,就會圍在一起想。

今天在另一個office的博士生帶來了有一個關於象棋的問題。雖然跟數學沒甚麼關係,但思考是數學的根源嘛,也在這裏講講吧。題目是這樣的:

藍方的車馬砲卒全,紅方的俥傌砲兵都沒有了。雙方有多少隻象(相)和士(仕)可任你決定。試設計一個殘局,若藍方先行,則藍方會輸。

聽聞在另一個office的博士生想了一整天才想到。但在我們lab的幾個人群策群力下,花了不夠15分鐘便解決了。

2008年9月28日 星期日

32x32棋盤的覆蓋問題

剛剛在網上見到這樣一個問題,覺得蠻有趣的,在這裏分享一下:

有一個 32 x 32 的棋盤。你要預先剪好5塊拼圖,使得當我拿走棋盤任意一個正方形後,你可以用這5塊拼圖覆蓋「餘下的棋盤」。

當然,老規矩,5塊拼圖覆蓋時不可重覆,亦不可有任何部分在「餘下的棋盤」外啦。


原本想說多些對這問題的感想,但不想影響到大家的解題方向,所以不講了。就這樣。