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

$23\times 2^2\times 29=23\ast 116=2668=311$ より、$2^2{23}^{2}29=311\times 23=7153=82$ が成り立つ。よって $-2^7{5}^{3}7\times 29\times {82}^4$ が求める値である。$29\times 82=2358=1$ より、$28\times 29\times {82}^2=-81$ が成り立つ。よって求める値はさらに $2^5{3}^4{5}^3{82}^2$ と計算される。$30\times 82=83$ より、これは $2^3{3}^{2}5\times {83}^2$ と等しい。

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

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