初等数论的课堂笔记：第三章欧拉函数

欧拉函数

• 定义
  • 引理1: 假设p为素数，且e\in {{\mathbb{Z}}_{>0}}，则可得\varphi \left( {{p}^{e}} \right)={{p}^{e}}-{{p}^{e-1}}={{p}^{e-1}}\left( p-1 \right)。特别地，\varphi \left( p \right)=p-1
  • 引理2: 若a,n\in {{\mathbb{Z}}_{>0}}，则\gcd \left( a,n \right)=1等价于存在b\in \mathbb{Z}使得ab\equiv 1\left( \bmod n \right)
  • 引理3: 若a,m,n\in {{\mathbb{Z}}_{>0}}，则\gcd \left( a,m \right)=\gcd \left( a,n \right)=1等价于\gcd \left( a,mn \right)=1
  • 引理4: 当m,n\in {{\mathbb{Z}}_{>0}}且\gcd(m,n)=1时，则有\varphi (mn) = φ(m)φ(n)
  • • 推广：若m∈{{ℤ}_{>0}}的素因数分解形式为m={{p}{1}}{{e}{1}}}{{p}{2}}{{e}{2}}}...{{p