作者Sfly (topos)
看板Math
標題Re: [其他] 奧數一題
時間Sun May 27 02:38:54 2018
令 g(n)=2011^(2011^(.....^2011)) (n個2011)
先證 g(2)=g(3) mod 2013.....(*)
pf. 2013=3*11*61
By Euler theorem and CRT,
g(1) = g(2) mod [2,10,60]
would imply (*).
However, 2011^2011 = 2011 mod N, where N=3,4,5
So, g(1)=g(2) mod 60.
Hence the result.
因此 g(2011) = g(2010)= ...= g(2) =
(-2)^2011=-2^2011=856 mod 2013
提示僅用在最後不用真的去計算 2^2011 mod 2013
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.165.188.189
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1527359946.A.DF4.html
1F:→ raymond92928: g(1) = g(2) mod [2,10,60]這部分看不懂 05/29 17:31
2F:推 LPH66 : 2013 = 3*11*61, φ(2013) = 2*10*60 05/29 20:36
3F:→ LPH66 : 不過這裡應該不是 CRT... 2 10 60 又不互質 05/29 20:38
4F:→ LPH66 : 這裡應該是 Carmichael(2013) = LCM(2,10,60) = 60 05/29 20:40
5F:→ LPH66 : 後幾行驗證 60 時用 3,4,5 拆開驗才是 CRT 05/29 21:06
6F:→ Sfly : no, 對 mod 3,11,31分別用歐拉定理,然後用中國剩餘 05/30 01:08
7F:→ Sfly : 定理 05/30 01:08
8F:→ Sfly : PS. CRT沒有限定兩兩互質 05/30 01:35
9F:推 raymond92928: 我懂了,謝謝.另外我看書上的CRT定理,有說要兩兩互質 05/30 14:32
10F:推 LPH66 : 喔, 是先拆質數再做 CRT... 05/30 16:46
11F:→ LPH66 : 感覺起來這好像差不多是 Carmichael Thm. 的證明? 05/30 16:46
12F:→ Sfly : maybe, 但我不記得卡米歇爾定理,我會稱這個過程為" 05/30 18:50
13F:→ Sfly : 精確的"Euler定理 05/30 18:50
14F:→ Sfly : 另,只有聯立同餘式之間是consistent, 就可以化簡為 05/30 18:54
15F:→ Sfly : mod 互質的同餘式,一般那樣子寫是比較省筆墨。用抽 05/30 18:54
16F:→ Sfly : 象代數的觀點CRT是 Z/I x Z/J = Z/ (I+J) 05/30 18:54
17F:推 arthurduh1 : 這樣寫 I, J 還是要 coprime 05/30 19:16
18F:→ arthurduh1 : 沒有互質條件就只會有單邊的 homomorphism 05/30 19:17
19F:→ arthurduh1 : 強度上來看, Carmichael Thm 強於 這個精確的 Euler 05/30 19:19
20F:→ arthurduh1 : Thm. 本題只需要後者就夠了. 05/30 19:19
21F:→ arthurduh1 : Carmichael Thm. 還要求最小, 這裡只需要互質的部分 05/30 19:20
22F:→ arthurduh1 : 能分開算這個性質. 05/30 19:21
23F:→ arthurduh1 : 而且右邊要改成Z/(IJ) 或 Z/(I∩J). 難怪覺得怪怪的 05/31 15:23