[이산수학] Euler's Phi Function (오일러 피 함수)

• complete set of residues : 1보다 큰 자연수 n에 대해 어떤 정수들의 집합의 원소들을 n으로 나눴을때 나머지가 모두 다를 때
• reduced set of residues : complete set of residues 중에서 n과 서로소인 수들의 집합
• ex) n = 10일 때
  • complete set of residues {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
  • reduced set of residues : {1, 3, 7, 9}
• reduced set of residues의 원소의 수를 Euler Phi (Totient) Function $ \phi (n) $ 이라고 한다. 
• $\phi (10) = 4$ 이고 그 집합은 {1, 3, 7, 9}가 된다.

 

정의

1부터 n 까지의 정수 가운데 n 과 서로소인 원소 m의 개수

$p_1, ..., p_t$이 서로 다른 소수이고 1이상 t미만의 모든 i에 대해 $e_i \geq 1$ 이면

 

$$ n = \prod_{i=1}^{t} p_i^{e_i}$$

$$ {\displaystyle \phi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right)} $$

 

예를 들어 20의 소인수는 2, 5 이므로 $ {\displaystyle \phi (20)=20\left(1-{\frac {1}{2}}\right)\left(1-{\frac {1}{5}}\right)=20\times {\frac {1}{2}}\times {\frac {4}{5}}=8} $ 이 된다.

 

따름 정리

p는 소수이고 e는 1이상일 때

$ n = p^e$ 일 때 $ \phi(n) = p^{e - 1} (p - 1)  $

$ n = p $ 일 때 $\phi(n) = n - 1 $

 

• ex) $ \phi(27) = 3^2(3 - 1) = 18 $ , $\phi(11) = 11 - 1 = 10$

만약 gcd(m, n) = 1 (m과 n이 서로소) 이면, $\phi(mn) = \phi(m)\phi(n)$

 

• ex) $\phi(270) = (2 - 1) (5 - 1)(3^3 - 3^2) = 4 \cdot 18 = \phi(10) \phi(27) $
• m과 n의 서로소라면 공통된 소인수들을 갖지 않기 때문에 m과 n을 곱한 mn은 m과 n의 서로소들을 모두 포함한다.

 

$Z_n^*$ VS $ \phi(n) $

정의

$Z_n^*$ 은 n과 서로소인 숫자들의 집합이다.

$Z_n^*$의 크기는 $\phi(n)$의 값과 같다.

 

$Z_{15}^*$의 곱셈 테이블

모든 원소들이 항등원이 되는 값을 가진다. => 역원이 존재한다.

Closure(닫힘성), Associative(결합법칙), Identity(항등원), Inverse(역원), Commtative(교환법칙)를 만족하는 Abelian Group이다.

 

일반적으로 1보다 큰 양수 n에 대해 

• $\phi(n)$ 개의 Unit
• $n - 1 - \phi(n)$ 개의 zero divisor가 존재한다.