Number Theory - 7.2 오일러 파이 함수
오일러 $\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$이면,
증명
$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{개}}$
따라서 이 수들을 제외한 개수는
$\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)$ 임을 보이자.
다음과 같은 수들의 격자식 배열을 고려한다.
$n$행 $m$열을 갖는다.
유클리드 호제법으로 $gcd(qm+r,m)=gcd(r,m)$이므로 어떤 $r$열의 수들이 $m$과 서로소일 조건은 $gcd(r,m)=1$ 이다.
또한 해당 열의 모든 수들은 모두 $m$과 서로소이다.
따라서 $\phi(m)$개의 열들이 이러한 경우에 해당된다.
$gcd(r,m)=1$ 인 어떤 $r$열을 보자.
의 수들은 법 $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$함수의 짝수성
Theorem 7.4
$n > 2$ 이면 $\phi(n)$은 짝수이다.
증명
$n$이 $2$의 거듭제곱이라고 하자.
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