循環小數與素數
循環小數的學問
若我們把一分數轉化為小數,只有兩個可能結果:
一是成為有限小數,如 1/4 = 0.25 、 2/5 = 0.4 等 ,
二是成為循環小數 (Repeating Decimal) ,如 2/3 = 0.66666666... 、 1/7 = 0.1428571428... 等。
在循環小數中,我們知道它們的數位 (Digit) 會重複,有周期性,不像無理數般冇規律。我們稱這周期為循環節 (Repetend) ,循環節有長有短,如 2/3 的循環節僅一數,如 1/7 的循環節則有 6 位之多。
我們從 10 的因子分解式 (Factorization) 中只看到有 2 和 5 兩個素因子 (Prime Factor),故一分數的分母若只含有 2 或 5 兩個素因子,不論次數多少,這也必然是有限位的小數;反之便是循環小數了。若以 1/p ( p 為素數且不等於 2 或 5) 轉化為小數,則必定是循環小數了。
說回循環小數,有些循環小數,如以 7 為分母的,它只有一個循環:
1/7= |
0.142857142857...... |
2/7= |
0.285714285714...... |
3/7= |
0.428571428571...... |
4/7= |
0.571428571428...... |
5/7= |
0.714285714285...... |
6/7= |
0.857142857142...... |
由上表可知,以 7 為分母的分數的循環節總是由 142857 這六個數依序開首而成。
但有些循環小數,如以 13 為分母的,它則有二個循環:
1/13= |
0.076923076923...... |
2/13= |
0.153846153846...... |
3/13= |
0.230769230769...... |
4/13= |
0.307692307692...... |
5/13= |
0.384615384615...... |
6/13= |
0.461538461538...... |
7/13= |
0.538461538461...... |
8/13= |
0.615384615384...... |
9/13= |
0.692307692307...... |
10/13= |
0.769230769230...... |
11/13= |
0.846153846153...... |
12/13= |
0.923076923076...... |
由上表可知,以 13 為分母的分數的循環節不只是由一個循環而成。和以 7 為分母的分數相同是同樣長 6 數的循環節,但不同的便是有兩組數了。分子為 1、3、4、9、10 和 12 的以 076923 為循環節;而其餘的,即分子為 2、5、6、7、8、11 的則以 153846 為循環節。奇不奇怪?
其實這也不難解釋的。
1/7 = 0.142857142857......,而 10/7 = 1.428571428571...... 即 1 + 3/7 = 1.428571428571......
故 3/7 = 0.428571428571......
我們看 30/7 = 4.285714285714...... ,而 30/7 = 4 + 2/7,所以得 2/7 = 0.285714285714......
我們不斷把原數乘以 10 ,不斷產生新的分數:1 => 3 => 2=> 6=> 4 => 5 => 1=> 3 ......
若然我們可以在不斷產生新的分數的過程產生全部 (p-1) 個分子,以那素數為分母的分數便會只得一個循環了。
現在讓我們看看 13 的例子吧!
1/13 = 0.076923076923......,而 10/13 = 0.769230769230......,100/13 = 7 + 9/13 = 7.692307692307......,所以 9/13 = 0.692307692307......。如此下去,我們得 1 => 10=> 9 => 12 => 3 => 4 => 1。留意這一數列無法產生 2 等其他數字,而 2 等則在另一序列出現: 2 => 7 => 5 => 11 => 6 => 8 => 2。所以以 13 為分母的分數存在兩個不同的循環了。
留意,每序列出現的數字個數應是一樣的,這和模 p 同餘 (Congruence) 的理論相關,讀者或可在看完本章後自行參透,本人不作冗述。是故我們只要找到一序列的周期,便可知道以該素數為分母的分數包含多少個不同的循環了。是故循環節的長度必為 p-1 的因子。
附表列出一些素數分母的分數的循環節:
3 |
3、6 |
7 |
142857 |
11 |
09、18、27、36、45、54、63、72、81、90 |
13 |
076923、153846 |
17 |
08823529117647 |
19 |
052631578947368421 |
23 |
0434782608695652173913 |
29 |
0344827586206896551724137931 |
31 |
032258064516129、096774193548387 |
37 |
027、054、081、135、162、189、243、297、378、459、486、567 |
41 |
02439、04878、07317、09756、12195、14634、26829、36585 |
43 |
023255813953488372093、046511627906976744186 |
47 |
0212765957446808510638297872340425531914893617 |
53 |
0188679245283、0377358490566、0754716981132、0943396226415 |
59 |
0169491525423728813559322033898305084745762711864406779661 |
61 |
016393442622950819672131147540983606557377049180327868852459 |
67 |
014925373134328358205955223880597、029850746268656716417910447761194 |
71 |
01408450704225352112676056338028169、09859154929577464788732394366197183 |
73 |
01369863、02739726、04109589、05479452、06849315、08219178、12328767、15068493、16438356 |
79 |
0126582278481、0253164556962、0379746835443、0506329113924、0759493670886、1518987341772 |
83 |
01204819277108433734939759036144578313253、02409638554216867469879518072289156626506 |
89 |
01123595505617977528089887640449438202247191、03370786516853932584269662921348314606741573 |
97 |
01030927835051546391752577319587628865979381443298 -96907216494845360082474226804123711340206185567 |
註 |
97 那行,該數是一組數,只因過長而分兩行書寫。 |
長素數
從以素數 p 為分母的分數,我們不難找到一些只有一組循環的分數,即那循環節長 (p-1)。這樣的素數,我們便稱為全循環素數 (Full Reptend
Prime) 或長素數 (Long Prime)。我們不難發現 7 是一全循環素數,因 1/7 的循環節恰好是 6 個位。
其實下表中全是全循環素數:
7 |
1/7= |
|
17 |
1/17= |
|
19 |
1/19= |
|
23 |
1/23= |
在 100 以內的長素數還有 29 、 47 、 59 、 61 和 97。 (OEIS A001913)
長素數與純元數
我們先前以分數倍大的角度來看過循環小數,及由其而生的長素數。
現在試由以更數學化的角度來看同樣的問題。
這便涉及數論 (Number Theory) 中原根 (Primitive Root) 的問題了。
若 g 與 p 互素,且 g 是一素數 p 的原根,即
gi = 1 (mod p)
而這個 i 最小的值是 p-1。
回到我們的課題上,原來若 p 是全循環素數,當且僅當,10 是 p 的原根:
10i = 1 (mod p)
而這個 i 最小的值是 p-1。其實這個 i 的值便是那循環節的長度。
換句話說,
10i - 1 = 0 (mod p)
即,一必要但非充要的條件是 9Rp-1 可被 p 整除。(這裡 Rp-1 為 p-1 數位的純元數 (Repunit),即連續 p-1 位的 111...111。) 亦當 p 不為 3 時,即 Rp-1 可被 p 整除。
如為何分別以 7 和 13 為分母的分數循環節長度為 6 ,這便是因為 7 和 13 同是 111111 的因子。
( 111111 =3 * 7 * 11 * 13 * 37,但 3 是 9 的因子,而 11 和 37 分別是較小的純元數 11 和 111 的因子。故以這些素數為分母的分數的循環節長度不是 6。)
此外,那些全循環素數的倒數還有一特別的地方,看看下表:
1/7 |
0.142857... |
1/17 |
0.05882352941176470... |
2/7 |
0.285714... |
2/17 |
0.1176470588235294... |
3/7 |
0.428571... |
3/17 |
0.1764705882352941... |
4/7 |
0.571428... |
4/17 |
0.2352941176470588... |
5/7 |
0.714285... |
5/17 |
0.2941176470588235... |
6/7 |
0.857142... |
6/17 |
0.3529411764705882... |
7/17 |
0.4117647058823529... |
||
8/17 |
0.4705882352941176... |
||
9/17 |
0.5294117647058823... |
||
10/17 |
0.5882352941176470... |
||
11/17 |
0.6470588235294117... |
||
12/17 |
0.7058823529411764... |
||
13/17 |
0.7647058823529411.. |
||
14/17 |
0.8235294117647058... |
||
15/17 |
0.8823529411764705... |
||
16/17 |
0.9411764705882352... |
我們發現這些循環節的小數總是由第一個循環小數的循環節中選取不同的起始點而成,故我們稱這些循環節中的數如 142857、 5882352941176470 、 526315789473684210 等為循環數 (Cyclic Number)。 (OEIS A004042)
唯一周期的素數
惟一周期素數 (Unique Period Prime) ,亦稱惟一素數 (Unique Prime), 是以素數 p 為分母的分數所產生的循環小數的另一產物。若以素數 p 為分母的分數所產生的循環小數的循環節長度,沒有別的素數和它相同,那便是唯一周期素數或唯一素數了。
如 3 的循環節長度為 1,沒有別的素數和它相同,3 是唯一素數。
如 7 和 13 的循環節長度同為 6,是故 7 和 13 也不是唯一素數。
下表為 10100 以內的 23 個唯一素數:
循環節長度 |
唯一素數 |
1 |
3 |
2 |
11 |
3 |
37 |
4 |
101 |
10 |
9091 |
12 |
9901 |
9 |
333667 |
14 |
909091 |
24 |
99990001 |
36 |
99 9999000001 |
48 |
999999 9900000001 |
38 |
90909090 9090909091 |
19 |
111111111 1111111111 |
23 |
111 1111111111 1111111111 |
39 |
9009 0090090099 0990990991 |
62 |
9090909090 9090909090 9090909091 |
120 |
100 0099999998 9998999900 0000010001 |
150 |
1 0000099999 9999899998 9999900000 0000100001 |
106 |
90 9090909090 9090909090 9090909090 9090909090 9090909091 |
93 |
9009009009 0090090090 0900900900 9909909909 9099099099
0990990991 |
134 |
909090 9090909090 9090909090 9090909090 9090909090
9090909090 9090909091 |
294 |
1428 5715714285 7142856999 9999857142 8571428585
7142857142 8557142855 7142857142 8572857143 |
196 |
9999 9999999999 0000000000 0000999999 9999999900
0000000000 0099999999 9999990000 0000000001 |
註:上表的每欄均為一數字,若數字過長分行書寫,每十數位一間隔。(網友亦可參考 OEIS A040017 )
參考文獻及網址:
Caldwell, C. K. "Unique Prime." http://primes.utm.edu/glossary/page.php?sort=UniquePrime.
Conway, J. H. and Guy, R. K. The Book of Numbers. New York: Springer-Verlag, 1996.
Wells, D. The Penguin Dictionary of Curious and Interesting Numbers. Middlesex, England: Penguin Books, p. 71, 1986.
Weisstein, E. W. "Full Reptend Prime." From MathWorld. http://mathworld.wolfram.com/FullReptendPrime.html.
Wikipedia. "Unique prime." From Wikipedia. http://en.wikipedia.org/wiki/Unique_prime.