欧拉定理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都成立。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpszfg.html