线性代数1

数论相关知识点：

Q1：为什么由费马小定理可以得出 \(a^{-1}\equiv a^{P-2}(\mod P)\)

线性代数：

1. 费马小定理

首先明确一个事情，当 \(a\) 不为 \(P\) 的倍数的时候，不存在 \(x\neq y,1\leq x,y<p\)，使得 \(xa\equiv ya \ (\bmod P)\)

因为如果条件成立，则 \(x\mod P=y\mod P\)，又因为 \(x\neq y\) 不符合条件。

我们仔细一想，发现 \(\forall x\in[1,P-1],ax\%P\) 皆不相等。则 \(ax\) 在 \(\mod P\) 意义下仍为 \(1\sim P-1\)

所以 \(\prod\limits_{i=1}^{P-1}i\equiv \prod\limits_{i=1}^{P-1}ai \ (\bmod P)\)

又因为 \(\prod\limits_{i=1}^{P-1}i\) 显然不是 \(P\) 的倍数，所以：\(a^{P-1}\equiv1 \ (\bmod P)\)

注意：此定理仅适用于P为质数且a不是P的倍数的时候

\({\uppercase\expandafter{\romannumeral2} }\)

同时我们可以通过费马小定理，解决逆元问题。当 \(P\) 为质数的时候， \(a^{P-1}\equiv 1 \ (\bmod P)\Rightarrow a^{-1}\equiv a^{P-2} \ (\bmod P)\)

总结到这里的时候，想到一个十分常用的东西 \(a^x\equiv a^{x\%(P-1)} \ (\bmod P)\)

发现 \(a^x\equiv a^{x\%(P-1)}\times a^{t\times (P-1)} \ (\bmod P)\) 我们根据费马小定理，可以得出 \(a^x\equiv a^{x\%(P-1)} \ (\bmod P)\)

2.