Quod Erat Demonstrandum

2008/10/17

不能秒殺的提問

在堂上,一般情況下,學生提問,在下多半手起刀落,秒殺解之。今天 4E 同學問了兩個問題,在下不能秒殺:

1. 誰發明 _nC_r 這個符號?
2. 畢氏數組中是否必然存在 3 或 5 的倍數?

在下多番言明,在下的數學歷史學養貧乏,一直以為是牛頓創之,但查下網

http://baike.baidu.com/view/67312.htm

原來是在 1830 年由皮科克引入。當然,查考真偽,不能只在網上,有心研究的同學,找找文獻看吧。

至於畢氏數組,即滿足畢氏定理的三個正整數,例如 {3,4,5},{7,24,25},{20,21,29} 等等。同學留意到,三個數字中,似乎一定有 3 及 5 的倍數,這個猜想是否正確?可以舉出反例嗎?

嗯,難以秒殺,加上放學時間,沒法停下和他「慢」談,唯有在此解說。

我們知道

3^2 + 4^2 = 5^2

9 + 16 = 25

把上面 3 個數字:9, 16, 25 除以 3 後,餘數分別是

0, 1, 1

可見,上式對應著的餘數,也滿足以下關係:

0 + 1 = 1

又例如

7^2 + 24^2 = 25^2
49 + 576 = 625

而 49, 576, 625 被 3 除後,餘數分別為 1, 0, 1;可見 3 個餘數同樣滿足

1 + 0 = 1

一般地,正整數 x, y, z,若有

x + y = z

r_1, r_2, r_3 分別是 x, y, z 除以 3 後的餘數,則

r_1 + r_2 = r_3(注:必須當 r_1 + r_2 < 3 的條件下,式子才成立。)

(利用 mod,可以簡單描述為 x + y = z \Longrightarrow x + y \equiv z (mod 3)

一個正整數除以 3 後,餘數可以是 0, 1 或 2。

但一個正整數,取平方後,例如 5^2 = 25,除以 3 後,它的餘數卻只能是 0 或 1。

比如 25 = 3*8 + 1,64 = 3*21 + 1 等,不能出現餘數是 2。

為什麼呢?因為正整數的形式,只能有 3 種情況:

3k, 3k + 1, 3k + 2 (其中 k 是非負整數)(why?)

分別把它們的平方寫出

(3k)^2 = 9k^2 = 3(3k^2) = 3K
(3k + 1)^2 = 9k^2 + 6k + 1 = 3(3k^2 + 2k) + 1 = 3M + 1
(3k + 2)^2 = 9k^2 + 12k + 4 = 3(3k^2 + 4k + 1) + 1 = 3N + 1

(當中 K, M, N 皆為非負整數)

可見,當一個正整數 n 不是 3 的倍數(n \ne 3k),它的平方,被 3 除後,餘數必然是 1。- – – – – – (*)

好了,返回同學的提問,畢氏數組內,是否一定有 3 的倍數?答案是肯定有的。

如果沒有,即下式

a^2 + b^2 = c^2

a, b, c 沒有一個是 3 的倍數。

那麼,如果上式 3 個平方數 a^2, b^2, c^2 除以 3 後,餘數必然是 1(再看 (*) 吧)。

但這是沒有可能的,因為

a^2 + b^2 = c^2
\Longrightarrow r_a + r_b = r_c (r_a, r_b, r_c 分別是 a^2, b^2, c^2 除以 3 後的餘數)
\Longrightarrow 1 + 1 = 1 (沒有可能!)

也即是說:「a, b, c 中沒有一個是 3 的倍數」是沒有可能的。

(懂 mod,一行寫完:a^2 + b^2 = c^2 \Longrightarrow a^2 + b^2 \equiv c^2 (mod 3) \Longrightarrow 1 + 1 \equiv 1 (mod 3)

用類似手法,可知「a, b, c 中沒有一個是 5 的倍數」是沒有可能的。同學試證之。

後話:我不能(秒)殺的題目又點止咁少…

習題

1. 對正整數 x, y, z,下面的關係是否一定成立?
x + y = z \Longrightarrow r_x + r_y = r_z(其中 r_x, r_y, r_z 分別是 x, y, z 被 3 除後的餘數。)

2. 要尋找所有兩兩互素的畢氏數組,我們有 {mn, \frac{m^2 - n^2}{2}, \frac{m^2 + n^2}{2}},其中 m, nm \ge n)是奇數。試代入不同的 m, n 找出一些畢氏數組。嘗試證明或找資料,看看人們如何得出 {mn, \frac{m^2 - n^2}{2}, \frac{m^2 + n^2}{2}}。

2 則迴響 »

  1. 有一處錯了..
    就是9,16,25除3的餘數分別是0,1,1而不是0,1,2.
    而0+1=2應轉為0+1=1.

    迴響 由 Humdrum — 2008/10/21 @ 6:13 下午 | 回覆

  2. Thank you Humdrum! 改正了。

    迴響 由 johnmayhk — 2008/10/21 @ 6:43 下午 | 回覆


RSS feed for comments on this post. TrackBack URI

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s

在WordPress.com寫網誌.

%d 位部落客按了讚: