歐拉函數

瑞士數學家歐拉 (Leonhard Euler 1707-1783)

(照片取自「The MacTutor History of Mathematics Achieve」http://www-gap.dcs.st-and.ac.uk/~history/ )

歐拉函數

歐拉 j 函數 (Euler Totient Function) j(n) 來表示不大於 n 且與 n 互素 (Coprime) 的整數 (Integer) 個數。

例如不大於 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 互素。

數學家舒軒斯爾 (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(x) = n 無解的正偶數 n，我們稱為非j值 (Nontotient)。如 n = 14、26、34、38、50、...... (OEIS A005277)

若使 j(x) = n 無解的正偶數 n，我們稱為非對偶j值 (Noncototient)。如 n = 10、26、34、50、52、...... (OEIS A005278)

「非j值」和「非對偶j值」和「歐拉 j函數」一樣：既是解決問題好幫手，亦是產生問題的煩東西。也許數學就是這樣矛盾，也許這才是數學家的腦子「年終無休」。

雷默問題

我們知道對於任何素數 p，其歐拉函數值，j(p) = p - 1，美國人雷默 (Derrick Henry Lehmer 1905-1991) 在 1932 年問「是否存在合數 n ，使 j(n) 整除 n - 1？」這個問題至今尚未解決，而且我們現在和當年雷默的情況沒多大分別。

但我們現在只知這數若存在的話：該數一定很大且有很多因子。

雷默在 1932年證明了 n 必為沒平方因子的奇數，而且它的素因子個數不少於 7。

後來 1944年，舒歐 (F. Schuh) 證明了素因子個數不少於 11。

到了 1970年，理歐倫斯 (E. Lieuwens) 證明了若 n 為三的倍數，其素因子個數不少於 213 個且 n > 5.5* 10⁵⁷⁰，而當 n 不為三十的倍數 ( 即 n 同時不為 2、3、5 的倍數) 時，其素因子個數不少於 13。

到了 1980年，高漢 (G. L. Cohen) 及希基斯 (P. Jr. Hagis) 證明了對任意合成數 n ，n 必定不少於二十數位，且其素因子個數不少於 14。和爾 (D. W. Wall) 證明了當 n 不為三十的倍數時，其素因子個數不少於 26。

看素因子個數和數值日大，我們真的懷疑有否這樣的數存在，但證明它不存在又是何等容易的事呢？

卡邁克爾猜想

美國數學家卡邁克爾 (Robert Daniel Carmichael 1879-1967) 在 1922 年提出了個關於歐拉函數取值重覆度的猜想：

對於任何正整數 n ，均有一正整數 m 不等於 n ，使 j(m) = j(n) 。

這便是卡邁克爾猜想 (Carmichael Conjecture)。

1947 年，基爾 (V. L. Klee) 證明了這猜想對 j(n) < 10¹⁰⁰ 中所有 n 均成立。1982年馬沙 ( P. Masai) 及瓦利特 (A. Valette) 利用同一方法得到 j(n) < 10¹⁰⁰⁰⁰ 。1994年，舒拉法 (A. Schlafly) 及韋根 (S. Wagon) 證明反例的下界在 n > 10^(10^7)。福特 (K. Ford) 把下界推至 n > 10^(10^10)。

基本上數學家都相信卡邁克爾猜想是正確的。

參考文獻及網址：

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.