欧拉定理CRT学习笔记
欧拉定理CRT学习笔记
前置知识：
\(1,\)数论欧拉定理(这里)[https://www.cnblogs.com/wangxiaodai/p/9758242.html]
\(2,\)积性函数\(\phi\)的性质
\(3,\)以下引理
证明引理用到的引理
(一)，引理
设\(x\)=\(lcm(a,b)\)。
可以分解如下
\[
a=p_1^{a_1}*……*p_k^{a_k}\\b=p_1^{b_1}*……*p_k^{b_k}
\]
那么可得：
\[
x=p_1^{max(a_1,b_1)}*……*p_k^{max(a_k,b_k)}
\]
证明：推倒上面的式子，将指数可加解释到整体的乘除法，同理取max也是一样。
或者手推几个数。
引理
(一)，
已知
\[
\begin{cases}
x\equiv y(mod m_1)\\
x\equiv y(mod m_2)
\end{cases}
\]
可得：
\[
x\equiv y(mod lcm(m1,m2))
\]
引理一证明：
可以对\(x,m1,m2\)进行分解：
\[
\begin{cases}
x= p_1^{a_1}*……*p_k^{a_k}\\
m1=p_1^{b_1}*……*p_k^{b_k}\\
m2=p_1^{c_1}*……*p_k^{c_k}
\end{cases}
\]
又因为：
\[
\begin{cases}
x％m_1=p_1^{a_1％b_1}*……*p_k^{a_k％b_k}=y\\x％m_2=p_1^{a_1％c_1}*……*p_k^{a_k％c_k}=y
\end{cases}
\]
那么对于\(y\)可以有唯一分解定理解得：
\[
a_i％b_i=a_i％c_i
\]
稍加分析就可以得到：
\[
x％lcm(m1,m2)=p_1^{a_1％max(b_1,c_1)}*……*p_k^{a_k％max(b_k,c_k)}=y
\]
即证得：
\[
x\equiv y(mod lcm(m1,m2))
\]
(二)，
在p是质数的前提下
\[
\phi(p^q)=p^q-p^{q-1}\geq q
\]
引理二的证明也是非常的妙妙啊。
引理二证明
小于等于\(p^q\)的正整数一共有\(p^q-1\)个，其中不与\(p^q\)互质的是\(p,p*2,p*3,p^q-p=(p^{q-1}-1)*p\)这\(p^{q-1}-1\)个数。
那么就可以得到\(\phi(p^q)=p^q-p^{q-1}\)
妙妙
另外在正式证明之前还要提一句\(\phi\)的性质：
在n和m互质的前提下，存在
\[
\phi(n*m)=\phi(n)*\phi(m)
\]
正式证明
首先先来回顾一下我们要证得是什么？
欧拉定理CRT
先把式子放出来：
\[
a^b \equiv\begin{cases}
a^{b％\phi(m)} (gcd(a,m)==1)\\
a^b (gcd(a,m) !=1 ＆b<\phi(m))\\
a^{b％\phi(m)+\phi(m)} (gcd(a,m)!=1＆b\geq\phi(m))
\end{cases}(mod m)
\]
然后很容易发现这三个式子都可以用第三个式子表示，也就是在满足任何数的意义下，存在扩展欧拉定理：
\[
a^b\equiv a^{b％\phi(m)+\phi(m)}(mod m)
\]
开始愉快地证明吧：
首先我们假设模数\(m=p^q\)，那么很容易知道\(a\)和\(m\)的同余性是可以推至\(a\)和\(p\)的，当然反推也可以。
那么就开始最美妙的分情况讨论时间了：
(1)，\(gcd(a,p)==1\)时，求证：
\[
a^b \equiv a^{x％\phi(p^q)}(mod p^q)
\]
这就不证了，很明显的欧拉定理式子。
(2)，\(gcd(a,p)!=1\)也就是\(gcd(a,p)==p\)。 因为p是质数啊喂
那么我们另\(a=k*p\)。
那么就是求证：
\[
(k*p)^b \equiv (k*p)^{b％\phi(p^q)+\phi(p^q)}(mod p^q)
\]
因为\(b\geq\phi(p^q)\) 根据引理二可以知道\(b\geq q\)
所以可以得到：
\[
p^b％p^q=0
\]
所以又可以得到：
\[
a^b=(k*p)^b \equiv 0 (mod p^q)
\]
又因为\(\phi(p^q)\geq q\)，所以又可得：
\[
a^{b％\phi(m)+\phi(m)}\equiv 0 (mod p^q)
\]
那么到了这里，就已经证毕。
即证得：
\[
a^b \equiv a^{b％\phi(m)+\phi(m)}(mod p_q)
\]
又因为\(\phi\)函数的积性，可以将上述结论推至对所有模数m都成立。