LuoJi_1995 LuoJi_1995
关注数: 0 粉丝数: 862 发帖数: 29,459 关注贴吧数: 40
【蒟蒻也来骗经验】NOI2013D2T1和矩阵的Fermat小定理 对于 mod p 的剩余域上的 n 阶矩阵 A,如果 A 的特征多项式在 F 上有 n 个根(重根按重数计算),则任意 r, k in N,有 A^(n + r + kp(p - 1)) = A^(n + r) 证明:将 A 相似到 Jordan 标准型。 注意由于有可能有 0 作为特征值出现,特征值 0 对应的 Jordan 块显然是幂零的,n 阶幂零矩阵的 n 次幂必须是 0,这是因为 rank(A^n) = rank(A^(n + k)),任意k >= 0(这结论是代数经典习题:-P)。 下面证明 p(p - 1) 是每个非 0 特征值的 Jordan 块的周期,对每个 Jordan 块,它的幂次(次数不少于 n)的每个元的通项是 f(n)r^n,每个 f 都是关于 n 的多项式。(这点随便数归一下啦) 根据 Fermat 小定理,我们知道 f(kp(p - 1) + q)r^(kp(p - 1) + q) = f(0 + q)r^q = f(q)r^q 注意之所以 f 括号里面的 kp(p - 1) 变成了 0,是因为在这个域里面,p 和 0 是同一个元素。r 的指数中的 p 不是 0,是因为 r 的指数是一个整数,而不是此剩余域的元素! 无论如何,Jordan 块的幂从 n 次幂开始是周期的。 于是 Jordan 标准型的幂从 n 次幂开始是周期的,于是原矩阵也是这样。 综上,真正的矩阵的 Fermat 小定理是:对 mod p 剩余域上的 n 阶矩阵 A,如果 A 在这个剩余域上具有 n 个特征值,则对任意 r >= n,有 A^(r + kp(p - 1)) = A^r。 特别地,如果 A 可逆,则对任意的 r in Z 都成立上式。 NOI 2013 D2 T1 之所以可以分开讨论,是因为原题具有特殊之处,两种情况分别是等差递推和等比递推。 顺便我不知道 Euler 定理是否成立,在环上我不太会解多项式方程,也不太会化 Jordan 标准型。 蒟蒻拿得一把经验. P.S. 我是不是可以把这个做成下个学期的研学 = =
1 下一页