오일러 ϕ 함수
Definition 7.1
주어진 n≥1 에 대해 ϕ(n)은 n과 서로소이면서 n 이하인 자연수의 개수이다.
특히, gcd(1,1)=1 이므로 ϕ(1)=1, 소수는 자기 자신으로만 나뉘어지므로 ϕ(p)=p−1 임에 주목한다.
∵ 서로소의 정의에 의해 1은 자기 자신과 서로소이다.
ϕ(n)=n−1 인 것은 n이 소수다와 동치이다.
증명
n이 합성수라고 할 때, 1<d<n 을 만족하는 진약수 d가 존재하여 ϕ(n)≤n−2 가 되기 때문에 ϕ(n)=n−1 이 되려면 n이 소수여야만 한다. □
오일러 ϕ함수와 소인수분해를 이용한 계산법
Theorem 7.1
p가 소수이고 k>0이면,
ϕ(pk)=pk−pk−1
증명
gcd(n,pk)=1 일 조건은 p∤n 이다.
1부터 pk 까지 p의 배수는 정확히 pk−1개이다.
∵ p,2p,…,pk−1⋅ppk−1개
따라서 이 수들을 제외한 개수는
ϕ(pk)=pk−pk−1
□
오일러 ϕ함수의 승법성
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∣a, d∣bc 이므로 gcd(a,bc)≥d 임을 의미하고, gcd(a,bc)=1 이므로 d=1 임을 강제한다.
gcd(a,c)=1 도 동일하게 유도할 수 있다.
역 증명
gcd(a,b)=1,gcd(a,c)=1 일 때, gcd(a,bc)=d1>1 이라 가정하자.
d1이 가지는 소인수 p가 p∣a, p∣bc 이므로 p∣b 혹은 p∣c 여야 한다.
이 때, gcd(a,b) 혹은 gcd(a,c) 는 p가 되므로 모순이다.
즉, gcd(a,bc)=1 이다. □
Theorem 7.2
ϕ는 승법 함수이다.
증명
m⊥n 일 때, ϕ(mn)=ϕ(m)ϕ(n) 임을 보이자.
다음과 같은 수들의 격자식 배열을 고려한다.
1m+12m+1⋮(n−1)m+12m+22m+2(n−1)m+2⋯⋯⋯⋯rm+r2m+r(n−1)m+r⋯⋯⋯⋯m2m3mnm
n행 m열을 갖는다.
유클리드 호제법으로 gcd(qm+r,m)=gcd(r,m)이므로 어떤 r열의 수들이 m과 서로소일 조건은 gcd(r,m)=1 이다.
또한 해당 열의 모든 수들은 모두 m과 서로소이다.
따라서 ϕ(m)개의 열들이 이러한 경우에 해당된다.
gcd(r,m)=1 인 어떤 r열을 보자.
r,m+r,2m+r, … ,(n−1)m+r
의 수들은 법 n에 대해 완전잉여계를 이룬다. 그렇지 않다면
r+am≡r+bm(modn) (0≤a,b<n)
이 되어 (a−b)m≡0(modn)⟹a−b≡0(modn) 이 되어 모순이다.
따라서 ϕ(m)개의 각 열에 있는 n개의 수 중에 ϕ(n)개가 mn과 서로소이므로, nm에 서로소인 수의 개수는 ϕ(m)ϕ(n)이다.
즉, ϕ(mn)=ϕ(m)ϕ(n) □
오일러 ϕ함수의 값을 구하는 법
이는 PS에서 나오는 문제 중 하나이다.
Theorem 7.3 ⭐️
정수 n>1이 소인수분해되어 n=p1k1p2k2⋯prkr이면,
ϕ(n)=(p1k1−p1k1−1)⋯(prkr−prkr−1)
증명 생략
오일러 ϕ함수의 짝수성
Theorem 7.4
n>2 이면 ϕ(n)은 짝수이다.
증명
n이 2의 거듭제곱이라고 하자.
n=2k (k>1)
Theorem 7.3에 의해 ϕ(n)=2k−2k−1=(2−1)⋅2k−1 는 짝수이다.
2가 아닌 다른 소인수를 포함한다고 할 때, ϕ(n)=(p−1)⋅pk−1⋯ 처럼 되기때문에, (p−1) 이 짝수라서 짝수이다.
ϕ는 승법함수라서 ϕ(n)=ϕ(p1k1p2k2⋯prkr)=ϕ(p1k1)ϕ(p2k2)⋯ϕ(prkr) 이 되어 결국 ϕ(n)은 짝수이다. □
소수의 무한성과 오일러 ϕ함수
이를 이용해 소수의 무한성을 증명해보자.
소수가 유한개 존재한다고 할 때, 그 집합을 {p1,p2,…,pr} 이라 하자.
n=p1p2⋯pr 을 고려하자.
1<k<n 인 모든 k에 대해 gcd(k,n)>1 이다.
k가 가지는 어떤 소인수는 pi에 포함되므로 pi∣n, pi∣k 이기 때문에 gcd(n,k)>1 이다.
그러면 ϕ(n)=1 이 되고 이는 Theorem 7.4에 모순이다.
따라서 소수는 무한하다. □
Comments