畢氏定理上的素數
畢氏數
從留言板網友 Patrick Lau 的留言中引發靈感，試看畢氏定理 (Pythagorean Theorem) 中的素數。
我們對畢氏定理相信不會感到陌生，也許它是我們所學的第一道定理。這畢氏定理在中國又名商高定理 (Soon Go Theorem) 或勾股定理。
相傳古希臘數學家畢達哥拉斯 (Pythagoras 約前 569 - 約前 475) 從直角三角形的地板中引發靈感，發現直角三角形的斜邊的平方正好是另外兩邊的平方和，即：
這顯淺而實用定理，我們在初中數學課定必接觸得到。若我們進一步規定式中的 a、b、c 均為正整數 (Positive Integer) ，這便是所謂的畢達哥拉斯數 (Pythagoras Numbers) 或畢達哥拉斯三重數 (Pythagorean Triple)，簡稱畢氏數或勾股數。
這三數組中會否全為素數，答案是不會。
原來古希臘的數學家已知要使三整數 a、b、c 符合畢氏定理，那必須有兩數 u 和 v 使：
( a, b, c ) = (u2 - v2, 2uv, u2 + v2)
若要達至本原解 (Primitive Solution) 即 GCD ( a, b, c ) = 1，我們必須要求 u > v 、GCD(u, v) = 1及 u、v 為一奇一偶。
那麼 2uv 必為偶數且不等於 2 ，當然找不到全素數的解了。
退一步，那 u2 - v2 以及 u2 + v2 都是素數，又可以嗎？
我們知道 u2 - v2 = (u - v) (u + v)，要使 u2 - v2 為素數只有使 u - v = 1 及 u + v 為素數。
如取 u = 3 及 v = 2，我們有 (5,12,13) 這一組合，組合中的 5 和 13 均為素數。
又如取 u = 6 及 v = 5，我們有 (11, 60, 61) 這一組合，又找到 11 和 61 兩素數了。
會不會有例外？留給大家想一想吧，計一計吧。
同餘的智慧
當然不會這樣簡單吧。若取 u = 9 及 v = 8，我們有 u2 - v2 = 17，這是一素數，但 u2 + v2 = 145，不是素數。
其實我們了解 u - v = 1 及 u + v 為素數只是其中一條件，若要使 u2 + v2 為素數，我們還得一些要求，這是什麼，用一丁點同餘的知識便可知。
設 v = u - 1 ， u2 + v2 = u2 + (u-1)2 = 2u2 - 2u + 1
若要使 u2 + v2 為一素數，即要使 u2 + v2 不等於任何素數的倍數。
即在任何素數模 p 下， 2u2 - 2u + 1 均不等於零。
故我們考慮使 2u2 - 2u + 1 = 0 (mod p) 的數值，把之挑起。
2u2 - 2u + 1 = 0 (mod p) => 2u(u-1) = -1 (mod p)
我們只需考慮 f(u) = 2u(u-1) 在什麼情況會有 f(u) = -1 (mod p)。
其實 p 不可為 2 ，因在模 2 以下 2u(u-1) 恒為零。
而 u 不可為 0 或 1，因這也恒為零。
再加上 f(u) 和 f(p+1-u) 的數值是相同，此等都減少了我們測試之數目。
下表給出一些 p 和 u 的數值使 f(u) = -1 (mod p) 及相關的畢氏數及其分解式。
p |
u (mod p) |
u 的例子 |
u2 - v2 |
u2 + v2 |
u2 + v2 的素因子分解式 |
5 |
2 |
7 |
13 |
85 |
5*17 |
4 |
9 |
17 |
145 |
5*29 |
|
13 |
3 |
16 |
31 |
481 |
13*37 |
11 |
115 |
229 |
26221 |
13*2017 |
|
17 |
7 |
75 |
149 |
11101 |
17*653 |
11 |
45 |
89 |
3961 |
17*233 |
當然例子不此上述三組，還有很多。
順帶一提，因令 u - v = 1 所以我們有
u2 + v2 - 2uv = (u - v)2 = 1
即 u2 + v2 比 2uv 多 1 而已，這種三數中有兩數相差一的情況，我們稱作孿生畢氏數 (Twin Pythagoras Numbers)。
