1.4 오일러 정리와 페르마의 소정리

거듭제곱의 나머지가 1이 되는 지점을 찾는 것은 정수론의 가장 아름다운 발견 중 하나입니다. 오일러 정리는 페르마 소정리의 일반화된 형태이며, 이는 군론(Group Theory)의 기초가 됩니다.

1. 페르마의 소정리 (Fermat’s Little Theorem)

소수 $p$와 $p$의 배수가 아닌 임의의 정수 $a$($\gcd(a, p)=1$)에 대하여 다음이 성립합니다.

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

양변에 $a$를 곱한 형태인 $a^p \equiv a \pmod p$는 모든 정수 $a$에 대해 성립합니다.

페르마의 소정리를 임의의 합성수 $m$으로 확장한 정리입니다.

Euler's Phi Function

$\phi(m)$은 $1$부터 $m$까지의 정수 중 $m$과 서로소인 수의 개수를 뜻합니다. $\gcd(a, m)=1$이면 다음이 성립합니다.

$$a^{\phi(m)} \equiv 1 \pmod{m}$$

핵심 용도: 지수가 매우 클 때, 지수를 $\phi(m)$으로 나눈 나머지로 줄여서 계산할 수 있습니다.

법 $m$에 대한 기약잉여계는 곱셈에 대해 군(Group)을 형성합니다.

1. 기약잉여군 $(\mathbb{Z}/m\mathbb{Z})^\times$: 법 $m$과 서로소인 나머지들의 집합입니다. 원소의 개수는 $\phi(m)$개입니다.

2. 모듈러 역원: $\gcd(a, m)=1$이면 $ax \equiv 1 \pmod m$을 만족하는 $x$가 항상 존재합니다. 오일러 정리에 의해 역원은 다음과 같이 구할 수 있습니다.

$$x \equiv a^{\phi(m)-1} \pmod m$$

$m$의 소인수분해가 $p_1^{e_1} p_2^{e_2} \dots$ 일 때:

$$\phi(m) = m \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \dots$$