tsujimotterの下書きノート

このブログは「tsujimotterのノートブック」の下書きです。数学の勉強過程や日々思ったことなどをゆるーくメモしていきます。下書きなので適当です。

記事一覧はこちらです。このブログの趣旨はこちら。

メインブログである「tsujimotterのノートブログ」はこちら。

12^345 を 691 で割った余り

ラマヌジャンの合同式

\tau(p) \equiv 1 + p^{11} \pmod{691}

より

-24 = \tau(2) \equiv 1 + 2^{11} \pmod{691}
252 = \tau(3) \equiv 1 + 3^{11} \pmod{691}

である。

ここから

12^{11} = 2^{22} \cdot 3^{11}
\equiv (\tau(2) - 1)^2 (\tau(3) - 1)
\equiv 25^2 \cdot 251
\equiv 18 \pmod{691}

が得られる。

また

18^{11} = 2^{11}3^{22}
\equiv (\tau(2) - 1) (\tau(3) - 1)^2
\equiv (-25) \cdot 251^2
\equiv (-25) \cdot 120
\equiv (-3000)
\equiv 455 \pmod{691}

が得られる。

よって、

12^{345} = 12^{2\cdot 11 \cdot 11 + 9\cdot 11 + 4}
= ((12^{11})^{11})^2 \cdot (12^{11})^9 \cdot 2^8\cdot 3^4
\equiv 455^2 \cdot 18^9 \cdot 2^8\cdot 3^4
\equiv 455^2 \cdot 18^{11} \cdot 2^6
\equiv 455^2 \cdot 455 \cdot 64
\equiv 637 \cdot 64
\equiv 690 \pmod{691}