p是質數，證明循環小數1/p的循環節最多是(p-1)位

Question

p是質數，且p不是2也不是5，請證明循環小數1/p的循環節最多是(p-1)位。
比方1/7循環節142857，6位數。
1/17循環節0588235294117647，16位數。
為何1/p的循環節最多就是p-1位數呢？
我知道兩種方法，但是還是想和大家討論一下，說不定有人也知道這兩種方法，甚至能有第三種方法也說不定。

Answer 1

根據費瑪小定理若(a,p)=1則ap-1≣1 (mod p)因為不為2不為5的p與10互質所以10p-1≣1 (mod p)p | 10p-1-1pk=10p-1-11/p = k/10p-1-1所以1/p就是p-1位循環

2005-05-30 08:12:58 補充：
k剛好就是循環的數

Answer 2

孟：
沒錯，我所知道的兩個方法一個是費馬小定理，一個就是你用的鴿籠原理，但是你似乎有點用錯了吧？！
我不是要證有某個數不斷重複，而是要證至多在第p位以前必然會開始重複，
比方說1/19的循環節為什麼不是19位數？為什麼不是20位數？或甚至更長的位數？差一點了，再想想吧！

Answer 3

我會用鴿籠原理證明

鴿籠原理：
當 k 個籠子裡總共裝 k + 1 隻鴿子，其中一定有某個籠子裡的鴿子數不少於二隻。

因為 a 除以 b 所的到的餘數 r 勢必不會大於除數 b，那麼反覆除法運算所得到的餘數一定是 1 至 b - 1（至多）之間的數字。根據鴿籠原理，如果答案沒有整除而是循環小數的話，餘數由 1 到 b - 1 這 b - 1 個數中，一定有某個數不斷重覆。就像是有 b - 1 個籠子，但是鴿子卻是多的數不完的情形一樣。

2005-05-28 22:25:08 補充：
呵呵... 我沒看清楚就急著回答了... >.< 不好意思呀...