[정수론 입문 시리즈 16편] 오일러 피 함수와 오일러 정리는 페르마 소정리를 어떻게 넓힐까?

왜 RSA 같은 공개키 암호에서는 아주 큰 소수 두 개를 곱한 수를 쓸까요? 답은 “서로소인 수가 몇 개인지”와 “거듭제곱이 언제 1로 돌아오는지”를 알려 주는 오일러 정리에 있습니다.

지난 글의 페르마 소정리는 소수 mod에서 매우 강력했습니다. 하지만 현실에서는 mod가 항상 소수인 것은 아닙니다. 8, 10, 12 같은 합성수 mod에서도 비슷한 구조를 보고 싶다면, 그 역할을 하는 것이 오일러 피 함수와 오일러 정리입니다.

What this post covers

• 오일러 피 함수가 무엇을 세는지 설명합니다.
• 오일러 정리가 페르마 소정리를 어떻게 일반화하는지 이해합니다.
• 간단한 예시로 값을 계산해 봅니다.
• 다음 글의 중국인의 나머지 정리로 이어집니다.

이번 글에서 새로 나오는 용어

• 오일러 피 함수 (Euler Totient Function): $1$부터 $n$까지의 자연수 중 $n$과 서로소인 수의 개수입니다.
• 오일러 정리 (Euler's Theorem): $\gcd(a,n)=1$이면 $a^{\varphi(n)} \equiv 1 \pmod n$이 성립한다는 정리입니다.
• 서로소 (Coprime): 최대공약수가 1인 관계입니다.
• 페르마 소정리 (Fermat's Little Theorem): 소수 mod에서의 특수한 경우입니다.

먼저 세어 보기: mod 8과 mod 10

공식부터 외우기 전에 작은 수로 세어 봅시다. $n=8$일 때 1부터 8까지의 수 가운데 8과 서로소인 수는

• 1, 3, 5, 7

입니다. 모두 mod 8에서 곱셈을 되돌릴 수 있는 수들입니다. 그래서 개수는 4개입니다.

또 $n=10$이면 1, 3, 7, 9가 10과 서로소이므로 역시 4개입니다.

이렇게 “1부터 $n$까지에서 $n$과 서로소인 수가 몇 개인지” 세는 함수를 $\varphi(n)$, 즉 오일러 피 함수라고 합니다. 따라서

$$\varphi(8)=4,\qquad \varphi(10)=4$$

입니다.

이제 패턴을 거듭제곱에 적용하면 오일러 정리가 나옵니다. 정수 $a,n$에 대해 $\gcd(a,n)=1$이면

$$a^{\varphi(n)} \equiv 1 \pmod n$$

이 성립합니다. 이 정리가 바로 오일러 정리입니다.

페르마 소정리와 어떤 관계일까?

만약 $p$가 소수라면, 1부터 $p-1$까지의 모든 수가 $p$와 서로소입니다. 따라서

$$\varphi(p)=p-1$$

입니다.

그러므로 오일러 정리에 $n=p$를 넣으면

$$a^{p-1} \equiv 1 \pmod p$$

가 되어 페르마 소정리가 됩니다.

즉, 페르마 소정리는 오일러 정리의 특수한 경우입니다.

예시 1. $3^{100} \pmod 10$

10과 서로소인 수의 개수는

$$\varphi(10)=4$$

입니다.

또 $\gcd(3,10)=1$이므로 오일러 정리에 의해

$$3^4 \equiv 1 \pmod {10}$$

입니다.

100은 4의 배수이므로

$$3^{100} = (3^4)^{25} \equiv 1^{25} \equiv 1 \pmod {10}$$

입니다.

예시 2. $5^{20} \pmod 8$

8과 서로소인 수는 1, 3, 5, 7이므로

$$\varphi(8)=4$$

입니다. 또 $\gcd(5,8)=1$이므로

$$5^4 \equiv 1 \pmod 8$$

입니다. 따라서

$$5^{20} = (5^4)^5 \equiv 1^5 \equiv 1 \pmod 8$$

입니다.

실험: 손으로 계산하기

오일러 피 함수와 오일러 정리는 먼저 “서로소인 나머지들이 몇 개 있는가?”와 “그 수들을 거듭제곱하면 어떤 반복이 생기는가?”를 손으로 확인하면 이해하기 쉽습니다.

실험 1. $\varphi(8)$ 세기

1부터 8까지에서 8과 서로소인 수를 표시해 봅시다.

수	$\gcd(수,8)$	서로소?
1	1	예
2	2	아니오
3	1	예
4	4	아니오
5	1	예
6	2	아니오
7	1	예
8	8	아니오

따라서 $\varphi(8)=4$입니다.

실험 2. $\varphi(10)$ 세기

10과 서로소인 수는 1, 3, 7, 9입니다. 따라서

$$\varphi(10)=4$$

입니다.

실험 3. 오일러 정리 확인하기

$\gcd(3,10)=1$이고 $\varphi(10)=4$이므로 오일러 정리는 $3^4\equiv 1\pmod {10}$을 예측합니다.

$$3^2=9\equiv 9\pmod {10}$$ $$3^4\equiv 9^2=81\equiv 1\pmod {10}$$

또 $\gcd(5,8)=1$이고 $\varphi(8)=4$이므로

$$5^4=625\equiv 1\pmod 8$$

입니다.

패턴 발견

실험에서 보이는 패턴은 두 가지입니다.

• $\varphi(n)$는 mod $n$에서 “곱셈을 되돌릴 수 있는 수”, 즉 역원을 가진 수의 개수와 연결됩니다.
• $a$가 $n$과 서로소이면 $a^{\varphi(n)}$은 mod $n$에서 1로 돌아옵니다.

따라서 오일러 정리는 합성수 mod에서도 거듭제곱을 작게 줄이는 길을 줍니다. 소수 mod에서 $p-1$을 쓰던 페르마 소정리가, 일반 mod에서는 $\varphi(n)$을 쓰는 형태로 넓어지는 것입니다.

이론 정리

오일러 피 함수와 오일러 정리

$\varphi(n)$는 1부터 $n$까지의 자연수 중 $n$과 서로소인 수의 개수입니다.

$\gcd(a,n)=1$이면

$$a^{\varphi(n)}\equiv 1\pmod n$$

이 성립합니다.

특히 $p$가 소수이면 $\varphi(p)=p-1$이므로 페르마 소정리

$$a^{p-1}\equiv 1\pmod p$$

가 나옵니다.

Python으로 확인하기

아래 코드는 $\varphi(n)$을 직접 세고, 오일러 정리를 작은 예시에서 확인합니다.

from math import gcd


def phi(n):
    count = 0
    for k in range(1, n + 1):
        if gcd(k, n) == 1:
            count += 1
    return count

for n in [8, 10]:
    print(f"phi({n}) = {phi(n)}")

examples = [(3, 10), (5, 8), (7, 12)]

for a, n in examples:
    if gcd(a, n) == 1:
        exponent = phi(n)
        print(f"{a}^{exponent} mod {n} =", pow(a, exponent, n))

출력값이 모두 1이 되는 이유를 오일러 정리의 조건과 연결해 설명해 보세요.

Common mistakes

1. $\varphi(n)$를 그냥 $n-1$로 생각하는 실수

그것은 $n$이 소수일 때만 성립합니다.

2. 서로소 조건을 확인하지 않는 실수

오일러 정리도 $\gcd(a,n)=1$이어야 합니다.

3. 페르마 소정리와 오일러 정리를 완전히 별개로 외우는 실수

둘은 연결된 구조입니다. 페르마는 소수 mod의 특수 경우이고, 오일러는 일반화입니다.

Silverman 교재 연결

이 글은 Silverman 《친절한 수론 길라잡이》(경문사)의 다음 내용과 연결됩니다.

• 10장: 합동, 거듭제곱, 오일러 공식 - Silverman 교재의 장 제목에서는 $a^{\varphi(n)} \equiv 1 \pmod n$ 형태의 결과를 “오일러 공식”이라는 이름으로 다룹니다.
• 11장: 오일러 φ 함수와 중국인의 나머지 정리 - 법 $n$에서 $n$과 서로소인 서로소인 나머지들의 개수를 세는 오일러 $\varphi$ 함수와 연결됩니다.
• 관련 정리/예제: $\gcd(a,n)=1$이면 $a^{\varphi(n)} \equiv 1 \pmod n$이고, $n=p$가 소수이면 페르마의 소정리로 내려갑니다.

연습 문제

아래 점검 퀴즈에서 학습한 내용을 확인해 보세요.

Wrap-up

이번 글에서는 오일러 피 함수가 mod $n$에서 서로소인 수의 개수를 세며, 오일러 정리가 이를 이용해 일반 mod에서 거듭제곱 구조를 정리한다는 점을 살펴봤습니다.

다음 글에서는 서로소인 법들에 대한 나머지 조건을 하나로 합치는 중국인의 나머지 정리를 정리하겠습니다.