歐拉定理

歐拉定理（Euler's Theorem）係數論入面嘅一條定理，由數學家歐拉證明。

主要討論係${\displaystyle x^{m}\equiv 1\mod n}$呢條式。

基數

歐拉定理嘅基數同群入面嘅基數定義相似。

設${\displaystyle n\in \mathbb {Z} }$同埋${\displaystyle x\in \mathbb {Z} }$。

如果${\displaystyle \gcd(x,n)=1}$，${\displaystyle x\mod n}$嘅基數（Order）係最細嘅整數${\displaystyle m}$符合${\displaystyle x^{m}\equiv 1\mod n}$。

推論

如果${\displaystyle x^{i}\equiv x^{j}\mod n}$，咁${\displaystyle x^{i-j}\equiv 1\mod n}$。

歐拉 φ {\displaystyle \varphi } 函數

對應任何一個自然數${\displaystyle x\in \mathbb {N} }$，$${\displaystyle \varphi (x):=\#\{x\in \mathbb {Z} :a\leq n{\text{ and }}\gcd(a,n)=1\}}$$佢嘅意思係，揀一個數${\displaystyle x\in \mathbb {N} }$，數下有幾多數係細過${\displaystyle x}$又同時唔係${\displaystyle x}$嘅因數。

例子：

${\displaystyle \varphi (5)=\#\{1,2,3,4\}=4}$

${\displaystyle \varphi (6)=\#\{1,5\}=2}$

${\displaystyle \varphi (12)=\#\{1,5,7,11\}=4}$

推論

對應任何質數${\displaystyle p}$，${\displaystyle \varphi (p-1)=\#\{1,2,\cdots ,p-1\}=p-1}$。

歐拉定理

如果${\displaystyle \gcd(x,n)=1}$，咁${\displaystyle x^{\varphi (n)}\equiv 1\mod n}$。

睇埋

• 同餘
• 商餘
• 線性商餘方程