정수론 #4-2 :: 오일러 정리

Euler’s theorem

오일러 정리 = 페르마 소정리의 일반화.

 

$\begin{gather*}\gcd(a,k)=1 \end{gather*}$

 

$\begin{gather*}a^{\phi(k)}≡1 \mod k \end{gather*}$

• Φ(k) : Euler phi Function
  {1, 2, … ,(k-1)} 중 k와 서로소인 원소의 개수.
  이때 gcd(a, k) = 1이므로 a로는 그 서로소인 원소들만 될 수 있다.
• k : prime인 경우엔? 
  Φ(p) = p - 1
  당연히 1 ~ p-1 전부 p와 서로소이기 때문. ⇒ 페르마 소정리.

 

• gcd(a, k) = 1 ↔ ax ≡ 1 mod k for some x
  이유) ax - 1 = ky
  ⇒ ax - ky = 1
  의 해가 존재하려면 gcd(a, k) =1이여야 하기 때문. ⇒ 따라서 필요충분조건.

---

 

p to the power of k

$\begin{gather*}\phi(p^k)=p^{k-1}(p-1) \end{gather*}$

 

증명

$\begin{gather*}\begin{bmatrix} 1,&2,&...&p-1,&p\\ p+1,&p+2,&...&2p-1,&2p \\ 2p+1,&&...&&3p \\ &&...\\ (p^{k-1}-1)p+1,&&...&p^{k-1}p-1,&p^{k-1}p=p^k \end{bmatrix} \end{gather*}$

 

이중 p^k와 서로소가 아닌수는 p, 2p, 3p, …, p^k이다. (p가 들어있기 때문)

⇒ 행의 개수만큼 존재하므로 p^{k-1}개.

따라서

 

$\begin{gather*}\therefore \phi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1) \end{gather*}$

 

---

 

Proposition

$\begin{gather*}\gcd(m,n)=1 \Rightarrow \phi(mn)=\phi(m)\phi(n) \end{gather*}$

 

증명

전제

$\begin{gather*}\gcd(m,n)=1\\ I_m:=\{1\le a\le m-1 | \gcd(a,m)=1 \} \\ \phi(m) = |I_m| \end{gather*}$

 

사실

$\begin{gather*}\gcd(a,mn)=1 \leftrightarrow \gcd(a,m)=1, \ \ \ \ \gcd(a,n)=1 \end{gather*}$

⇒ 즉, a가 I_mn의 원소라면, a는 I_m의 원소이면서 I_n의 원소이다.

 

Φ(mn) = Φ(m)Φ(n) 임을 증명하기 위해선 |I_mn| = |I_m X I_n| 임을 보이면 된다.

두 집합의 크기가 동일하다는 것은 두 집합간의 일대일 대응이 가능하다는 것이기 때문에

일대일 대응을 보일 수 있다면 Proposition를 증명할 수 있다.

 

이때 사실에 의하여 a가 I_mn의 원소라면, a는 I_m의 원소이면서 I_n의 원소임이 보장된다.

 

$\begin{gather*}f:I_{mn}\rightarrow I_m \times I_n \end{gather*}$

 

위와 같은 일대일 대응 함수는 아래와 같이 존재한다.

 

$\begin{gather*}f(a)=(a_1, a_2) \end{gather*}$

 

f는 I_mn의 원소 a가 I_m의 원소 a1과 I_n의 원소 a2 순서쌍(a1, a2)에 대응되는 함수이다.

이 함수는 일대일 대응이기 때문에 이러한 a는 유일하고, 존재해야만 한다.

 

$\begin{gather*}\begin{cases} a\equiv a_1 \mod m \ \ \ \ 0\le a_1\le m-1 \\ a \equiv a_2 \mod n \ \ \ \ 0 \le a_2 \le n-1 \end{cases} \end{gather*}$

 

중국인의 나머지정리에 의하여 그런 a는 유일하게 존재한다.

 

a는 I_mn의 원소이고, (a1, a2) 순서쌍은 I_m X I_n의 원소이다.

 

따라서 (a1, a2)을 만족하는 a는 I_mn에서

유일하게 (단사 : injective)

존재한다. (전사 : surjective)

양쪽으로 만족되는 전단사(bijective) 함수이기에 일대일 대응이다.

 

$\begin{gather*}f:I_{mn}\rightarrow I_m \times I_n \end{gather*}$

 

그러므로 위가 성립한다. 즉, 두 집합은 크기가 같다.

 

$\begin{gather*}|I_{mn}|=|I_m\times I_n|\\\Rightarrow\phi(mn)=\phi(m)\phi(n) \end{gather*}$

 

---

 

Theorem

$\begin{gather*}n=p_1^{r_1}p_2^{r_2}...p_l^{r_l} \\ \Rightarrow\phi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_l}) \end{gather*}$

 

증명

Proposition에 의하여 아래가 성립한다.

 

$\begin{gather*}\phi(n)=\phi(p_1^{r_1})\phi(p_2^{r_2})...\phi(p_l^{r_l}) \end{gather*}$

 

p to the power of k에 의하여 다음이 성립한다.

 

$\begin{gather*}=p_1^{r_1-1}(p_1-1)p_2^{r_2-1}(p_2-1)...p_l^{r_l-1}(p_l-1) \\ =p_1^{r_1}(1-\frac{1}{p_1})p_2^{r_2}(1-\frac{1}{p_2})...p_l^{r_l}(1-\frac{1}{p_l})\\ = n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_l}) \end{gather*}$

 

---

 

Euler’s theorem Proof

$\begin{gather*}\gcd(b,k)=1 \Rightarrow b^{\phi(k)}\equiv 1 \mod k \end{gather*}$

 

증명

페르마 소정리 증명처럼 아래를 만족하는 일대일 대응을 찾으면 된다.

 

$\begin{gather*}I_k \leftrightarrow bI_k=\{ba \mod k|a\in I_k\} \end{gather*}$

 

$\begin{gather*}\Rightarrow a \leftrightarrow ba', \ \ \ \ a\equiv ba' \mod k \end{gather*}$

 

위를 만족하는 일대일 대응이 가능하려면 해가 유일하게 존재해야 한다.

따라서 b와 k는 서로소여야 한다.

이유) a ≡ ba’ mod k의 해가 하나만 존재하려면 ba’ - ky ≡ a 에서 gcd(b, k) = 1 여야 하므로.

 

즉, b와 k가 서로소라면 집합 I_k와 bI_k는 a ≡ ba’ mod k를 만족하면서 일대일 대응이된다.

따라서 아래가 성립한다.

 

$\begin{gather*}\Rightarrow \prod_{a\in I_k}a ≡\prod_{a\in I_k}ba= b^{\phi(k)}\prod_{a\in I_k}a \mod k \\ \because a≡b, \ \ c≡d \mod m \Rightarrow ac≡bd \mod m \end{gather*}$

 

I_k의 원소(a)는 k와 서로소 이므로 양변을 나눠도 된다.

 

$\begin{gather*}\Rightarrow \not{\prod_{a\in I_k}a} ≡ b^{\phi(k)}\not{\prod_{a\in I_k}a} \mod k \\ \therefore 1 ≡b^{\phi(k)} \mod k \end{gather*}$