tsujimotterの下書きノート

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

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

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

12^123 を 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}

が得られる。

よって、

12^{123} = 12^{11\cdot 11 + 2} \equiv 18^{11}\cdot 144
\equiv 2^{11}3^{22}\cdot 144
\equiv (\tau(2) - 1) (\tau(3) - 1)^2 \cdot 144
\equiv (-25) \cdot 251^2 \cdot 144
\equiv (-25) \cdot 5
\equiv (-125)
\equiv 566 \pmod{691}

が得られる。