※ 引述《KevinLan (Posaunenblaeser)》之銘言：
: ※ 引述《KevinLan (Posaunenblaeser)》之銘言：
: : 如果稍微知道一點數論或是群論
: : 或是直接知道什麼是 Euler φ-function
: : (定義是: φ(n) = "比 n 少又跟 n 互質的正整數的總數")
: : (比如說 φ(5)=4, φ(12)=4, φ(27)=18)
: : 則 1/n 的循環節可以取成 φ(n) 的因數
: : 現在網路有點慢
: : 詳細的證明晚點在補
: 現在來證明 1/n 是一 φ(n) 位循環小數
: (如此 1/n 的最短循環節長度自然是 φ(n) 的因數)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
把這句話也證明一下好了:
考慮 S = { k 是正整數 ; 1/n 是 k 位循環小數 }
= { k 是正整數 ; 存在正整數 m 使得 n | (10^m)(10^k-1) }
S 非空, 因為 φ(n) 落在 S 中
若 a,b 屬於 S
則存在 m 使得 n | (10^m)(10^a-1) 且 n | (10^m)(10^b-1)
若 u,v 是整數, d 是正整數
滿足 ua+vb=d
假設 u > 0, v < 0 (不然就倒過來做)
由 n |（10^m)(10^(ua)-1) => n | (10^m)(10^(-vb+d)-1)
再由 n | (10^m)(10^(-vb)-1) => n | (10^m)(10^(-vb+d)-10^d)
兩式相減 => n | (10^m)(10^d-1)
=> d 也屬於 S
則若 1/n 的最小循環節是 k (於是 k 是 S 中的最小元素)
k 與 φ(n) 的最大公因數可由輾轉相除法表示成 uφ(n)+vr 的形式
所以也會在 S 裡
可是此時 k 已經是 S 中最小的了
就表示他們的最大公因數只能是 k
於是 k 整除 φ(n), 結束
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: cartan.math.ntu.edu.tw