(扩展)欧拉定理学习笔记 | Bill Yang's Blog

(扩展)欧拉定理学习笔记

在本文中,使用$(x,y)$代表$x,y$的最大公约数,$[x,y]$代表$x,y$的最小公倍数。

数论欧拉定理

有很多定理都叫欧拉定理,本文的欧拉定理特指数论中的欧拉定理,即:

其证明参考这里

费马小定理

费马小定理是欧拉定理的一个特例。
当$p$是素数的时候。

上述两个定理在数论中经常用到,其中费马小定理用处最大。

扩展欧拉定理

其中$a$是任意整数,$x,m$是正整数。
该定理可以简写为:

其中$x\ge\varphi(m)$,不要求$(a,m)=1$。

证明

前置技能

积性函数性质

$\varphi(nm)=\varphi(n)\varphi(m)\quad(n,m)=1$
因为$\varphi$是积性函数,因此成立。

引理1

证明如下:
分解$x,y,m_1,m_2$得到:

其中$p_i$为素数。
根据条件有:

因此:

证毕

推论
  1. 当$(m_1,m_2)=1$时,$x\equiv y\pmod {m_1m_2}$
  2. 当有多个同余式时:
  3. 当$(m_1,m_2,\ldots,m_n)=1$时:

引理2

$p$是任意素数,$q$是大于$1$的正整数,有$\varphi(p^q)\ge q$。
此处证明过的结论:

证明正文

假设$m=p^q$

  • 当$(a,p)=1$时 证明:
    根据欧拉定理,$a^{\varphi(p^q)}\equiv1\pmod {p^q}$。
    证毕。
  • $(a,p)\neq1$,即$(a,p)=p$
    令$a=kp$。
    因为$x\ge\varphi(m)$,因此根据引理2,$x\ge q$,因此$a^x\equiv0\pmod{p^q}$。
    又因为$\varphi(m)\ge q$,因此$a^{x\bmod\varphi(m)+\varphi(m)}\equiv0\pmod{p^q}$。
    因此$a^x\equiv a^{x\bmod\varphi(m)+\varphi(m)}\pmod{p^q}$

$m$为任意数

根据$\varphi$的积性性质,将$m$拆分为素数幂的乘积,又因为有引理1的推论3,因此结论

对任意$m$成立。

参考资料

本篇文章有用吗?有用还不快点击!
0%