티스토리 뷰

Mathematics/theorem

Euler's Totient Function

키팅529 2006. 5. 3. 07:12
반응형
# 정수론에서 합동의 정의
a, b를 m으로 나눈 나머지가 같을 때, a와 b가 법(modulo) m에 관하여 합동 (Congruence)이라고 하고, a≡b(mod m)으로 나타낸다.

# 합동의 기본 성질
a≡b(mod m)이고, c≡d(mod m) 이면
1. a+c≡b+d(mod m)
2. ac≡bd(mod m)
3 aⁿ≡bⁿ(mod m)


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

-- 합동의 기약화

두 양의 정수 n, d에 대하여 다음이 성립한다.

# ad≡bc(mod nd)↔a≡b(mod n)

[증명] nd|d(a-b)↔n|a-b

# gcd(m,n)=1이고 am≡bm(mod n)이면 a≡b(mod n)

[증명] cf) aa`≡1(mod n)일 때, a`을 n에 대한 a의 역수라고 한다.

이런 역수가 존재할 조건은 gcd(a, n)=1이며

이는 일차부정방정식 ax+ny=1에서의 해 x와 같다.

gcd(m,n)=1에서, mm`≡1(mod n)을 만족하는 m` 존재

a≡a·1≡a(mm`)≡(am)m`

≡(bm)m`≡b(mm`)≡b·1≡b

# gcd(m, n)=d이고 am≡bm(mod n)이면 a≡b(mod n/d)

[증명] 위 증명에서, 최대공약수 1을 d로 확장시키면, m과 n, d의 관계에서

위 관계가 성립



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


이제 합동에 관한 전반은 숙지한 셈이므로 오일러 함수와 정리를 이해하는 데에는 큰 지장이 없을 것이다. 그렇다면 오일러 함수(정리)에 대해 알아보자.




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



-- 오일러 함수

# 양의 정수 m에 대하여, m 이하의 자연수 중에서 m과 서로소인 정수의 개수를 φ(m)으로 나타내고 함수 φ : Z→N 를 오일러의 φ함수라고 한다.

# !!DEEP!!


위 오일러 함수의 정의가 잘 이해가지 않는 사람이 있을 것이며, 이 함수의 성질은 더더욱 이해하기 어려울 수 있다. 따라서 다음을 참고하라.

~임의의 자연수 n에 대하여 n이 취할 수 있는 모든 나머지의 집합을 '완전잉여계'라 하며, 이를 집합으로 표현하면 다음과 같다.

자연수 n에 대한 완전잉여계 ; {0, 1, 2, … , n-1} (단, i는 i를 일의 자리로 하는 모든 자연수)

~ 그리고, 특별히 이러한 완전잉여계의 원소 중 n과 서로소인 것들의 집합을 '기약잉여계'라 하며 이를 집합으로 표현하면 다음과 같다.

자연수n에 대한 기약잉여계 ; {r₁, r₂, r₃,…, rφ(n)} (단, gcd(ri, n)=1)

~ 가장 중요한 것은

gcd(a, n)=1일 때, {ar₁, ar₂, ar₃,…,arφ(n)} 또한 위의 기약잉여계와 같아진다.




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



-- 오일러 함수의 성질

p가 소수일 때 다음이 성립한다.

# φ(p)=p-1

[증명] 소수p는 자지 자신을 제외한 p이하의 자연수 모두와 서로소이므로 성립

# φ(p^k)=p^k-p^(k-1)

[증명] p^k 이하의 자연수 중 이와 서로소가 아닌 것은

1·p, 2·p,…, p^(k-1)·p(=p^k)의 p^(k-1)개이므로 이를 빼주면 된다.

# φ(2^k)=2^k-2^(k-1)(k≥1)

[증명] 위로부터, φ(2^k)=2^k-2^(k-1)=2^k-1(2-1)=2^k-1(k≥1)

# gcd(m,n)=1일 때, φ(mn)=φ(m)φ(n)

[증명] 위의 증명 과정은 매우 복잡하여 여기에 제시하기는 힘들기 때문에 생략



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


-- 오일러 정리

양의 정수 n과 gcd(a, n)=1인 정수 a에 대하여 a^φ(n)≡1(mod n)이다.

[증명] n의 기약잉여계

A={r₁, r₂, r₃,…, rφ(n)}

gcd(a, n)=1이므로, A를 다르게 나타내면

B={ar₁,ar₂,ar₃,…, arφ(n)} * DEEP 참고

A와 B는 상등하므로 그 나머지가 같은 원소가 일대일로 존재한다.

따라서 a^φ(n)·r1r2…rφ(n)≡r1r2…rφ(n) (mod n)

n과 r₁, r₂, r₃,…, rφ(n)은 각각 서로소이므로 약분 가능 * 합동의 기약화

따라서 a^φ(n)≡1(mod n)

cf) 오일러 정리는 법 n에 대한 한 정수 a의 역수를 쉽게 구하는 데 활용된다.




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



-- 페르마의 소정리(Ferma's Little Theorem)

p가 소수일 때, gcd(a, p)=1인 정수 a에 대하여 a^(p-1)≡1(mod p)이다.

[증명] 오일러 정리에서 n=p대입하고, φ(p)=p-1이용하면 증명


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



이로써 오일러 정리를 알아보았다. 오일러 정리는 정수론에서 다양하게 사용되며, 응용분야가 많다. 이러한 오일러 정리를 위 체계대로만 잘 정리해 놓으면 정수론은 물론 수론에서 다양하게 활용할 수 있다.

출처: http://blog.naver.com/vmflstm90?Redirect=Log&logNo=90001921657
반응형
댓글