在本文中，使用$(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$为素数。
根据条件有：
因此：
证毕
推论
- 当$(m_1,m_2)=1$时，$x\equiv y\pmod {m_1m_2}$
- 当有多个同余式时：
- 当$(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$成立。
