오일러 $\phi$ 함수

Definition 7.1

주어진 $n \ge 1$ 에 대해 $\phi(n)$은 $n$과 서로소이면서 $n$ 이하인 자연수의 개수이다.

특히, $gcd(1,1)=1$ 이므로 $\phi(1)=1$, 소수는 자기 자신으로만 나뉘어지므로 $\phi(p)=p-1$ 임에 주목한다.

$\because$ 서로소의 정의에 의해 $1$은 자기 자신과 서로소이다.

$\phi(n)=n-1$ 인 것은 $n$이 소수다와 동치이다.

증명

$n$이 합성수라고 할 때, $1 < d < n$ 을 만족하는 진약수 $d$가 존재하여 $\phi(n) \le n-2$ 가 되기 때문에 $\phi(n)=n-1$ 이 되려면 $n$이 소수여야만 한다. $\square$

오일러 $\phi$함수와 소인수분해를 이용한 계산법

Theorem 7.1

$p$가 소수이고 $k > 0$이면,

$$ \phi(p^k)=p^k-p^{k-1} $$

증명

$gcd(n,p^k)=1$ 일 조건은 $p \nmid n$ 이다.

$1$부터 $p^k$ 까지 $p$의 배수는 정확히 $p^{k-1}$개이다.

$\because ~~ \overbrace{ p,2p,\dots,p^{k-1} \cdot p }^{p^{k-1} \text{개}}$

따라서 이 수들을 제외한 개수는

$$ \phi(p^k)=p^k-p^{k-1} $$

$\square$

오일러 $\phi$함수의 승법성

Lemma

주어진 정수 $a,b,c$에 대해 $gcd(a,bc)=1$ 일 필요충분조건은 $gcd(a,b)=1$ 그리고 $gcd(a,c)=1$ 이다.

증명

$gcd(a,bc)=1$ 이라 가정하고, $d=gcd(a,b)$ 라 놓자.

$d \mid a,~~ d \mid bc$ 이므로 $gcd(a,bc) \ge d$ 임을 의미하고, $gcd(a,bc)=1$ 이므로 $d=1$ 임을 강제한다.

$gcd(a,c)=1$ 도 동일하게 유도할 수 있다.

역 증명

$gcd(a,b)=1, gcd(a,c)=1$ 일 때, $gcd(a,bc)=d_1>1$ 이라 가정하자.

$d_1$이 가지는 소인수 $p$가 $p \mid a, ~~ p \mid bc$ 이므로 $p \mid b$ 혹은 $p \mid c$ 여야 한다.

이 때, $gcd(a,b)$ 혹은 $gcd(a,c)$ 는 $p$가 되므로 모순이다.

즉, $gcd(a,bc)=1$ 이다. $\square$

Theorem 7.2

$\phi$는 승법 함수이다.

증명

$m \perp n$ 일 때, $\phi(mn)=\phi(m)\phi(n)$ 임을 보이자.

다음과 같은 수들의 격자식 배열을 고려한다.

$$ \begin{matrix} 1&2&\cdots & r & \cdots & m \\ m+1 & m+2 & \cdots & m+r & \cdots & 2m \\ 2m+1 & 2m+2 & \cdots & 2m+r & \cdots & 3m \\ \vdots \\ (n-1)m+1 & (n-1)m+2 & \cdots & (n-1)m+r & \cdots & nm \end{matrix} $$

$n$행 $m$열을 갖는다.

유클리드 호제법으로 $gcd(qm+r,m)=gcd(r,m)$이므로 어떤 $r$열의 수들이 $m$과 서로소일 조건은 $gcd(r,m)=1$ 이다.

또한 해당 열의 모든 수들은 모두 $m$과 서로소이다.

따라서 $\phi(m)$개의 열들이 이러한 경우에 해당된다.

$gcd(r,m)=1$ 인 어떤 $r$열을 보자.

$$ r,m+r,2m+r, ~~\dots ~~ ,(n-1)m+r $$

의 수들은 법 $n$에 대해 완전잉여계를 이룬다. 그렇지 않다면

$$ r+am \equiv r + bm \pmod n ~~ (0 \le a,b < n) $$

이 되어 $(a-b)m \equiv 0 \pmod n \Longrightarrow a-b \equiv 0 \pmod n$ 이 되어 모순이다.

따라서 $\phi(m)$개의 각 열에 있는 $n$개의 수 중에 $\phi(n)$개가 $mn$과 서로소이므로, $nm$에 서로소인 수의 개수는 $\phi(m)\phi(n)$이다.

즉, $\phi(mn)=\phi(m)\phi(n)~~ \square$

오일러 $\phi$함수의 값을 구하는 법

이는 PS에서 나오는 문제 중 하나이다.

Theorem 7.3 ⭐️

정수 $n > 1$이 소인수분해되어 $n=p_1^{k_1}p_2^{k_2} \cdots p_r^{k_r}$이면,

$$ \phi(n)=\Bigl( p_1^{k_1}-p_1^{k_1-1} \Bigr)\cdots \Bigl( p_r^{k_r}-p_r^{k_r-1} \Bigr) $$

증명 생략

오일러 $\phi$함수의 짝수성

Theorem 7.4

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

증명

$n$이 $2$의 거듭제곱이라고 하자.

$$ n=2^k~(k > 1) $$

Theorem 7.3에 의해 $\phi(n)=2^k-2^{k-1}=(2-1)\cdot 2^{k-1}$ 는 짝수이다.

$2$가 아닌 다른 소인수를 포함한다고 할 때, $\phi(n)=(p-1) \cdot p^{k-1} \cdots$ 처럼 되기때문에, $(p-1)$ 이 짝수라서 짝수이다.

$\phi$는 승법함수라서 $\phi(n)=\phi(p_1^{k_1}p_2^{k_2} \cdots p_r^{k_r})=\phi(p_1^{k_1}) \phi(p_2^{k_2}) \cdots \phi(p_r^{k_r})$ 이 되어 결국 $\phi(n)$은 짝수이다. $\square$

소수의 무한성과 오일러 $\phi$함수

이를 이용해 소수의 무한성을 증명해보자.

소수가 유한개 존재한다고 할 때, 그 집합을 $\{p_1, p_2, \dots, p_r\}$ 이라 하자.

$n=p_1p_2 \cdots p_r$ 을 고려하자.

$1 < k < n$ 인 모든 $k$에 대해 $gcd(k,n) > 1$ 이다.

$k$가 가지는 어떤 소인수는 $p_i$에 포함되므로 $p_i \mid n,~ p_i \mid k$ 이기 때문에 $gcd(n,k) > 1$ 이다.

그러면 $\phi(n)=1$ 이 되고 이는 Theorem 7.4에 모순이다.

따라서 소수는 무한하다. $\square$

Comments

You may also enjoy