合数次方同余

fungarwai

\(x^{n+1} \equiv x \begin{pmatrix} C_{x-1}^0 & C_{x-1}^1 & ... & C_{x-1}^{m-2} \end{pmatrix} \begin{pmatrix} 1 & 0 & ... & 0\\-1 & 1 & ... & 0\\... & ... & ... & ...\\ (-1)^{m-1} & (-1)^{m-2}C_{m-1}^1 & ... & 1 \end{pmatrix} \begin{pmatrix} 1 \\ 2^n \\ ... \\ (m-1)^n \end{pmatrix}\pmod{m!}\)

\(x^{n+1} \equiv x \begin{pmatrix} C_{x-1}^0 & C_{x-1}^1 \end{pmatrix} \begin{pmatrix} 1 & 0\\-1 & 1\end{pmatrix} \begin{pmatrix} 1 \\ 2^n \end{pmatrix}\pmod{6}\)

\(x^{n+1} \equiv x \begin{pmatrix} C_{x-1}^0 & C_{x-1}^1 & C_{x-1}^2 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0\\-1 & 1 & 0\\ 1 & -2 & 1 \end{pmatrix} \begin{pmatrix} 1 \\ 2^n \\ 3^n \end{pmatrix}\pmod{24}\)  

fungarwai

我把原题解答贴出来，让大家了解一下。

证$504|x^9-x^3$

$504=2^3 \times 3^2 \times 7=7 \times 8 \times 9$

$x^7 - x \equiv 0(mod 7),x^9 \equiv x^3(mod 7)$

方法1：$x^{mp+(p-1)n} \equiv \sum_{i=1}^m (-1)^{i-1} C_{i-1+n}^{i-1} C_{m+n}^{m-i} x^{mp-(p-1)i} (mod p^m)$

$x^{6+n} \equiv C_{3+n}^2 x^5-C_{1+n}^1 C_{3+n}^1 x^4 +C_{2+n}^2 x^3 (mod 8)$

$x^9-x^3 \equiv 15x^5-24x^4+10x^3-x^3 \equiv -x^5+x^3 \equiv (1-x)x^3(1+x) \equiv 0(mod 8)$

$x^{6+2n} \equiv C_{2+n}^1 x^4-C_{1+n}^1 x^2 (mod 9)$

$x^9-x^3 \equiv 3x^5-3x^3 \equiv 3x^2(x^3-x) \equiv 0(mod 9)$

方法2：\(x^{n+1} \equiv x \begin{pmatrix} C_{x-1}^0 & C_{x-1}^1 & ... & C_{x-1}^{m-2} \end{pmatrix} \begin{pmatrix} 1 & 0 & ... & 0 \\ -1  & 1 & ... & 0 \\ ... & ... & ... & ...\\ (-1)^{m-1} & (-1)^{m-2} C_{m-1}^1 & ... & 1 \end{pmatrix} \begin{pmatrix} 1 \\ 2^n \\ ... \\ (m-1)^n \end{pmatrix}(mod m!)\)

\(\begin{pmatrix} 1 & 0 & 0\\ -1 & 1 & 0\\ 1 & -2 & 1 \end{pmatrix} \begin{pmatrix} 1^8 \\ 2^8 \\ 3^8 \end{pmatrix} \equiv {pmatrix} \begin{pmatrix} 1 & 0 & 0\\ -1 & 1 & 0\\ 1 & -2 & 1 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix} \equiv \begin{pmatrix} 1 \\ -1 \\ 2 \end{pmatrix} (mod 8)\)

\($x^9 \equiv x \begin{pmatrix} C_{x-1}^0 & C_{x-1}^1 & C_{x-1}^2 \end{pmatrix} \begin{pmatrix} 1 \\ -1 \\ 2 \end{pmatrix} \equiv x(1-x+1+(x-1)(x-2)) \equiv x^3-4x^2+4x \equiv x^3-4(x^2-x) \equiv x^3 (mod 8)\)

\(\begin{pmatrix} 1 & 0 & 0 & 0 & 0\\ -1 & 1 & 0 & 0 & 0\\ 1 & -2 & 1 & 0 & 0\\ -1 & 3 & -3 & 1 & 0\\ 1 & -4 & 6 & -4 & 1 \end{pmatrix} \begin{pmatrix} 1^8 \\ 2^8 \\ 3^8 \\ 4^8 \\ 5^8 \end{pmatrix} \equiv \begin{pmatrix} 1 & 0 & 0 & 0 & 0\\ -1 & 1 & 0 & 0 & 0\\ 1 & -2 & 1 & 0 & 0\\ -1 & 3 & -3 & 1 & 0\\ 1 & -4 & 6 & -4 & 1 \end{pmatrix} \begin{pmatrix} 1 \\ 4 \\ 0 \\ 7 \\ 7 \end{pmatrix} \equiv \begin{pmatrix} 1 \\ 3 \\ 2 \\ 0 \\ 0 \end{pmatrix}(mod 9)\)

\(x^9 \equiv x \begin{pmatrix} C_{x-1}^0 & C_{x-1}^1 & C_{x-1}^2  & C_{x-1}^3 & C_{x-1}^4 \end{pmatrix} \begin{pmatrix} 1 \\ 3 \\ 2 \\ 0 \\ 0 \end{pmatrix} \equiv x(1+3(x-1)+(x-1)(x-2)) \equiv x^3(mod 9)\)

fungarwai

刚才在英文维基找到了9#的矩阵
Companion matrix
https://en.wikipedia.org/wiki/Companion_matrix