歐拉函數跟因子總和同行

一個變大、一個變小、一個證明

歐拉函數 (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 - 1s( 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.

 

 

Free Web Hosting