歐拉函數

瑞士數學家歐拉 (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-p₁^-1) * (1-p₂^-1) *...* (1-p_r^-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)，即對上式所有 a_i 也是 1，j(n) = (p₁- 1 ) * (p₂ - 1 ) *...* (p_r - 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*10⁵⁸ 中，對每個 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* 10⁵⁷⁰，而當 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) < 10¹⁰⁰ 中所有 n 均成立。1982年 馬沙 ( P. Masai) 及 瓦利特 (A. Valette) 利用同一方法得到 j(n) < 10¹⁰⁰⁰⁰ 。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.