歐拉函數跟因子總和同行
一個變大、一個變小、一個證明
歐拉函數 (Euler's Function) j(n) 來表示不大於 n 且與 n 互素 (Coprime) 的整數的個數。 關於這個函數的介紹，詳可參看《歐拉函數》一文。但由於 n 不會與自身互素，所以我們可以肯定一點對所有 n 而言， j(n) < n 。
因子總和 (Sum of Divisors) s(n) 表示 n 的所有因子加起來的值。關於這個函數的介紹，詳可參看《因子總和》一文。但由於 n 本身也是 n 的因子之一，所以我們又可以肯定一點對所有 n 而言 s(n) > n 。
這樣兩個一大一小的函數值相乘會有什麼結果呢？我們可以肯定它們的乘積小於 n2，即 j(n) * s(n) < n2，或 j(n) * s(n) / n2 < 1。
為何呢？
我們假定設
即 j(n) = n * (1-p1-1) * (1-p2-1) *...* (1-pr-1) = n * [(p1 - 1) * (p2 - 1) *...* (pr - 1)] / [(p1) * (p2) *.....* (pr)]
而 s(n) = (p1a1+1-1)/(p1-1) * (p2a2+1-1)/(p2-1) * ... * (prar+1-1)/(pr-1)
那麼 j(n) * s(n) / n2 = [(p1a1+1-1) * (p2a2+1-1) * ... * (prar+1-1)] / [(p1) * (p2) *.....* (pr) * n]
亦即為 [(p1a1+1-1) * (p2a2+1-1) * ... * (prar+1-1)] / [(p1a1+1) * (p2a2+1) * ... * (prar+1)] < 1
問題得證。
其實我們有絕對不等式 6n2 / p2 < j(n) * s(n) < n2。
一個倍數、一個因子
同一數的歐拉函數值和因子總和當然不會相同，兩值之間也可以說是沒什麼大的關連。於是數學家便替這兩個函數 (Function) 的值設限，再看看有沒有整數符合。這兒，我為大家介紹一些常見的問題吧。
首先一問，會否有一數，該數的歐拉函數值可整除該數的因子總和。換句話來說，我們要求因子總和是歐拉函數值的倍數 (Multiple)，或歐拉函數值是因子總和的因子 (Factor)。
以數式表示：
s(n) = k * j(n)
其中 k 為大於 1 的整數。
首先，除 2 、3 以外，不會再有素數 (Prime Number) 滿足上式：
對 2 而言，s(2) = 3，j(2) = 1，即 k = 3；而 3 呢，s(3) = 4，j(3) = 2，即 k = 2。
但由於對任何素數 s(p) = p + 1， j(p) = p - 1。若真的存有整數 k 值滿足上式的話，即
p + 1 = k (p - 1)，(k - 1)p = k + 1，p = (k + 1) / (k - 1)，
最後我們有 p = 1 + 2 /( k - 1)。要使 p 為整數，故得 k = 2 或 3，從而得 p = 3 或 2 ，即上例。
在 1000 以內，我們發現有下列的數符合要求：
| k 值 | 符合要求的數 |
| 2 | 3、 35 |
| 3 | 2、 15 |
| 4 | 14、 105、 248、 418 |
| 5 | 56、 190 |
| 6 | 6、 616、 735 |
| 7 | 12、 78、 910 |
| 8 | 42、 594、 744 |
| 9 | 30、 264、 714 |
| 10 | 168、 270、 570 |
| 11 | 當中沒有符合要求的數值。 |
| 12 | 210 |
| 13 | 630 |
| 14 | 420 |
| 15 | 840 |
可參考另文附表《素因子分解表》。
是你的我，還是我的你？
同一數的歐拉函數值和因子總和當然不會相同，但同樣經過兩種函數運算的數值又會否一樣呢？
我是說先作歐拉函數後求因子總和，跟先作因子總和後求歐拉函數的數值又會否相同。數學上說，兩值若相等，即是要求
s( j(n) ) = j( s(n) )
要知道這兩個函數不是相逆的函數，我們不保證先後次序的改動對數值不會有影響。正因如此，數學家才對滿足上式的整數 n 有興趣。
我們測試後得知 1, 9, 225, 242, 516, 729, 3872, 13932, 14406, 17672 等 (OEIS A033632 ) 滿足上式。
先不看特別的 1 ，因為 1 的歐拉函數值和因子總和也是 1 。
我們亦發現當中包括 9, 729 等 3 的方冪，其實這一點，伊朗伊斯法罕大學 (University of Isfahan) 講師法奧沙巴赫 (Farideh Firoozbakht 1962- ) 亦看到，他更指出若 (3n + 1 - 1) / 2 是一個素數的話，3n 便滿 足上式。我們且看看 9 和 729 兩例，即 n = 2 和 5，那 (3n + 1 - 1) / 2 = 13 和 1093 均為素數。
其實這也不難證明的：
s( 3n ) = (3n + 1 - 1) / 2，
若這為素數，即 j( s( 3n ) ) = j( (3n + 1 - 1) / 2 ) = (3n + 1 - 1) / 2 - 1 = (3n + 1 - 3 ) / 2 = 3 / 2 * (3n - 1 )
j( 3n ) = 2 * 3n - 1，s( j( 3n ) ) = (22 - 1) / (2 - 1) * (3n - 1) / (3 - 1) = 3 / 2 * (3n - 1 )
故兩式相等，該數符合上式要求。
相同的素因子
我們看到 s(n) 、 j(n) 、 n 的數值都不同，但它們會否含有或是只含有相同的素因子 (Prime Factor) 呢？
在較小的數值中，我們可看不到這個現象。因為要符合相同素因子的要求， n 得含有很多不同的素因子。
數學愛好者比波迪 (Luke Pebody) 找到一個符合要求的例子，n = 6534150553412193640795377701190：
n = 2 * 3 * 5 * 7 * 11 * 133 * 172 * 292 * 313 * 372 * 672 * 3073
j(n) = 218 * 38 * 52 * 7 * 11 * 132 * 172 * 29 * 312 * 37 * 67 * 3072
s(n) = 219 * 35 * 54 * 75 * 11 * 133 * 17 * 29 * 31 * 37 * 672 * 307
他亦同時給出一個更小的例子 ，n = 103654150315463023813006470：
n = 2 * 34 * 5 * 7 * 11 * 133 * 173 * 292 * 313 * 372 * 672
j(n) = 217 * 39 * 52 * 7 * 11 * 132 * 172 * 29 * 312 * 37 * 67
s(n) = 216 * 37 * 52 * 74 * 112 * 132 * 17 * 29 * 31 * 37 * 672
更重要的是比波迪找出一道通式，找尋一定數量的解。他發現，符合要求的數一定包含下列 14 個素因子：
2、3、5、7、11、13、17、29、31、37、41、67 、73和 307 再配以不同的方冪而成。
| 素因子 |
可能方冪 |
| 2 | 0、1、2、3、4、5、7、8、9、11、19 |
| 3 | 0、1、2、3、4、5、7、11 |
| 5 | 0、1、2、3、5 |
| 7 | 0、1、3 |
| 11 | 0、1 |
| 13 | 0、1、3 |
| 17 | 0、1、2、3、5 |
| 29 | 0、1、2 |
| 31 | 0、1、3 |
| 37 | 0、2 |
| 41 | 0、1、3 |
| 67 | 0、1、2 |
| 73 | 0、1、3 |
| 307 | 0、1、3 |
上述共有 57736800 個不同的組合，比波迪一一測試，最終找到上述的解。而他找到最大的解值為 408022974940131316797952098741068774084359509019326873600000。
留意，這兒所列的並非所有的解，因為比波迪在找尋合用的素冪時設了限，他只考慮不大於 1000000 的素數。我們若把該限制放寬，解數或會更多，解值或會更大。
參考文獻及網址：
Rivera, C. "Problems & Puzzles: Puzzle 451 - Prime factor of n, j(n) & s(n)." http://www.primepuzzles.net/puzzles/puzz_451.htm.
