合数次方同余

tommywong

$n^2 \equiv n(mod2),n^3 \equiv n(mod3),n^5 \equiv n(mod5),n^7 \equiv n(mod7)$

$n^4 \equiv n^2(mod4),n^4 \equiv n^2(mod6),n^5 \equiv n^3(mod8),n^8 \equiv n^2(mod9),n^5 \equiv n(mod10)$

其妙

回复 1# tommywong
啥子飞马定理吧？或质数的欧拉？

tommywong

研究大致上完成
有关讨论参见：bbs.emath.ac.cn/thread-5600-1-1.html

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

$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!)$

其妙

回复 3# tommywong
，这题可以搬到高等数学论坛了！

tommywong

先允许数归吧。

证明若有$\displaystyle x^m \equiv \sum_{i=1}^m (-1)^{i-1} C_m^i x^{m-i} (mod k)$

则有$\displaystyle x^{m+n} \equiv \sum_{i=1}^m (-1)^{i-1} C_{n+i-1}^n C_{n+m}^{n+i} x^{m-i} (mod k)$

tommywong

$\displaystyle x^{m+n} \equiv \sum_{i=1}^m (-1)^{i-1} C_{i-1+n}^{i-1} C_{m+n}^{m-i} x^{m-i} (mod k)$

$\displaystyle C_m^i C_{n+m}^{m-1} -C_{n+i}^i C_{n+m}^{m-1-i} =\frac{m!(n+m)!}{i!(m-i)!(m-1)!(n+1)!}-\frac{(n+i)!(n+m)!}{i!n!(m-1-i)!(n+i+1)!}$

$=\displaystyle \frac{m(n+m)!(n+i+1)-(m-i)(n+1)(n+m)!}{i!(m-i)!(n+1)!(n+i+1)}=\frac{(n+m+1)!(n+i)!}{(i-1)!(m-i)!(n+1)!(n+i+1)!}=C_{n+i}^{i-1} C_{n+1+m}^{m-i}$

算是推了过去吧......

tommywong

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

证$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：$\displaystyle 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)$