108^469 mod 2357

この記事は、コメントで指摘されている通り重大な誤りを含んでいます。本来は記事を修正するべきではあるのですが、正直面倒ではあるので、結局の計算結果が誤っていることをご了解願えたらと思います。(2020-11-24)

——————————

以下、数は $2357$ を法として考えることがある。例えば $2358$ と $1$ が $2357$ を法として合同であることを $2358=1$ と表記する。ところで $2357$ って素数なんですかね？

$108^{469}$ を $2357$ で割った余りを求める。

$108^2=11664=-121$ より、$108^{469}=(-121)^{234}\times 108$ が成り立つ。

(ところで $108^2+11^2=0$ らしい。$11$ と $2357$ とは互いに素であるため、任意の $2357$ の素因子 $p$ について、$-1$ は法 $p$ で平方数である。よって平方剰余の相互法則より $p$ は法 $4$ で $1$ と合同である。このような素数で $2357$ の平方根未満のものは $5$, $13$, $17$, $29$, $41$ のみである。これらの素数で $2357$ は割れないので、$2357$ は素数である。)

$(-121)^{234}=121^{234}=11^{468}$ が成り立つ。ここで、$468=2^2 3^2 13$ が成り立つ。

$11^4=14641=499$ である。$499=2856=28\times 102$ より、$11^6=28\times 102 \times 121=11\times 14\times 2244 =11\times 14\times(-113)=7\times (-2488)=7\times (-131)=-917=1440$ が成り立つ。よって $11^6=2^5 3^2 5$ である。

$11^{468}=(11^6)^{78}=2^{390} 3^{156} 5^{78}$ が成り立つ。ここで $108=2^23^3$ であったため、$108^{469}=2^{492}3^{159}5^{78}$ が成り立つ。

このとき、$3^7=2187=-170$ より、$3^{154}=2^{22}5^{22}17^{22}$ が成り立つ。よって $2^{492}3^{159}5^{78}=2^{504}3^5 5^{100} 17^{22}$ が成り立つ。

$17^2 2^3=289\times 8=2312=-45=-3^2 5$ より、$2^{504} 3^5 5^{100} 17^{22}=-2^{471} 3^{27} 5^{111}$ が成り立つ。

$2^{14}=16384=-115$ より、$2^{16}5=-2300=57$ が成り立ち、さらに $2^{19} 5^2=2280=-77$ が成り立つため、$2^{456} 5^{48} = 7^{24}11^{24}$ より、$-2^{471}3^{27}5^{111}=-2^{15}3^{27}5^{63}7^{24}11^{24}$ が成り立つ。ここで、$11^6=2^53^2 5$ であったため、結局 $-2^{35}3^{35}5^{67}7^{24}$ と等しい。

そろそろ行き当たりばったりでやるのしんどくなってきた。

$3^7=-170$ であったため、$-2^{35}3^{35}5^{67}7^{24}=2^{42}5^{72}7^{29}17^5=5^{75}7^{29}17^5 23^3$ が成り立つ。

$5^47^2=125\times 245=30625=7055=-16$ より、$5^{56}7^{28}=2^{56}=(-115)^4=115^4$ が成り立つ。したがって、求める値は $5^{23}7\times 17^523^8$ と等しい。 $5^317=2125=-232$ より、これは$-2^{15}5^3 7\times 23^8 29^5$ と等しい。

$23\times 2^2\times 29=23*116=2668=311$ より、$2^223^229=311\times 23=7153=82$ が成り立つ。よって $-2^75^37\times 29\times 82^4$ が求める値である。$29\times 82=2358=1$ より、$28\times 29 \times 82^2=-81$ が成り立つ。よって求める値はさらに $2^53^45^3 82^2$ と計算される。$30\times 82=83$ より、これは $2^33^25\times 83^2$ と等しい。

$83^2=6889=-192$ である。$12\times -192=-2304=53$ より、求める値は $30\times 53=1590$ である。

暗算でできたら、ヤバいなって思う。間違いあったら言ってね。