Re: [其他] 奧數一題

[Sfly (topos)]

令 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://www.ptt.cc/bbs/Math/M.1527359946.A.DF4.html
→ raymond92928: g(1) = g(2) mod [2,10,60]這部分看不懂
推 LPH66       : 2013 = 3*11*61, φ(2013) = 2*10*60
→ LPH66       : 不過這裡應該不是 CRT... 2 10 60 又不互質
→ LPH66       : 這裡應該是 Carmichael(2013) = LCM(2,10,60) = 60
→ LPH66       : 後幾行驗證 60 時用 3,4,5 拆開驗才是 CRT
→ Sfly        : no, 對 mod 3,11,31分別用歐拉定理，然後用中國剩餘
→ Sfly        : 定理
→ Sfly        : PS. CRT沒有限定兩兩互質
推 raymond92928: 我懂了,謝謝.另外我看書上的CRT定理,有說要兩兩互質
推 LPH66       : 喔, 是先拆質數再做 CRT...
→ LPH66       : 感覺起來這好像差不多是 Carmichael Thm. 的證明?
→ Sfly        : maybe, 但我不記得卡米歇爾定理，我會稱這個過程為"
→ Sfly        : 精確的"Euler定理
→ Sfly        : 另，只有聯立同餘式之間是consistent, 就可以化簡為
→ Sfly        : mod 互質的同餘式，一般那樣子寫是比較省筆墨。用抽
→ Sfly        : 象代數的觀點CRT是 Z/I x Z/J = Z/ (I+J)
推 arthurduh1  : 這樣寫 I, J 還是要 coprime
→ arthurduh1  : 沒有互質條件就只會有單邊的 homomorphism
→ arthurduh1  : 強度上來看, Carmichael Thm 強於 這個精確的 Euler
→ arthurduh1  : Thm. 本題只需要後者就夠了.
→ arthurduh1  : Carmichael Thm. 還要求最小, 這裡只需要互質的部分
→ arthurduh1  : 能分開算這個性質.
→ arthurduh1  : 而且右邊要改成Z/(IJ) 或 Z/(I∩J). 難怪覺得怪怪的