오일러 피 함수(Euler's phi function)

정의1

서로소 판별함수 :

임의의 양의 정수 $m, n \in \mathbb{Z}^+$에 대해 $\mathbf{1}_n(m) = \begin{cases} 1 ,&  \gcd(m,n) = 1 \text{일때} \\ 0 ,&  \gcd(m,n) \ne 1 \text{일때}  \end{cases}$ 로 정의되는 

산술함수 $\mathbf{1}_n : \mathbb{Z}^+ \to \{ 0, 1 \}$를 $n$에 대한 서로소 판별함수로 정의한다.

오일러 피 함수 : 

모든 $n \in \mathbb{Z}^+$에 대해 $\phi(n) = \displaystyle \sum_{ m = 1}^n \mathbf{1}_n(m)$ 으로 

$n$과 서로소인 $n$보다 작거나 같은 양의 정수의 개수를 세는 산술함수 $\phi : \mathbb{Z}^+ \to \mathbb{Z}^+$를 오일러 $\phi$-함수로 정의한다.

최대공약수 정리로 모든 $n \in \mathbb{Z}^+$에 대해 $\gcd(n,1) = 1$이므로 $\phi(n) \ge 1$이다.

 

 

 

정리1

임의의 $n,m \in \mathbb{Z}^+$에 대한 서로소 판별함수 $\mathbf{1}_n ,\mathbf{1}_m : \mathbb{Z}^+ \to \{ 0, 1 \}$에 대해 다음이 성립한다.

1. $\mathbf{1}_n $은 완전 곱셈적이다.

2. $\mathbf{1}_n(m) = \mathbf{1}_m(n)$이다.

증명

1.

임의의 $m,k \in \mathbb{Z}^+$에 대해 $\mathbf{1}_n(m) = 1 = \mathbf{1}_n(k)$이면

$\gcd(m,n) = 1 = \gcd(k,n)$이므로 서로소 정리로 $\gcd(m\cdot k , n) = 1$이 되어 $\mathbf{1}_n(m) \cdot \mathbf{1}_n(k) =  1 = \mathbf{1}_n(m\cdot k)$이다.

$\mathbf{1}_n(m) \ne 1$ 또는 $\mathbf{1}_n(k) \ne 1$일때 일반성을 잃지 않고 $\mathbf{1}_n(m) \ne 1$이라 가정하면

$\mathbf{1}_n(m) = 0 $이므로 최대공약수의 정의로 $\gcd(m,n)  = d  > 1$에 대해 $m / d \in \mathbb{Z}$이고 $n/d \in \mathbb{Z}$이다.

또 $m = q\cdot d$인 $q \in \mathbb{Z}$가 존재하고 $m \cdot k = (q\cdot k) \cdot d$이므로 $(m\cdot k) / d \in \mathbb{Z}$가 되어

최대공약수의 정의로 $\gcd(m\cdot k, n) \ge d > 1$이고 $\mathbf{1}_n(m) \cdot \mathbf{1}_n(k) =  0 = \mathbf{1}_n(m\cdot k)$이다.

2.

최대공약수 정리로 $\gcd(m,n) = \gcd(n,m)$이므로 서로소 판별함수의 정의로 $\mathbf{1}_n(m) = \mathbf{1}_m(n)$이다.

 

 

 

정리2

오일러 $\phi$-함수에 대해 다음이 성립한다.

1. $k \ge 1$인 임의의 $a,k \in \mathbb{Z}$와 소수 $p$에 대해 $\gcd(a,p^k) = 1$이기 위한 필요충분조건은 $a /p \notin \mathbb{Z}$인 것이다.

2. 임의의 $k \in \mathbb{Z}^+$와 소수 $p$에 대해 $\phi(p^k) = p^k - p^{k-1} = p^k \cdot \left ( 1 - \dfrac{1}{p}\right )$이다.

3. $p\ge 2$인 $p \in \mathbb{Z}^+$가 소수이기 위한 필요충분조건은 $\phi(p) = p-1$인 것이다. 

4. $\phi(1) = 1$이고 $n \ge 2$인 모든 $n \in \mathbb{Z}^+$에 대해 $\phi(n)<n$이다.

증명

1.

$\gcd(a,p^k) = 1$일때 $a /p \in \mathbb{Z}$라고 가정하면

$p/p \in \mathbb{Z}$이므로 최대공약수의 정의와 소수의 정의로 $\gcd(a,p) \ge p> 1$인데

서로소 정리로 $\gcd(a,p) = 1$이 되어 모순이므로 $\gcd(a,p^k) = 1$이면 $a /p \notin \mathbb{Z}$이다.

역으로 $a /p \notin \mathbb{Z}$이면

소수의 정의로 $a/d, p/d \in \mathbb{Z}$인 $d \in \mathbb{Z}^+$는 $d = 1$ 또는 $d = p$인데 $a /p \notin \mathbb{Z}$이므로 $d \ne p$가 되어

$\gcd(a,p) = 1 = d$이고 서로소 정리로 $\gcd(a,p^k) = 1$이다.

2.

$m \le p^k$인 $m \in \mathbb{Z}^+$에 대해 1번의 대우로 $\gcd(m,p^k) \ne 1$이기 위한 필요충분조건은 $m /p \in \mathbb{Z}$이므로

$m / p \in \mathbb{Z}$이기 위한 필요충분조건은 서로소 판별함수가 $\mathbf{1}_{p^k}(m) = 0$인 것이 되어

$\mathbf{1}_{p^k}(m) = 0$인 모든 $m \le p^k$은 $m = q\cdot p$인 $q \in \mathbb{Z}^+$가 존재하고 $ q\cdot p = m \le p^k$로 $q \le p^{k-1}$이므로

$\displaystyle \sum_{q = 1}^{p^{k-1}}\mathbf{1}_{p^k}( q\cdot p) = 0$을 제외하면 오일러 $\phi$-함수는 $ \displaystyle \phi(p^k) =\sum_{m = 1}^{p^k} \mathbf{1}_{p^k}(m) = p^k - p^{k-1} = p^k \cdot \left ( 1 - \frac{1}{p}\right )$이다.

3.

$p\ge 2$인 $p \in \mathbb{Z}^+$가 소수이면 2번으로 $\phi(p) = \phi(p^1) = p^1 - p^0 = p -1$이다.

역은 대우로 증명한다.

$p\ge 2$인 $p \in \mathbb{Z}^+$가 소수가 아니면 소수의 정의로 $p/d \in \mathbb{Z}$일때 $d \ne 1$이고 $d \ne p$인 $d \in \mathbb{Z}^+$가 존재하여

약수 정리로 $p =|p|\ge |d| = d$이므로 $\gcd(p,p) \ge p > 1$이고 $\gcd(p,d) \ge d > 1$이다.

따라서 $\mathbf{1}_p(p) = 0$이고 $\mathbf{1}_p(d) = 0$이므로 $ \displaystyle \phi(p) =\sum_{m = 1}^{p} \mathbf{1}_{p}(m) \le p -2 < p -1$이다.

4.

최대공약수 정리로 $\gcd(1,1) = 1$이므로 서로소 판별함수가 $\mathbf{1}_1(1) = 1$이 되어 $\phi(1) = \displaystyle \sum_{m = 1}^1\mathbf{1}_1(1) = \mathbf{1}_1(1) = 1$이다.

3번으로 $n \ge 2$인 임의의 $n \in \mathbb{Z}^+$이 소수이면 $\phi(n) = n-1 < n$이고 $n$이 소수가 아니면 $\phi(n) \le n-2 < n$이다.

 

 

 

정리3

오일러 $\phi$-함수는 곱셈적이다.

증명

$\gcd(n,k) = 1$인 임의의 $n,k \in \mathbb{Z}^+$에 대해

위 정리로 $ \begin{align*}\phi(n\cdot k) = \sum_{m = 1}^{n\cdot k} \mathbf{1}_{n\cdot k}(m) = \sum_{m = 1}^{n\cdot k}\mathbf{1}_m(n\cdot k) = \sum_{m = 1}^{n\cdot k} \mathbf{1}_m(n)\cdot \mathbf{1}_m(k) = \sum_{m=1}^{n\cdot k}\mathbf{1}_{n}(m)\cdot \mathbf{1}_k(m) \end{align*}$이고

함수 정리로 $(x,y) \in \{ 1,2,\cdots,n \} \times \{ 1,2,\cdots, k \}$에 대해 $(y-1)\cdot n + x \in \{ 1,2,\cdots,n\cdot k \}$는 전단사이므로

$ \begin{align*}\phi(n\cdot k) =  \sum_{m=1}^{n\cdot k}\mathbf{1}_{n}(m)\cdot \mathbf{1}_k(m)  = \sum_{x = 1}^n \sum_{y = 1}^k \mathbf{1}_n((y-1)\cdot n + x)\cdot \mathbf{1}_k((y-1)\cdot n + x)\end{align*}$이다.

또 모듈로 연산 정리와 최대공약수 정리로

$\gcd((y-1)\cdot n +x, n) = \gcd(n, ((y-1)\cdot n + x) \bmod{n}) = \gcd(n,x\bmod{n})$이고

최대공약수 정리로 $\gcd(n,0) = \gcd(n,n)$이므로 $\gcd((y-1)\cdot n +x, n)  = \gcd(n,x\bmod{n}) = \gcd(n,x)$가 되어

$ \begin{align*}\phi(n\cdot k) & = \sum_{x = 1}^n \sum_{y = 1}^k \mathbf{1}_n((y-1)\cdot n + x)\cdot \mathbf{1}_k((y-1)\cdot n + x) \\[0.5em] & = \sum_{x = 1}^n \sum_{y = 1}^k \mathbf{1}_n(x) \cdot \mathbf{1}_k((y-1)\cdot n +x) \\[0.5em] & = \sum_{x = 1}^n \left ( \mathbf{1}_n(x) \cdot \left ( \sum_{y = 1}^k \mathbf{1}_k((y-1)\cdot n + x)\right) \right )  \text{ 이다.}\end{align*}$

임의의 $x \in \{ 1,2,\cdots, n\}$와 임의의 $y_1,y_2 \in \{ 1,2,\cdots, k \}$에 대해

$((y_1 - 1)\cdot n + x)\bmod{k}  = ((y_2-1) \cdot n + x) \bmod{k}$이면 모듈로 연산 정리로

$(y_1 - 1)\cdot n + x \equiv (y_2-1 ) \cdot n +x \pmod{k}$이고 $(y_1 - 1)\cdot n  \equiv (y_2-1 ) \cdot n  \pmod{k}$이므로

$\dfrac{k}{\gcd(n,k)} = k$에 대해 모듈로 합동 정리로 $y_1 -1 \equiv y_2 -1 \pmod{k}$가 되어 $y_1 -1 = y_2-1$이고 $y_1  = y_2$이다.

따라서 $x$에 상관없이 $y \in \{ 1,2,\cdots, k \}$에 대해 $((y-1) \cdot n + x) \bmod{k} \in \{ 0,1,\cdots, k-1\}$는 전단사이고

최대공약수 정리로 $\gcd(k,0) = \gcd(k,k)$이므로

$\gcd((y-1)\cdot n +x, k)  = \gcd(k,((y-1)\cdot n +x )\bmod{k}) = \gcd(k,j)$인 $j \in \{ 1,2,\cdots, k \}$가 존재하여

$ \begin{align*}\phi(n\cdot k)  & = \sum_{x = 1}^n \left ( \mathbf{1}_n(x) \cdot \left ( \sum_{y = 1}^k \mathbf{1}_k((y-1)\cdot n + x)\right) \right ) \\[0.5em] & = \sum_{x = 1}^n \left ( \mathbf{1}_n(x) \cdot \left ( \sum_{j = 1}^k \mathbf{1}_k(j)\right) \right ) \\[0.5em] & = \left (\sum_{i = 1}^n \mathbf{1}_n(i) \right )\cdot \left ( \sum_{j = 1}^k \mathbf{1}_k(j)\right) \\[0.5em] & = \phi(n)\cdot \phi(k) \text{ 이다.}\end{align*}$

 

 

 

정리4

오일러 $\phi$-함수와 $n \ge 2$인 임의의 $n \in \mathbb{Z}^+$에 대해 $n = p_1^{m_1} \cdot p_2^{m_2} \cdot \; \cdots \; \cdot p_k^{m_k}$가 되는

서로 다른 소수 $p_1, p_2,\cdots, p_k \in \mathbb{Z}^+$와 중복가능한 $m_1, m_2,\cdots, m_k \in \mathbb{Z}^+$가 존재하면

$\begin{align*}\phi(n) & = \left( p_1^{m_1} - p_1^{m_1 -1}\right)\cdot \left( p_2^{m_2} - p_2^{m_2 -1}\right) \cdot \; \cdots \; \cdot \left( p_k^{m_k} - p_k^{m_k -1}\right) \\[0.5em] & = n\cdot \left ( 1 -\frac{1}{p_1} \right ) \cdot \left ( 1 -\frac{1}{p_2} \right )\cdot \; \cdots \; \cdot\left ( 1 -\frac{1}{p_k} \right ) \text{ 이다.} \end{align*} $

증명

위 정리로 $\phi$는 곱셈적이므로 산술함수 정리와 위 정리로

$\begin{align*}\phi(n)  & = \phi(p_1^{m_1}) \cdot \phi( p_2^{m_2}) \cdot \; \cdots \; \cdot \phi(p_k^{m_k}) \\[0.5em] & = \left( p_1^{m_1} - p_1^{m_1 -1}\right)\cdot \left( p_2^{m_2} - p_2^{m_2 -1}\right) \cdot \; \cdots \; \cdot \left( p_k^{m_k} - p_k^{m_k -1}\right) \\[0.5em] & = \left( p_1^{m_1} \cdot p_2^{m_2} \cdot \; \cdots \; \cdot p_k^{m_k} \right )\cdot \left ( 1 -\frac{1}{p_1} \right ) \cdot \left ( 1 -\frac{1}{p_2} \right )\cdot \; \cdots \; \cdot\left ( 1 -\frac{1}{p_k} \right ) \\[0.5em] & = n\cdot \left ( 1 -\frac{1}{p_1} \right ) \cdot \left ( 1 -\frac{1}{p_2} \right )\cdot \; \cdots \; \cdot\left ( 1 -\frac{1}{p_k} \right ) \text{ 이다.} \end{align*} $

 

 

 

정리7

오일러 $\phi$-함수와 $n \ge 3$인 임의의 $n \in \mathbb{Z}^+$에 대해 $\phi(n)$은 짝수이다.

증명

산술의 기본정리로 $n = p_1^{m_1} \cdot p_2^{m_2} \cdot \; \cdots \; \cdot p_k^{m_k}$이고 $p_1<p_2<\cdots < p_k$인

소수 $p_1, p_2,\cdots, p_k \in \mathbb{Z}^+$와 중복가능한 $m_1, m_2,\cdots, m_k \in \mathbb{Z}^+$가 존재하고

위 정리로 $\phi$는 곱셈적이므로 산술함수 정리와 위 정리로

$\phi(n)   = \phi(p_1^{m_1}) \cdot \phi( p_2^{m_2}) \cdot \; \cdots \; \cdot \phi(p_k^{m_k})  = \left( p_1^{m_1} - p_1^{m_1 -1}\right)\cdot \phi( p_2^{m_2}) \cdot \; \cdots \; \cdot \phi(p_k^{m_k})   $이다.

$p_1 = 2$이면

$\phi(n)  = \left( 2^{m_1} - 2^{m_1 -1}\right)\cdot \phi( p_2^{m_2}) \cdot \; \cdots \; \cdot \phi(p_k^{m_k}) = 2^{m_1} \cdot \left (1 -\dfrac{1}{2} \right ) \cdot \phi(p_2^{m_2})\cdot \; \cdots \; \cdot \phi(p_k^{m_k}) =  2^{m_1-1} \cdot \phi( p_2^{m_2}) \cdot \; \cdots \; \cdot \phi(p_k^{m_k}) \text{ 이므로}$

$m_1 \ge 2$일때 $\phi(n)  =2\cdot  2^{m_1 - 2} \cdot \phi( p_2^{m_2}) \cdot \; \cdots \; \cdot \phi(p_k^{m_k})$로 $\phi(n)$은 짝수이고

$m_1 = 1$일때 $n \ge 3$이므로 $p_1 =2 < p_2$가 존재하여 소수 정리로 $p_2$는 홀수이므로 홀짝 정리로 $p_2 - 1$은 짝수이고

$\phi(n)  =   2^{m_1-1} \cdot ( p_2^{m_2} - p_2^{m_2 -1}) \cdot \phi(p_3^{m_3})\cdot \; \cdots \; \cdot \phi(p_k^{m_k}) = p_2^{m_2-1} \cdot (p_2 -1) \cdot \phi(p_3^{m_3}) \cdot \; \cdots \; \cdot \phi(p_k^{m_k}) $가 되어

$\phi(n)$은 짝수이다.

$p_1 \ne 2$일때 $2< p_1$이므로 비슷하게 $\phi(n)  =  p_1^{m_1-1} \cdot (p_1 -1) \cdot \phi(p_2^{m_2}) \cdot \; \cdots \; \cdot \phi(p_k^{m_k}) $가 되어 $\phi(n)$은 짝수이다.

 

 

 

정리5

오일러 $\phi$-함수와 $n \ge 2$이고 $\gcd(a,n)$ $= 1$인 임의의 $a,n \in \mathbb{Z}$에 대해 

서로 다른 양의 정수 $a_1,a_2,\cdots,a_{\phi(n)} \in \mathbb{Z}^+$이 모든 $i = 1,2,\cdots, \phi(n)$에 대해 $a_i < n$이고 $\gcd(a_i,n) = 1$이면

$a\cdot a_i \equiv a_{j_i} \pmod{n}$인 $j_i = 1,2,\cdots, \phi(n)$가 존재하고 $u \ne v$인 모든 $u,v = 1,2,\cdots,\phi(n)$에 대해 $a_{j_u} \ne a_{j_v}$이다.

증명

$\gcd(a,n) =1$이고 모든 $i = 1,2,\cdots, \phi(n)$에 대해 $\gcd(a_i,n) = 1$이므로

서로소 정리로 $\gcd(a\cdot a_i,n) = 1$이 되어 최대공약수 정리로 $1= \gcd(a\cdot a_i,n) = \gcd((a\cdot a_i)\bmod{n},n)$이고

$n\ge 2$이므로 모듈로 연산의 정의로 $0< (a\cdot a_i) \bmod{n} < n$이다.

따라서 최대공약수 정리로 $\gcd(n,n) = n > 1$이므로

오일러 $\phi$-함수의 정의로 $a_i < n$이고 $\gcd(a_i,n) = 1$인 $a_i \in \mathbb{Z}^+$는 $\phi(n)$개 존재하여

$a_{j_i}\bmod{n} =a_{j_i}  =(a\cdot a_i) \bmod{n} $인 $j_i = 1,2,\cdots, \phi(n)$가 존재하고

모듈로 연산 정리로 $a\cdot a_i \equiv a_{j_i} \pmod{n}$이다.

또 $u \ne v$인 모든 $u,v = 1,2,\cdots,\phi(n)$에 대해 $a\cdot a_u \equiv a\cdot a_v \pmod{n}$이면

$\dfrac{n}{\gcd(a,n)} = n$에 대해 모듈로 합동 정리로 $a_u \equiv a_v \pmod{n}$가 되어 $a_u,a_v < n$임에 따라 $a_u = a_v$로 모순이므로

$a\cdot a_u \not\equiv a\cdot a_v \pmod{n}$가 되어 모듈로 연산 정리로 $a_{j_u} =(a\cdot a_u) \bmod{n} \ne (a\cdot a_v) \bmod{n} = a_{j_v}$이다.

 

 

 

정리6(오일러[Euler] 정리)

오일러 $\phi$-함수와 임의의 $a \in \mathbb{Z}$에 대해 다음이 성립한다.

1. $\gcd(a,n)$ $= 1$인 모든 $n \in \mathbb{Z}^+$에 대해 $a^{\phi(n)}\equiv 1 \pmod{n}$이다.

2. 임의의 $k \in \mathbb{Z}^+$와 $a / p\notin \mathbb{Z}$인 임의의 소수 $p \in \mathbb{Z}^+$에 대해 $a^{\phi(p^k)}\equiv 1 \pmod{p^k}$이다.

증명

1.

$n= 1$이면 $(a^{\phi(1)} -1 )/1 \in \mathbb{Z}$이므로 $a^{\phi(1)}\equiv 1 \pmod{1}$이다.

$n\ge 2$이면 최대공약수 정리로 $\gcd(n,n) = n > 1$이므로 오일러 $\phi$-함수의 정의로 모든 $i = 1,2,\cdots, \phi(n)$에 대해 

$a_i < n$이고 $\gcd(a_i,n) = 1$인 $\phi(n)$개의 서로 다른 양의 정수 $a_1,a_2,\cdots,a_{\phi(n)} \in \mathbb{Z}^+$가 존재하여

위 정리로 $a \cdot a_i \equiv a_{j_i} \pmod{n}$인 $j_i = 1,2,\cdots, \phi(n)$가 존재하고 곱셈 정리로

$(a \cdot a_1)\cdot (a\cdot a_2) \cdot \; \cdots \; \cdot (a\cdot a_{\phi(n)}) \equiv a_1\cdot a_2 \cdot \; \cdots \; \cdot a_{\phi(n)} \pmod{n}$이 되어

$a^{\phi(n)} \cdot (a_1\cdot  a_2 \cdot \; \cdots \; \cdot a_{\phi(n)}) \equiv a_1\cdot a_2 \cdot \; \cdots \; \cdot a_{\phi(n)} \pmod{n}$이다.

따라서 서로소 정리로 $\gcd(a_1\cdot  a_2 \cdot \; \cdots \; \cdot a_{\phi(n)},n) = 1$이므로 

$\dfrac{n}{\gcd(a_1\cdot a_2 \cdot \; \cdots \; \cdot a_{\phi(n)},n)} = n$에 대해 모듈로 합동 정리로 $a^{\phi(n)} \equiv 1 \pmod{n}$이다.

2.

$a/p \notin \mathbb{Z}$이므로 위 정리로 $\gcd(a,p^k) = 1$이 되어 1번으로 $a^{\phi(p^k)}\equiv 1 \pmod{p^k}$이다.

 

 

 

-------------------------------------------------------------------------------

정의의 링크 : 

https://openknowledgevl.tistory.com/64#def번호

번호는 해당 정의 옆에 붙어있는 작은 숫자입니다.

 

정리의 링크 : 

https://openknowledgevl.tistory.com/64#thm번호

번호는 해당 정리 옆에 붙어있는 작은 숫자입니다.

 

위 내용은 아래의 출처를 기반으로 정리한 내용입니다.

틀린 내용이 존재할 수 있습니다.

 

출처(저자 - 제목 - ISBN13)

David M. Burton - Elementary Number Theory - 9780073383149