歐拉定理(Euler's Theorem)係數論入面嘅一條定理,由數學家歐拉證明。
主要討論係xm≡1modn{\displaystyle x^{m}\equiv 1\mod n}呢條式。
歐拉定理嘅基數同群入面嘅基數定義相似。
設n∈Z{\displaystyle n\in \mathbb {Z} } 同埋x∈Z{\displaystyle x\in \mathbb {Z} } 。
如果gcd(x,n)=1{\displaystyle \gcd(x,n)=1} ,xmodn{\displaystyle x\mod n} 嘅基數(Order)係最細嘅整數m{\displaystyle m} 符合xm≡1modn{\displaystyle x^{m}\equiv 1\mod n} 。
如果xi≡xjmodn{\displaystyle x^{i}\equiv x^{j}\mod n} ,咁xi−j≡1modn{\displaystyle x^{i-j}\equiv 1\mod n} 。
對應任何一個自然數x∈N{\displaystyle x\in \mathbb {N} } ,
例子:
φ(5)=#{1,2,3,4}=4{\displaystyle \varphi (5)=\#\{1,2,3,4\}=4}
φ(6)=#{1,5}=2{\displaystyle \varphi (6)=\#\{1,5\}=2}
φ(12)=#{1,5,7,11}=4{\displaystyle \varphi (12)=\#\{1,5,7,11\}=4}
對應任何質數p{\displaystyle p} ,φ(p−1)=#{1,2,⋯,p−1}=p−1{\displaystyle \varphi (p-1)=\#\{1,2,\cdots ,p-1\}=p-1} 。
如果gcd(x,n)=1{\displaystyle \gcd(x,n)=1} ,咁xφ(n)≡1modn{\displaystyle x^{\varphi (n)}\equiv 1\mod n} 。