自作問題置き場 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)⟺n\star p_1\equiv a_1\wedge n\star p_2\equiv a_2\wedge \cdots \wedge 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\cdot 5,7\cdot 11\cdot 13,17)\equiv n\star (8,15,1001,17)\equiv (5,-1,-4,1).$$
もし、整数 $s,t,u$ が
$$\begin{array}{}\text{(1)}& 1001\cdot 17\cdot s\star & 15& \equiv & 17017s\equiv 1\text{(2)}& 15\cdot 17\cdot t\star & 1001& \equiv & (16-1)(16+1)t\equiv ({16}^2-1)t\equiv 255t\equiv 1\text{(3)}& 15\cdot 1001\cdot u\star & 17& \equiv & 15015u\equiv 1\end{array}$$
を満たすならば、
$$\begin{array}{}\text{(4)}& m=1001\cdot 17\cdot s\cdot (-1)+15\cdot 17\cdot t\cdot (-4)+1001\cdot 15\cdot u\cdot 1\end{array}$$
なる整数 $m$ は、
$$m\star (15,1001,17)\equiv (-1,-4,1)$$
を満たす。
式 (1) より、
$$\begin{gathered} 1001\cdot 17s\star 15\equiv 7\cdot 11\cdot 13\cdot 17s\equiv 7\cdot -4\cdot -2\cdot 2s\equiv 7\cdot 16s\equiv 7s\equiv 1, \\ 7\cdot 2\star 15\equiv 14\equiv -1より、7\cdot (-2)\equiv 1, \\ \therefore s\equiv -2\equiv 13. \end{gathered}$$
式 (2) より、$15\cdot 17t\star (7,11,13)\equiv (1,1,1)$ なので、
$$\begin{array}{}\text{(5)}& & 15\cdot 17t\star 7\equiv 1\cdot 3t\equiv 3t\equiv 1,3\cdot 5=15=7\cdot 2+1よりt\equiv 5,\text{(6)}& & 15\cdot 17t\star 11\equiv 4\cdot 6t\equiv 24t\equiv 2t\equiv 1,2\cdot 6=12=11+1よりt\equiv 6,\text{(7)}& & 15\cdot 17t\star 13\equiv 2\cdot 4t\equiv 8t\equiv 1,8\cdot 5=40=13\cdot 3+1よりt\equiv 5,\end{array}$$
式 (5), (7) より、$t$ は、自然数 $k$ を用いて、
$$t=7\cdot 13k+5=91k+5$$
と表わすことができる。これと式 (6) より、
$$\begin{gathered} 1\equiv (t-5)\star 11\equiv 7\cdot 13k+5-5\equiv 7\cdot 2k\equiv 14k\equiv 3k,3\cdot 4=12\equiv 1よりk=4, \\ \therefore t=91\cdot 4+5=364+5=369. \end{gathered}$$

式 (3) より、
$$15\cdot 1001u\star 17\equiv 15\cdot 7\cdot 11\cdot 13u\equiv -2\cdot 7\cdot -6\cdot -4u\equiv -14\cdot 24u\equiv 3\cdot 7u\equiv 21u\equiv 4u\equiv 1$$
両辺を 4 倍して
$$16u\star 17\equiv -u\equiv 4よりu\equiv -4\equiv 13.$$

求めた $(s,t,u)=(13,369,13)$ を式 (4) に代入し、$m$ の値を求める。
$$\begin{array}{rl}m& =1001\cdot (16+1)\cdot 13\cdot (-1)+255\cdot 369\cdot (-4)+1001\cdot (16-1)\cdot 13\cdot 1\\ & =-2\cdot 1001\cdot 13-4\cdot ((3\cdot 85)\cdot (3\cdot 123))\\ & =-2\cdot 1001\cdot 13-4\cdot 9(104-19)(104+19)\\ & =-2\cdot 1001\cdot 13-4\cdot 9({104}^2-{19}^2)=-2\cdot 1001\cdot 13-4\cdot 9(10816-361)\\ & =-2\cdot 1001\cdot 13-4\cdot 9\cdot 10455=-2\cdot 1001\cdot 13-4\cdot 94095\\ & =-2\cdot 1001\cdot 13-4\cdot (94\cdot 1001+1)=-2\cdot 1001(13+188)-4\\ & =-1001\cdot 402-4=-402406.\end{array}$$

ところで、$1001\star 8\equiv 1$ なので、
$$m\star 8\equiv -1001\cdot 402-4\equiv -1\cdot 2-4\equiv -6\equiv 10,$$
また、
$$M=3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\star 8\equiv 255\cdot 1001\equiv (256-1)\cdot 1\equiv -1.$$
$n$ は、$m$ に $M$ をいくつか足して 8 で割った余りが 5 になる最初の正の数だが、$n\equiv 10$ で $M$ を足すたびに剰余が 1 減るので、$M$ を 5 回足せばよく、
$$\begin{array}{rl}n& =m+5M=-1001\cdot 402-4+5\cdot 255\cdot 1001\\ & =1001\cdot 3\cdot (5\cdot 85-134)-4=1001\cdot 3\cdot (425-134)-4\\ & =1001\cdot 3\cdot 291-4=873873-4=873869.\end{array}$$