OMC194(F) - 多項式を用いた解法

　 $p=2752752752753$ とし，特に断りのない場合，合同式の法は全て $p$ とする．
　 $x$ の多項式 $f(x)$ について，次数を $4$ で割った余りが $0,1,2,3$ となる項の係数の総和をそれぞれ $A,B,C,D$ とする．このとき，以下の等式が成り立つ．（ $i$ は虚数単位）

$$A=\dfrac{1}{4}(1^0\times f(1)+i^0\times f(i)+(-1)^0\times f(-1)+(-i)^0\times f(-i))$$ $$B=\dfrac{1}{4}(1^3\times f(1)+i^3\times f(i)+(-1)^3\times f(-1)+(-i)^3\times f(-i))$$ $$C=\dfrac{1}{4}(1^2\times f(1)+i^2\times f(i)+(-1)^2\times f(-1)+(-i)^2\times f(-i))$$ $$D=\dfrac{1}{4}(1^1\times f(1)+i^1\times f(i)+(-1)^1\times f(-1)+(-i)^1\times f(-i))$$

　本問では， $f(x)=\dfrac{(7x)^{4p}-1}{7x-1}\times\dfrac{(11x)^{4p}-1}{11x-1}\times\dfrac{(13x)^{4p}-1}{13x-1}$ としたときの $S=B+C$ を答えればよい．
　これは， $g(x)=(x^2+x^3)f(x)$ とすると， $S=\dfrac{1}{4}(g(1)+g(i)+g(-1)+g(-i))$ である．
　また， $p$ は $4$ で割って $1$ 余る素数より， $n^2\equiv -1 (\bmod p)$ なる整数 $n$ が存在するから，それぞれFermatの小定理より，

$$\begin{aligned} g(1)&= 2\times\dfrac{7^{4p}-1}{7-1}\times\dfrac{11^{4p}-1}{11-1}\times\dfrac{13^{4p}-1}{13-1} \\ &\equiv 2\times\dfrac{7^4-1}{7-1}\times\dfrac{11^4-1}{11-1}\times\dfrac{13^4-1}{13-1} \\ &\equiv 2787456000 \end{aligned}$$

$$\begin{aligned} g(i)&= (-1-i)\times\dfrac{(7i)^{4p}-1}{7i-1}\times\dfrac{(11i)^{4p}-1}{11i-1}\times\dfrac{(13i)^{4p}-1}{13i-1} \\ &\equiv (-1-i)\times\dfrac{(7i)^4-1}{7i-1}\times\dfrac{(11i)^4-1}{11i-1}\times\dfrac{(13i)^4-1}{13i-1} \\ &= (-1-i)\times 48(-1-7i)\times 120(-1-11i)\times 168(-1-13i) \\ &= 967680(1+i)(1+7i)(1+11i)(1+13i) \\ &= 967680(660-1280i) \end{aligned}$$

$$\begin{aligned} g(-1)&= 0\times\dfrac{(-7)^{4p}-1}{-7-1}\times\dfrac{(-11)^{4p}-1}{-11-1}\times\dfrac{(-13)^{4p}-1}{-13-1} \\ &= 0 \end{aligned}$$

$$\begin{aligned} g(-i)&= \overline{g(i)} \\ &\equiv 967680(660+1280i) \end{aligned}$$

　よって，

$$\begin{aligned} S&= \dfrac{1}{4}(g(1)+g(i)+g(-1)+g(-i)) \\ &\equiv \dfrac{1}{4}(2787456000+967680(660-1280i)+0+967680(660+1280i)) \\ &= \mathbf{1016198400} \end{aligned}$$