※ 引述《weifuSDT (知名不具)》之銘言：
: 1.show that if a and b are positive integers,
: then (2的a次方 - 1) mod (2的b次方 - 1 ) = (2 的 2 mod b 次方) - 1
^a 吧?
底下 x=y (mod q) 表示 x 與 y 除 q 餘數相同
跟你寫的 a mod b 表示 a 除 b 的餘數的意思不一樣
2^b = 1 (mod 2^b-1)
=> 2^a=2^(a-qb)*2^b=2^(a-qb) (mod 2^b-1), for every q
c = a mod b => a=qb+c for some q, 0<=c<b
=> 2^a-1 = 2^(c+qb)-1 = 2^c-1 (mod 2^b-1), and 2^c-1 < 2^b-1
=> (2^a-1) mod (2^b-1) = 2^(a mod b)-1
: 2.how to prove Lame's theorem ?
: Lame's theorem is that let a and b be positive integers with
: a 大於或小於 b. Then the number of division used by the
: Euclidean algorithm to find gcd(a,b) is less than or equal
: to five times the number of decimal digits in b
從 q_0=b, r_0=a mod b 出發 (也就是無論如何先除一次)
每次考慮 q_(i+1)=r_i, r(i+1)=q_i mod r_i
則每次都有 0<= r_i < q_i
考慮 c = (sqrt(5)-1)/2, (1-c)=c^2
因 c 是無理數, 不可能有 r_i = c q_i
若 r_i < c q_i, 則 q_(i+1)=r_i < c q_i 就不理它
若 r_i > c q_i, 則 q_(i+2)=r(i+1)<= q_i-r_i < (1-c)q_i = c^2 q_i
意思是說, 在做輾轉相除 (Euclidean algorithm) 的過程中
每次剩下的東西, 不是在一次除法中減為 c 倍, 就是在兩次除法中減為 c^2 倍
對任一 k , 視輾轉相除的過程, 必有 q_(k-1) < c^(k-1) q_0 或 q_k < c^k q_0
考慮 k 使得 c^k q_0 < 1/c = 1+c
若已經有 q_k < c^k q_0 則 q_k < 1+c 只能是 0 or 1
若是 q_(k-1) < c^(k-1) q_0 , 則 c q_(k-1) < 1/c => q_(k-1) < 1/c^2 = 2+c
即 q_(k-1) = 0,1,2, 則 q_k < q_(k-1) 只是 0 or 1
ie 只要 k > log(b)/log(1/c)-1, 就一定有 q_k = 0 or 1
加最開始那次 a 除 b
總共需要除的次數小於 [log(b)/log(1/c)]+1
=[(4.7849...)log(b)]+1
< 5[log(b)+1]
也就是比 b 的十進位數的五倍少
這題大概還有比較簡單的作法
5 倍的估計其實是還粗了一點
一般來說, 對任意兩個 N 位數
輾轉相除所需的除法數最多只要:
ceil[ln(sqrt(5)N)/ln((1+sqrt(5)/2)] -2 ~ 2.078ln(N)+1.672
(其中ceil[x] 表示比 x 大的最小整數)
而平均來說則約需:
12ln(2)ln(N)/pi^2+0.14 ~ 0.843ln(N)+0.14
不過這個的證明就麻煩的多了.....
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: cartan.math.ntu.edu.tw