오일러 정리[Euler's Theorem]

정의

페르마의 소정리를 일반화 한 것이다.

임의의 자연수 a, n이 서로소일 때 아래 식을 만족한다.

 

 

여기서 φ(n)은 오일러의 피 함수라 하며 1 부터 n까지의 자연수 중에 n과 서로소인 것의 개수를 나타내는 함수이다.

 

증명

오일러 정리 증명 과정은 이전에 포스팅 한 페르마의 소정리의 증명과 유사하다.

 

① 아래 집합 S는 n이하 자연수에서 n과 서로소인 수들의 집합이다.

 

② S의 각 원소에 a를 곱한 집합을 AS라 하자.

 

③ 귀류법을 통해 S = AS임을 증명.

만약 S ≠ AS 라면, AS의 임의의 두 원소 a*si, a*sj (0 < si < sj < n)가 mod n에서 같거나 두 원소 중 하나 이상이 n과 서로소가 아니어야 한다.

a는 n과 서로소이며 si, sj 둘 다 n과 서로소이기 때문에 a*si, a*sj 또한 n과 서로소이다.

그리고 a*si ≡ a*sj (mod n) 이라면 a*(sj-si) ≡ 0이고 a는 n과 서로소이기 때문에 sj-si가 n의 배수여야 한다. sj-si는 (0 < si < sj < n) 조건 때문에 n보다 클 수 없다. 

따라서 서로 다른 S의 두 원소 si, sj에 대하여 a*si, a*sj는 서로 다르며 n과 서로소이다.

 

④ 두 집합의 원소들의 곱이 합동임을 통해 정의 증명.

S의 원소들을 나누면

심화

오일러 정리 증명과정이 페르마의 소정리의 증명과 유사하여 왜 굳이 φ(n) 오일러의 피 함수가 필요한지 의문이 들 수 있다.

실제로 φ(n)은 n이 소수가 아니면 계산량이 많아 나머지 연산에서 n이 소수일 때가 많다.

 

그럼 모든 자연수 a, n이 서로소일 때 페르마의 소정리의 식을 증명하도록 유도해보자.

 

① 아래 집합 S는 n보다 작은 자연수들의 집합이다.

 

② S의 각 원소에 a를 곱한 집합을 AS라 하자.

 

③ 페르마의 소정리의 증명 ①을 통해 S = AS 이다.

 

④ 두 집합의 곱이 합동이다. (여기까지는 오일러 정리와 같으며 참이다.)

 

⑤ 1 ~ n-1 중 n과 서로소가 아닌 수는 나눌 수 없다.

모든 정수 a, b에 대해 a*c ≡ b*c (mod n) 일 때 a ≡ b (mod n)을 만족하려면 n과 c가 서로소여야 한다.

a*c ≡ b*c, (a-b)*c ≡ 0 (mod n) 이다. 이 때 c가 n과 서로소가 아닌 n의 약수라면 a-b가 n의 다른 약수일 때

(a-b)*c ≡ 0 (mod n) 이 식은 만족한다.

예를 들어 4*2 ≡ 1*2 (mod 6)은 만족하지만 4 ≡ 1 (mod 6)은 아니다.

 

위 과정을 통해 mod n에서 n이 소수가 아닐 때 페르마의 소정리 식이 만족하지 않으며 φ(n)을 계산해야하는 이유를 알 수 있다.

그리고 n이 소수일 때 n보다 작은 모든 자연수는 n과 서로소이므로 φ(n) = n-1이다.

rsa 암호에서 쓰이는 소수들의 곱으로 나머지 연산을 하는 경우, 서로 다른 소수 p, q에 대해 φ(p*q) = (p-1)*(q-1) 로 응용해서 쓸 수도 있다.

 

응용

큰 지수 제곱을 나머지 연산에서 구하는 문제를 쉽게 풀 수 있다.

 

마치며

 이번시간에는 페르마의 소정리와 오일러 정리가 어떻게 다른지 오일러 피 함수가 왜 필요한지를 말씀드렸습니다.

다음시간에는 조합론에서 이용되는 뤼카의 정리를 포스팅할 까 합니다~