오일러 정리 합동식은 정수론에서 매우 중요한 개념으로, 모듈러 산술에서 거듭제곱의 나머지를 계산하는 데 유용하게 사용됩니다. 특히, 큰 수의 거듭제곱에 대한 나머지를 구할 때 효율적인 방법을 제공하여 암호학 등 다양한 분야에서 활용됩니다. 이번 글에서는 오일러 정리 합동식의 기본 공식과 그 의미를 살펴보고, 실제 문제에 어떻게 적용할 수 있는지 구체적인 예시를 통해 알아보겠습니다.
오일러 정리 합동식의 기본 공식
오일러 정리 합동식은 다음과 같이 정의됩니다. 만약 두 정수 $a$와 $n$이 서로소($ ext{gcd}(a, n) = 1$)라면, 다음이 성립합니다.
$a^{\phi(n)} \equiv 1 \pmod{n}$
여기서 $\phi(n)$은 오일러 피 함수(Euler's totient function)로, $1$부터 $n$까지의 자연수 중에서 $n$과 서로소인 양의 정수의 개수를 나타냅니다. 예를 들어, $\phi(10)$은 $10$과 서로소인 수인 $1, 3, 7, 9$의 개수이므로 $\phi(10) = 4$입니다.
오일러 피 함수($\phi(n)$) 계산 방법
오일러 피 함수는 $n$의 소인수분해를 이용해 계산할 수 있습니다. 만약 $n$의 소인수분해가 $n = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}$ (여기서 $p_i$는 서로 다른 소수이고 $k_i \ge 1$)이라면, 오일러 피 함수는 다음과 같이 계산됩니다.
$\phi(n) = n \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_r}\right)$
또는
$\phi(n) = (p_1^{k_1} - p_1^{k_1-1}) (p_2^{k_2} - p_2^{k_2-1}) \cdots (p_r^{k_r} - p_r^{k_r-1})$
예를 들어, $\phi(12)$를 계산해 봅시다. $12$의 소인수분해는 $2^2 \times 3^1$입니다. 따라서
$\phi(12) = 12 \left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{3}\right) = 12 \times \frac{1}{2} \times \frac{2}{3} = 4$
또는
$\phi(12) = (2^2 - 2^1)(3^1 - 3^0) = (4-2)(3-1) = 2 \times 2 = 4$
$12$와 서로소인 수는 $1, 5, 7, 11$로 총 4개입니다.
오일러 정리 합동식의 의미와 활용
오일러 정리 합동식 $a^{\phi(n)} \equiv 1 \pmod{n}$은 $a$를 $\phi(n)$번 거듭제곱하면 $n$으로 나누었을 때 나머지가 항상 $1$이 된다는 것을 의미합니다. 이는 큰 수의 거듭제곱에 대한 나머지를 계산할 때, 지수를 $\phi(n)$의 배수로 줄여서 계산할 수 있게 해줍니다. 즉, $a^k \pmod{n}$을 계산해야 할 때, $k$를 $\phi(n)$으로 나눈 나머지를 $k'$라고 하면 $a^k \equiv a^{k'} \pmod{n}$이 성립합니다. (단, $a$와 $n$이 서로소일 때)
실제 적용 예시
예시 1: $3^{100} \pmod{10}$ 계산하기
먼저 $a=3, n=10$입니다. $3$과 $10$은 서로소($ ext{gcd}(3, 10) = 1$)입니다. 오일러 피 함수 $\phi(10)$은 앞에서 계산했듯이 $4$입니다.
오일러 정리에 의해 $3^{\phi(10)} = 3^4 \equiv 1 \pmod{10}$이 성립합니다.
이제 $3^{100} \pmod{10}$을 계산하기 위해 지수 $100$을 $\phi(10)=4$로 나눕니다.
$100 = 4 \times 25$
따라서 $100$은 $4$의 배수이므로, $3^{100} = (3^4)^{25} \equiv 1^{25} \equiv 1 \pmod{10}$입니다.
예시 2: $7^{50} \pmod{12}$ 계산하기
$a=7, n=12$입니다. $7$과 $12$는 서로소($ ext{gcd}(7, 12) = 1$)입니다. $\phi(12)$는 앞에서 계산했듯이 $4$입니다.
오일러 정리에 의해 $7^{\phi(12)} = 7^4 \equiv 1 \pmod{12}$가 성립합니다.
이제 지수 $50$을 $\phi(12)=4$로 나눕니다.
$50 = 4 \times 12 + 2$
나머지는 $2$입니다. 따라서
$7^{50} \equiv 7^2 \pmod{12}$
$7^2 = 49$이고, $49 \pmod{12}$를 계산하면 $49 = 4 \times 12 + 1$이므로 나머지는 $1$입니다.
따라서 $7^{50} \equiv 1 \pmod{12}$입니다.
오일러 정리의 확장: 오일러-페르마 정리
오일러 정리는 페르마의 소정리의 일반화된 형태라고 볼 수 있습니다. 페르마의 소정리는 $p$가 소수이고 $a$가 $p$의 배수가 아닐 때 $a^{p-1} \equiv 1 \pmod{p}$라는 것을 말합니다. 오일러 피 함수는 소수 $p$에 대해 $\phi(p) = p-1$이므로, 오일러 정리는 페르마의 소정리를 포함합니다.
결론
오일러 정리 합동식은 $a^{\phi(n)} \equiv 1 \pmod{n}$ (단, $ ext{gcd}(a, n) = 1$)이라는 강력한 도구입니다. 이를 통해 우리는 복잡한 거듭제곱 연산의 나머지를 효율적으로 계산할 수 있으며, 이는 암호학, 코딩 이론 등 다양한 컴퓨터 과학 및 수학 분야의 기초가 됩니다. 오일러 피 함수의 계산 방법을 이해하고, 오일러 정리를 실제 문제에 적용하는 연습을 통해 모듈러 산술에 대한 이해를 더욱 깊게 할 수 있습니다.