合数次方同余

fungarwai · 发表于 2014-6-11 21:16:43

kastin 发表于 2014-6-11 17:14
你的矩阵表示什么意思，可以解释一下吗？并且这些东西跟1楼的问题有什么内在关系呢？

如果单独求最后的 ...

降幂矩阵可从递推数列得出。
若$x^2=ax+b$，则必然存在$A_n,B_n$使$x^n=A_n x+B_n$，且$A_1=1,B_1=0$
$x^{n+1}=A_{n+1} x+B_{n+1}=A_n x^2+B_n x=(aA_n+B_n)x+bA_n$
$x^3=ax^2+bx=(a^2+b)x+ab$
$\begin{pmatrix} a & 1\\b & 0\end{pmatrix}^2 \begin{pmatrix} 1\\0 \end{pmatrix}=\begin{pmatrix} a^2+b\\ab \end{pmatrix}$
13#第三行代入11#结果

fungarwai · 发表于 2014-6-12 08:18:44

用程序算了前6个
$2x+x^2+x^4 \equiv 0 (mod4)$
$5x+x^3 \equiv 0 (mod6)$
$2x+3x^2+2x^3+x^4 \equiv 0 (mod8)$
$7x^2+x^4+x^6 \equiv 0 (mod9)$
$9x+x^5 \equiv 0 (mod10)$
$6x+5x^2+x^4 \equiv 0 (mod12)$

k=4;a=zeros(1,k);
for x=0:k^k-1
for y=1:k
a(y)=rem(fix(x*k^(1-y)),k);
end
for y=1:k
if(a(k+1-y)~=0)
if(a(k+1-y)==1)z=1;
else z=0;
end
break;
end
end
if(max(a)==0)continue;
end
m=0;
for n=1:k
s=0;
for y=1:k
s=s+a(y)*n^y;
end
if(rem(s,k)==0)m=m+1;
end
end
if(m==k && z==1)
fprintf('%d',a);
fprintf('\n');break;
end
end

复制代码

fungarwai · 发表于 2014-6-12 18:22:55

$x^4 \equiv 2 x^3+ x^2-2 x \pmod{8}$

$\begin{pmatrix} 2 & 1 & 0\\1 & 0 & 1\\-2 & 0 & 0 \end{pmatrix}^n=\frac{1}{6}
\begin{pmatrix} 1 & -1 & 1\\-3 & 1 & 0\\2 & 2 & -1 \end{pmatrix}
\begin{pmatrix} (-1)^n & 0 & 0\\0 & 1 & 0\\0 & 0 & 2^n \end{pmatrix}
\begin{pmatrix} 1 & -1 & 1\\3 & 3 & 3\\8 & 4 & 2 \end{pmatrix}$

$\D x^{n+3} \equiv \frac{-3+(-1)^n+2^{n+3}}{6} x^3+\frac{1-(-1)^n}{2} x^2+\frac{3+(-1)^n-2^{n+2}}{3} x \pmod{8}$

fungarwai · 发表于 2014-6-13 07:05:37

A002034
1,2,3,4,5,3,7,4,6,5,11,4,13,7,5,6,17,6,19,5

$x^2-x \equiv 0 \pmod 2$
$x^{n+2} \equiv x \pmod 2$

$x^3-3x^2+2x \equiv 0 \pmod 6$
$x^{n+3} \equiv \begin{pmatrix} x^2 & x\end{pmatrix}\begin{pmatrix} -1 & 4\\2 & -4\end{pmatrix}\begin{pmatrix} 1\\2^n \end{pmatrix} \pmod 6$

$x^4-6x^3+11x^2-6x \equiv 0 \pmod{24}$
$x^{n+4} \equiv \frac{1}{2}\begin{pmatrix} x^3 & x^2 & x\end{pmatrix}\begin{pmatrix} 1 & -16 & 27\\-5 & 64 & -81\\6 & -48 & 54\end{pmatrix}\begin{pmatrix} 1 \\ 2^n \\ 3^n\end{pmatrix} \pmod{24}$

fungarwai · 发表于 2014-6-13 11:40:34

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

C未有通项，暂时用程序生成

m=input('m=');
p=zeros(1,m);p=poly([1:m-1]);
A=zeros(m-1);B=zeros(m-1);C=zeros(m-1);
for i=1:m-1
A(i,1)=-p(1,i+1);
for j=1:m-1
if(j-i==1)A(i,j)=1;end
B(i,j)=i^(1-j);
end
end
C=A/B;
rats(C)

复制代码

fungarwai · 发表于 2014-6-13 13:01:18

是范德蒙矩阵的逆...

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

fungarwai · 发表于 2014-6-13 14:46:56

$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 · 发表于 2014-6-17 09:01:20

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

证$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 · 发表于 2015-8-1 12:48:06

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

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 合数次方同余

点评