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

지난 글의 페르마 소정리는 소수 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에서의 특수한 경우입니다.

오일러 피 함수는 무엇을 세는가?

$\varphi(n)$는 1부터 $n$까지의 자연수 중에서 $n$과 서로소인 수의 개수입니다. 즉, 단순히 개수를 세는 함수가 아니라 mod $n$에서 역원을 가질 수 있는 수들이 얼마나 있는지와 연결되는 함수입니다.

예를 들어 $n=8$이면 1부터 8까지의 수 가운데 8과 서로소인 수는

• 1, 3, 5, 7

이므로

$$\varphi(8)=4$$

입니다.

또 $n=10$이면 1, 3, 7, 9가 10과 서로소이므로

$$\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$$

입니다.

Common mistakes

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

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

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

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

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

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

Wrap-up

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

다음 글에서는 이런 함수들을 더 넓게 보는 관점으로 넘어가, 산술함수라는 틀을 간단히 소개하겠습니다.