合数次方同余

fungarwai

有规律吗？

\(n^3\equiv n\pmod6,\ n^5\equiv n \pmod{10},\ n^7\equiv n\pmod{14},\ n^5\equiv n\pmod{15}\)

\(n^4\equiv n^2\pmod4,\ n^8\equiv n^2\pmod9,\ n^4\equiv n^2\pmod{12},\ n^8\equiv n^2\pmod{18},\ n^6\equiv n^2\pmod{20}\)

\(n^5\equiv n^3\pmod8\)

\(n^8\equiv n^4\pmod{16}\)

gxqcn

运用欧拉定理即可证明。

若 \(n,a\) 为正整数，且 \(n,a\) 互素（即\(\gcd(a,n)=1\)），则
\[a^{\varphi(n)} \equiv 1 \pmod n\]

fungarwai

gxqcn 发表于 2014-6-11 08:08
运用欧拉定理即可证明。

怎么证明？

fungarwai

gxqcn 发表于 2014-6-11 08:08
运用欧拉定理即可证明。

$n^44 \equiv n^2 (mod49)$最高次是44

$n^14 \equiv 2n^8-n^2 (mod49)$最高次是14

那怎么得到最小的？

kastin

对于合数模 `m`，和任意整数`n`，总有
$$n^a \equiv n^b \pmod{m}$$
这里指数`a`和`b`是正整数，且满足
$$a-b=\lambda(m)$$`\lambda(m)`是Carmichael 函数，它定义为对于所有与`m`互质的整数`A`，满足`A^k \equiv 1 \pmod{m}`的最小正整数`k`.

`\lambda(x)`函数与欧拉函数`\varphi(x)`(Euler's Totient Function)的定义有那么一点类似的地方，但是他们是不一样。不一样的地方在于前者是底数不固定，后者是底数固定。

这两个数论函数给出了关于模的指数运算的两个重要的性质。我们注意到，对于底数`A`与模`m`互质时，指数运算`A^x \equiv r \pmod{m}`中，如果将指数`x`不断变化，就会发现余数`r`是循环变化的，而这个循环长度大小跟底数有关。而`\varphi(m)`给出了模`m`时循环长度的倍数，而`\lambda(m)`给出的是循环长度的最大值。

现在问题在于如何找出最小的正整数`b`。因为`m`是合数，所以可以进行质因数分解，`b`就是`m`的质因数分解式中质因子的指数的最大值。例如`12=2^2\*3^2`指数最大值是`2`；`20=2^2\*5`指数最大值为`2`；`8=2^3`指数最大值是`3`。对比1楼中的式子，不难发现全部吻合。

类似地，`108=2^2\*3^3`指数最大值为`3`，`\lambda(108)=18`，那么我们可以写出`n^{21} \equiv n^3 \pmod{108}`.

kastin

fungarwai 发表于 2014-6-11 09:47
$n^44 \equiv n^2 (mod49)$最高次是44

$n^14 \equiv 2n^8-n^2 (mod49)$最高次是14

关键在于找出6#中最小的`b`，然后只要满足`a-b=\lambda(m)`的`a`和`b`都满足`n^a \equiv n^b \pmod{m}`。

比如对于`m=15`，`\lambda(15)=4`，根据楼主给出的最小`b=1`，
那么有$$\eqalign{ & n^5 \equiv n\phantom{^1} \pmod{15} \\&n^6 \equiv n^2 \pmod{15} \\&n^7 \equiv n^3 \pmod{15} \\ &\dots}$$

fungarwai

$x^14 \equiv 2x^8-x^2 (mod49)$

它的降幂矩阵有通项：

\(\begin{pmatrix} 2 & 1\\-1 & 0 \end{pmatrix}^n=\begin{pmatrix} n+1 & n\\-n & 1-n \end{pmatrix},\begin{pmatrix} 2 & 1\\-1 & 0 \end{pmatrix}^3 \begin{pmatrix} 1\\ 0 \end{pmatrix} = \begin{pmatrix} 4\\ -3 \end{pmatrix}\)

例如：

$x^30 \equiv 4(x^{30-3(6)})-3(x^{30-4(6)}) \equiv 4x^12-3x^6(mod49)$

而三阶的降幂矩阵又有通项：

\(\begin{pmatrix} 3 & 1 & 0\\-3 & 0 & 1\\1 & 0 & 0 \end{pmatrix}^n=\begin{pmatrix} C_{n+2}^2 & C_{n+1}^2 & C_n^2\\1-(n+1)^2 & 1-n^2 & 1-(n-1)^2\\C_{n+1}^2 & C_n^2 & C_{n-1}^2 \end{pmatrix}\)

那么m阶降幂矩阵：

\(\begin{pmatrix} C_m^1 & 1 & ... & 0 & 0\\-C_m^2 & 0 & ... & 0 & 0\\... & ... & ... & ... & ...\\ (-1)^{m-2} C_m^{m-1} & 0 & ...  & 0 & 1\\(-1)^{m-1} C_m^m & 0 & ... & 0 & 0\end{pmatrix}^n\)的通项是什么？

fungarwai

\(\begin{pmatrix} 4 & 1 & 0 & 0\\-6 & 0 & 1 & 0\\4 & 0 & 0 & 1\\-1 & 0 & 0 & 0\end{pmatrix}^n=\begin{pmatrix} C_{n-1}^0 C_{n+3}^3 & C_{n-2}^0 C_{n+2}^3 & C_{n-3}^0 C_{n+1}^3 & C_{n-4}^0 C_n^3\\-C_n^1 C_{n+3}^2 & -C_{n-1}^1 C_{n+2}^2 & -C_{n-2}^1 C_{n+1}^2 & -C_{n-3}^1 C_n^2\\C_{n+1}^2 C_{n+3}^1 & C_n^2 C_{n+2}^1 & C_{n-1}^2 C_{n+1}^1 & C_{n-2}^2 C_n^1\\-C_{n+2}^3 C_{n+3}^0 & -C_{n+1}^3 C_{n+2}^0 & -C_n^3 C_{n+1}^0 & -C_{n-1}^3 C_n^0\end{pmatrix}\)

猜想：\(a_{ij}=(-1)^{i-1} C_{n-1+i-j}^{i-1} C_{n+m-j}^{m-i}\)

kastin

你的矩阵表示什么意思，可以解释一下吗？并且这些东西跟1楼的问题有什么内在关系呢？

如果单独求最后的那个矩阵的n次幂，可以考虑Jordan分解:`A=SJS^{-1}`
设
$$A=\begin{pmatrix} C_m^1 & 1 & \cdots & 0 & 0 \\
-C_m^2 & 0 & \cdots & 0 & 0\\
\cdots & \cdots & \cdots & \cdots & \cdots\\
(-1)^{m-2} C_m^{m-1} & 0 & \cdots  & 0 & 1\\
(-1)^{m-1} C_m^m & 0 & \cdots & 0 & 0
\end{pmatrix}$$
那么
$$J=\begin{pmatrix} 1 & 1 & 0 & 0 & \cdots & 0\\
0 & 1 & 1 & 0 & \cdots  & 0\\
\vdots & \vdots & \vdots & \ddots & \ddots & \vdots\\
0 & 0 & 0 & \cdots & 1 & 1\\
0 & 0 & 0 & \cdots & 0 & 1
\end{pmatrix}_{(m\times m)}$$
并且`S`等于
$$\begin{pmatrix} (-1)^{m-1}C_{m-1}^{m-1} & (-1)^{m-1}C_{m-2}^{m-2} & 0 & 0 & \cdots & 0\\
(-1)^{m-2}C_{m-1}^{m-2} & (-1)^{m-2}C_{m-2}^{m-3} & (-1)^{m-1}C_{m-3}^{m-3} & 0 & \cdots  & 0\\
\vdots & \vdots & \vdots & \cdots & \vdots & \vdots\\
C_{m-1}^2 & C_{m-2}^1 & -C_{m-3}^1 & \cdots & (-1)^{m-1}C_1^1  & 0\\
-C_{m-1}^1 & -C_{m-2}^0 & C_{m-3}^0 & \cdots & (-1)^mC_1^0 & (-1)^{m-1}\\
C_{m-1}^0 & 0 & 0 & \cdots & 0 & 0
\end{pmatrix}_{(m\times m)}$$
根据矩阵运算规律$$A^n=SJ^nS^{-1}$$
这里$$J^n=\begin{pmatrix}C_n^0 & C_n^1 & C_n^2 & \cdots & C_n^{m-1} \\
0 & C_n^0 & C_n^1 & \cdots & C_n^{m-2}\\
\vdots & \vdots & \cdots & \cdots & \vdots \\
0 & 0 & \cdots & C_n^0 & C_n^1 \\
0 & 0 & \cdots & 0 & C_n^0
\end{pmatrix}_{(m \times m)}$$

fungarwai

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

如果单独求最后的 ...

$(x^p-x)^m \equiv 0 (mod p^m)$

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

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

$x^{6n+8} \equiv \sum_{i=1}^2 (-1)^{i-1} C_{n+i-2}^{i-1} C_{n+1}^{2-i} x^{14-6i} \equiv C_{n+1}^1 x^8-C_n^1 x^2(mod 49)$

代入n=3可得10#需要的$x^26 \equiv 4x^8-3x^2(mod49)$

类似可得$x^{2n+7} \equiv C_{n+2}^2 x^7-C_n^1 C_{n+2}^1 x^5 +C_{n+1}^2 x^3(mod27)$