自作問題置き場 2022年2月

問題

解法

$n$ が $p$ を法として $a$ に合同であることを $n \star p \equiv a$ と書くことにする。
さらに、
$$ n \star (p_1,p_2,\cdots,p_m) \equiv (a_1,a_2,\cdots,a_m) \Longleftrightarrow n \star p_1 \equiv a_1 \;\land\; n \star p_2 \equiv a_2 \;\land\; \cdots \land n \star p_m \equiv a_m $$
と書くことにする。先の問題の $n$ の条件は次のようになる。
$$ n \star (3,5,7,8,11,13,17) \equiv (2,4,3,5,7,9,1) \equiv (-1,-1,-4,5,-4,1) \;. $$
剰余が同じグループでまとめると、
$$ n\star(8,3\cdot5,7\cdot11\cdot13,17) \equiv n\star(8,15,1001,17) \equiv (5,-1,-4,1) \;. $$
もし、整数 $s,t,u$ が
\begin{align} 1001\cdot17\cdot s \star\;& 15 &\equiv\;& 17017s \equiv 1 \tag{1}\\ 15\cdot17\cdot t \star\;& 1001 &\equiv\;& (16-1)(16+1)t \equiv (16^2 - 1)t \equiv 255t \equiv 1 \tag{2} \\ 15\cdot1001\cdot u \star\;& 17 &\equiv\;& 15015u \equiv 1 \tag{3} \end{align}
を満たすならば、
$$ m = 1001\cdot17\cdot s\cdot(-1) + 15\cdot17\cdot t \cdot(-4) + 1001\cdot15\cdot u \cdot1 \tag{4} $$
なる整数 $m$ は、
$$ m\star(15,1001,17) \equiv (-1,-4,1) $$
を満たす。
式 (1) より、
$$ 1001\cdot17s\star 15 \equiv 7\cdot11\cdot13\cdot17s \equiv 7\cdot-4\cdot-2\cdot2s \equiv 7\cdot16s \equiv 7s \equiv 1, \\ 7\cdot2 \star15 \equiv 14 \equiv -1 より、7\cdot(-2) \equiv 1, \\ \therefore s \equiv -2 \equiv 13 . $$
式 (2) より、$15\cdot17t \star (7,11,13) \equiv (1,1,1)$ なので、
\begin{align} & 15\cdot17t \star 7 \equiv 1\cdot3t \equiv 3t \equiv 1,\; 3\cdot5 = 15 = 7\cdot2+1 \;より\; t \equiv 5, \tag{5} \\ & 15\cdot17t \star 11 \equiv 4\cdot6t \equiv 24t \equiv 2t \equiv 1, \; 2\cdot6 = 12 = 11+1 \;より\; t \equiv 6, \tag{6} \\ & 15\cdot17t \star 13 \equiv 2\cdot4t \equiv 8t \equiv 1, \; 8\cdot5 = 40 = 13\cdot3+1 \;より\; t \equiv 5, \tag{7} \\ \end{align}
式 (5), (7) より、$t$ は、自然数 $k$ を用いて、
$$ t = 7\cdot13k + 5 = 91k + 5 $$
と表わすことができる。これと式 (6) より、
$$ 1 \equiv (t - 5) \star 11 \equiv 7\cdot13k + 5 - 5 \equiv 7\cdot2k \equiv 14k \equiv 3k, \; 3\cdot4 = 12 \equiv 1 \;より\; k = 4, \\ \therefore t = 91\cdot4 + 5 = 364 + 5 = 369 \;. $$

式 (3) より、
$$ 15\cdot1001u\star 17 \equiv 15\cdot7\cdot11\cdot13u \equiv -2\cdot7\cdot-6\cdot-4u \equiv -14\cdot24u \equiv 3\cdot7u \equiv 21u \equiv 4u \equiv 1 $$
両辺を 4 倍して
$$ 16u \star17 \equiv -u \equiv 4 \; より\; u \equiv -4 \equiv 13\; . $$

求めた $(s,t,u) = (13,369,13)$ を式 (4) に代入し、$m$ の値を求める。
\begin{align} m &= 1001\cdot(16+1)\cdot13\cdot(-1) + 255\cdot369\cdot(-4) + 1001\cdot(16-1)\cdot 13 \cdot1 \\ &= -2\cdot1001\cdot13 - 4\cdot((3\cdot85)\cdot(3\cdot123)) \\ &=-2\cdot1001\cdot13 - 4\cdot9(104-19)(104+19) \\ &= -2\cdot1001\cdot13 - 4\cdot9(104^2-19^2) = -2\cdot1001\cdot13 - 4\cdot9(10816 - 361) \\ &= -2\cdot1001\cdot13 - 4\cdot9\cdot10455 = -2\cdot1001\cdot13 - 4\cdot94095 \\ &= -2\cdot1001\cdot13 - 4\cdot(94\cdot1001 + 1) = -2\cdot1001(13 +188)-4 \\ &= -1001\cdot402 - 4 = -402406 \;. \end{align}

ところで、$1001 \star 8 \equiv 1$ なので、
$$ m \star 8 \equiv -1001\cdot402 -4 \equiv -1\cdot2 - 4 \equiv -6 \equiv 10, $$
また、
$$ M = 3\cdot5\cdot7\cdot11\cdot13\cdot17 \star 8 \equiv 255\cdot1001 \equiv (256-1)\cdot1 \equiv -1 \;. $$
$n$ は、$m$ に $M$ をいくつか足して 8 で割った余りが 5 になる最初の正の数だが、$n \equiv 10$ で $M$ を足すたびに剰余が 1 減るので、$M$ を 5 回足せばよく、
\begin{align} n &= m + 5M = -1001\cdot402-4+5\cdot255\cdot1001 \\ & = 1001\cdot3\cdot(5\cdot85-134)-4 = 1001\cdot3\cdot(425-134)-4 \\ &= 1001\cdot3\cdot291-4=873873-4 = 873869 \; . \end{align}