Free Hosting

Free Web Hosting with PHP, MySQL, Apache, FTP and more.
Get your Free SubDOMAIN you.6te.net or you.eu5.org or...
Create your account NOW at http://www.freewebhostingarea.com.

Cheap Domains

Cheap Domains
starting at $2.99/year

check

只有一個數字的數 - 純元數

從一而終

我們把清一色由 1 組成的數,如 1 、 11 、 111 、.... 稱為純元數 (Repunit),我們對這些特殊形態的數的素性特別有興趣。

我們可以把這些數記成

10x-1+10x-2+10x-3+...+102+10+1 或 (10x-1) / 9。

如 17位的純元數,即取 x=17, 或是 (1017-1) / 9。

 

下表列出部份純元數的素性 (Primality) 和其素因子 (Prime Divisor):

x

素因子分解式
素性
x
素因子分解式
素性
1
1
單位
2
11
素數
3
3*37
合數
4
11*101
合數
5
41*271
合數
6
3*7*11*13*37
合數
7
239*4649
合數
8
11*73*101*137
合數
9
32*37*333667
合數
10
11*41*271*9091
合數
11
21649*513239
合數
12
3*7*11*13*37*101*9901
合數
13
53*79*265371653
合數
14
11*239*4649*909091
合數
15
3*31*37*41*271*2906161
合數
16
11*17*73*101*137*5882353
合數
17
2071723*5363222357
合數
18
32*7*11*13*19*37*52579*333667
合數
19
1111111111111111111
素數
20
11*41*101*271*3541*9091*27961
合數

 

我們不難發現上表合數居多,純元素數 (Repunit Prime) 僅得 2 員,即 x = 2 和 19。其實若 x 是一合數,假設 x = ab,

10ab-1 = (10a+1) (10(a-1)b + 10(a-2)b + 10(a-3)b + ...... + 1),即可以分解,純元數也可被分解。反過來說,則未必成立。

故我們現在只考慮當 x 是素數的情況。

 

下表列出部份當 x 為素數時的純元數的素性和其素因子:

x
素因子分解式
素性
x
素因子分解式
素性
1
1
單位
2
11
素數
3
3 * 37
合數
5
41 * 271
合數
7
239 * 4649
合數
11
21649 * 513239
合數
13
53 * 79 * 265371653
合數
17
2071723 * 5363222357
合數
19
1111111111111111111
素數
23
11111111111111111111111
素數
29
3191 * 16763 * 43037 * 62003 * 7784389397
合數
31
2791 * 6943319 * 57336415063790604359
合數
37
2028119 * 247629013 * 2212394296770203368013
合數
41
83 * 1231 * 538987 * 201763709900322803748657942361
合數
43
173 * 1527791 * 1963506722254397 * 2140992015395526641
合數
47
35121409 * 316362908763459525091406154038726382279
合數
53
107 * 1659431 * 1325815267337711173 * 47198858799491425660200071
合數
59
2559647034361 * 43400876285657460212144534289928559826755746751
合數
61
733 * 4637 * 329401 * 974293 * 1360682471 * 106007173861643 * 7061709990156159479
合數
67
493121 * 79863595778924342083*28213380943176667001263153660999177245677
合數
73
121171337159 * 1856193842151350117 * 49207341634646326934001739482502131487446637
合數
79
317 * 6163 * 10271 * 307627 * 49172195536083790769 * 3660574762725521461527140564875080461079917
合數
83
3367147378267 * 9512538508624154373682136329 * 346895716385857804544741137394505425384477
合數
89
497867 * 103733951 * 104987505733 * 5078554966026315671444089 * 403513310222809053284932818475878953159
合數
97
12004721 * 846035731396919233767211537899097169 * 109399846855370537540339266842070119107662296580348039
合數
     

我們終於找到第三個純元素數了。這即是 x = 23。

 

若 p 為素數,且具有以下型式 40r±1、40r±3、40r±9、40r±13之一,則有

10(p-1)/2 = 1 (mod p)

即 10(p-1)/2 除以 p 餘 1 。若取 x = (p-1)/2 是合數則不用理會,因可分解。但若 x 是素數,我們便可從上式,得知 10x-1 是 p 的倍數,而長 x 數位的純元數也自然是 p 的倍數,是一合數。

在 100 以內的 x 值,符合上述數式的素數 x 僅 41 和 53,即相對於 p = 83 和 107 而言。是故 1041-1 可被 83 整除,而 1053-1 可被 107 整除。儘管我們還可應用更多數論上的知識來驗證純元數的素性,但總體而言也是黑暗一片,未見光明。

 

其實,我們現在找到的純元素數只有五個,分別是有 2、 19 、23 、 317 和 1031 個數位。無巧不成 2 * 19 * 23 * 317 * 1031 + 1 = 285646799 亦是一個素數。

 

 

一道奧數問題

二零零五至零六年度香港區數學奧林匹克競賽個人組預賽出了一這樣的一道問題,估不到解題中牽扯到純元數上,故引來討論。

 

該問題原列第七題,問題如下:

已知在數列 1001,1001001,1001001001,......,1001001...1001,...... 中有 R 個素數 (原文為質數),求 R 的值。

若要同學估計答案可不難,1001 = 7 * 11 * 13 ,而 1001001 又是 3 的倍數, 1001001001 又會是 1001 的倍數。素數性質雖多變,然可問的答案一是在首數項中出現素數,一是無限,然現在首三項也不見素數蹤影,估「R = 0」相信也不會錯了吧。

然則如何證明,「R = 0」呢?

本人草證如下:

設數列 A1 = 1,A2 = 1000,A3 = 10002,......,An = 1000n-1

S1 = A1,S2 = A1 + A2,S3 = A1 + A2 + A3,...... ,Sn = A1 + A2 + A3 + ...... + An

而原問題中的數列即是 S2,S3,S4,......

 

首先 Sn 為一數含有 n 個 1 的及 2(n-1) 個零的數,其位數為 3n-2。 此 Sn 有下列三個特性:

1. S2 是合數,因其可被 7、11、13整除;

2. S3 是合數,因其可被 3 整除;

3. Skn是合數,因其可被 Sn 整除,而 k 是任意正整數。

由此可知,我們只得考慮 Sp 的素性,其中 p 為一大於 3 的素數。

 

而利用等比級數求和公式,我們可知

Sp = (1000p - 1) / 999

Sp = (1000p - 1) / (9 * 111)

然令 X = (1000p - 1) / 9 為一純元數且位數為 3p,Y = (10p - 1) / 9 為一純元數且位數為 p。即

X = 111......111 (3p數位);Y = 111......111 (p數位)

故 X 是 Y 的倍數。且 X = 111 * Sp ,但由於 p 為一大於 3 的素數,故該純元數 Y 比 111 大,且 Y 不是 111 的倍數,即 (Y, 111) = 1 。但 Y 不會和 Sp 相等,因 Y 是 p 位數的,而 Sp 是 (3p-2) 位數的。自然不過, Y 便是 Sp 的因子之一。是故 Sp 為一合數,原問題數列中沒有素數,取 R = 0。

 

會不會有更直接的證明方法,因本人以為此法要求學生有一定的數感 (Mathematical Sense),即對數字直觀而聯想至其特性的能力,然本人自問數感不足,也得經過對數列中首十數項進行素因子分解後,才從因子中找到頭緒。幸運的是,預賽只用寫上答案,不用證明。

 

一個推廣

我們把純元數的要求擴展至任何的進制,即該數在某一進制下的全 1 ,我們便稱為廣義純元數 (Generalized Repunit)。

以數學式表示即

(bn- 1) / (b - 1) 式中 b 不少於 2

那數便是在 b 進制下的純元數了。

如 7 = (23- 1) / (2 - 1),所以 7 是二進制下的純元數,因為 7 = 111(2)

(其實所有梅森數 (Mersenne Number) 均是二進制的純元數,本章所述的不包括此數。)

如 43 = (63- 1) / (6 - 1),所以 43 是六進制下的純元數,因為 43 = 111(6)

上述兩例均為素數,若某數為廣義純元數且為素數,則某數為廣義純元素數 (Generalized Repunit Prime)。

 

參考文獻及網址

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, p. 66, 1987.

Beiler, A. H. "11111...111." Ch. 11 in Recreations in the Theory of Numbers: The Queen of Mathematics Entertains. New York: Dover, 1966.

Caldwell, C. K. "The Top Twenty: Generalized Repunit ." http://primes.utm.edu/top20/page.php?id=16.

De Geest, P. "Repunits and Their Prime Factors." From World of Number. http://users.skynet.be/worldofnumbers/repunits.htm .

Weisstein, E. W. "Repunit." From MathWorld. http://mathworld.wolfram.com/Repunit.html.