【ネタ計算】12の345乗を691で割った余りを計算してみた

出先なので正確じゃないですが、690 ですか？ #peing #質問箱 https://t.co/mgoDz0QsZg
— たけのこ赤軍@9/22名古屋プリパ (@691_7758337633) 2019年9月19日

上のツイートをみて、面白そうだなと思ったので、計算してみました。

ただし、普通に計算しても面白くない。せっかく ${}\bmod{691}$ なので、「ラマヌジャンの合同式」を生かした形で計算したいなと思いました。

ラマヌジャンの合同式

$p$ を素数とするとき，次が成り立つ：

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

全然効率の良くないネタ計算ではありますが、よろしければお付き合いください。

f:id:tsujimotter:20190919220459p:plain:w300

解答例

ラマヌジャンの合同式 $(*)$ と $\tau(2) = -24, \; \tau(3) = 252$ により

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

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

である。

ここから

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

が得られる。

また、同様に

$\begin{align} 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} \end{align}$

が得られる。

よって、

$\begin{align} 12^{345} &= 12^{2\cdot 11 \cdot 11 + 9\cdot 11 + 4} \\ &= ((12^{11})^{11})^2 \cdot (12^{11})^9 \cdot 12^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} \end{align}$