歐拉函數
瑞士數學家歐拉 (Leonhard Euler 1707-1783)
(照片取自「The MacTutor History of Mathematics Achieve」http://www-gap.dcs.st-and.ac.uk/~history/ )
歐拉函數
歐拉 j 函數 (Euler Totient Function) 或簡稱歐拉函數 (Euler's Function) j(n) 來表示不大於 n 且與 n 互素 (Coprime) 的整數的個數。
例如不大於 10 且與 10 互素的整數有 1、3、7、9,所以 j(10) = 4。
若某數 n 的素因子分解式 (Prime Factorization) 為
則 j(n) = n * (1-p1-1) * (1-p2-1) *...* (1-pr-1) 。
如 j(100) = 100 * (1-1/2) * (1-1/5) = 100 * 1/2 * 4/5 = 40。
我們可知若 p 為一素數,j(p) = p - 1,因由 1 至 p - 1 也跟 p 互素。
若 n 為一無平方因子數 (Squarefree Number),即對上式所有 ai 也是 1,j(n) = (p1- 1 ) * (p2 - 1 ) *...* (pr - 1 )。
數學家舒軒斯爾 (A. Schinzel) 猜想對每個偶數 k, j(n) = j(n+k) 有無窮多個解。他注意到奇數 k 是不成立的。若 k = 3,在 n < 10000 中,只有 n = 3 和 n = 5 是解。波蘭數學家謝爾品斯基 (Waclaw Sierpinski 1882 - 1969) 證明了對每一個 k 至少存在一個解,舒軒斯爾和華古利錫 (A. Wakulicz) 更證明在 2*1058 中,對每個 k 至少存在兩個解。
2*j(n) = j(n+k) 又如何?數學家馬高域斯基 (Andrzej Makowski) 證明對每一個 k 至少有一解。3*j(n) = j(n+k) 又如何?4*j(n) = j(n+k) 又如何?5*j(n) = j(n+k) 又如何?
歐拉 j函數既是解決問題好幫手,亦是產生問題的煩東西。也許數學就是這樣矛盾,也許這才是數學家的腦子「年終無休」。
雷默問題
我們知道對於任何素數 p,其歐拉函數值,j(p) = p - 1,美國數學家 D.H.雷默 (Derrick Henry Lehmer 1905-1991) 或譯萊默,在 1932 年問「是否存在合數 n ,使 j(n) 整除 n - 1?」這個問題至今尚未解決,而且我們現在和當年D.H.雷默的情況沒多大分別。
但我們現在只知這數若存在的話:該數一定很大且有很多因子。
D.H.雷默在 1932年證明了 n 必為無平方因子的 (Squarefree) 奇數,而且它的素因子個數 (Number of Prime Divisor) 不少於 7。
後來 1944年,舒歐 (F. Schuh) 證明了素因子個數不少於 11。
到了 1970年,理歐倫斯 (E. Lieuwens) 證明了若 n 為三的倍數,其素因子個數不少於 213 個且 n > 5.5* 10570,而當 n 不為三十的倍數 ( 即 n 同時不為 2、3、5 的倍數) 時,其素因子個數不少於 13。
到了 1980年,傑弗里.高漢 (Geoffrey L. Cohen) 及 希基斯 (P. Hagis, Jr.) 證明了對任意合成數 n ,n 必定不少於二十數位,且其素因子個數不少於 14。D. W. 沃爾 (D. W. Wall) 證明了當 n 不為三十的倍數時,其素因子個數不少於 26。
看素因子個數和數值日大,我們真的懷疑有否這樣的數存在,但證明它不存在又是何等容易的事呢?
卡邁克爾猜想
美國數學家卡邁克爾 (Robert Daniel Carmichael 1879-1967) 在 1922 年提出了個關於歐拉函數取值重覆度的猜想:
對於任何正整數 n ,均有一正整數 m 不等於 n ,使 j(m) = j(n) 。
這便是卡邁克爾 j 函數猜想 (Carmichael's Totient Function Conjecture)。
1947 年,基爾 (V. L. Klee) 證明了這猜想對 j(n) < 10100 中所有 n 均成立。1982年 馬沙 ( P. Masai) 及 瓦利特 (A. Valette) 利用同一方法得到 j(n) < 1010000 。1994年,舒拉法 (A. Schlafly) 及 韋根 (S. Wagon) 證明反例 (Counterexample) 的下界 (Lower Bound) 在 n > 10^(10^7)。福特 (K. Ford) 把下界推至 n > 10^(10^10)。
基本上數學家都相信卡邁克爾猜想是正確的。
由歐拉函數而來的素數
若使 j(x) = n 有解的正偶數 n ,我們稱為 j值 (Totient)。 反之使上式無解的正偶數 n,我們稱為非j值 (Nontotient)。如 n = 14、26、34、38、50、... (OEIS A005277)
若使 x - j(x) = n 有解的正偶數 n ,我們稱為對偶 j值 (Cototient)。 反之使上式無解的正偶數 n,我們稱為非對偶j值 (Noncototient)。如 n = 10、26、34、50、52、... (OEIS A005278)
若一數 k 使 x - j(x) = k 有解且解的數目比任何小於 k 的整數為多,這 k 我們便稱之為高對偶 j數 (Highly Cototient Number)。
高對偶 j數的例子有:2, 4, 8, 23, 35, 47, 59, 63, 83, 89, 113, 119, 167, 209, 269, ... (OEIS A100827)
當中有不少奇數,其實除 2, 4, 8 以外其餘的高對偶 j數都是奇數,在 209 或以後的個位全是 9。
當中的素數,我們便稱之為高對偶 j素數 (Highly Cototient Prime),如 2, 23, 47, 59, 83, 89, 113, 167, 269, 389, ... (OEIS A105440)
參考文獻及網址:
Beiler, A. H. Ch. 12 in "Recreations in the Theory of Numbers: The Queen of Mathematics Entertains." New York: Dover, 1966.
Conway, J. H. and Guy, R. K. "Euler's Totient Numbers." The Book of Numbers. New York: Springer-Verlag, pp. 154-156, 1996.
Ribenboim, P. "The Little Book of Bigger Prime" , New York: Springer-Verlag, 1991
Weisstein, E. W. "Totient Function." From MathWorld. http://mathworld.wolfram.com/TotientFunction.html.
Wikipedia. "Euler's Totitent Function." From Wikipedia. http://en.wikipedia.org/wiki/Euler's_totient_function.
Wikipedia. "Highly Cototitent Number." From Wikipedia. http://en.wikipedia.org/wiki/Highly_cototient_number.