4. 페르마 소정리, 오일러 정리 및 활용

관련 코드는 github에서 찾아볼 수 있다.

다음 정리들은 정수론의 기초적이고 중요한 결과들이다. 증명은 찾아보면 쏟아져 나온다. 혹시 필요하면 댓글 :)

• 페르마의 소정리. 소수 $p$와 자연수 $a$가 $\text{gcd}(a, p)=1$을 (즉, $a$는 $p$의 배수가 아니다) 만족하면 $a^{p-1} \equiv 1 \pmod{p}$. 
• 오일러 정리. 앞서 오일러 파이 함수를 정의했다. 사실 $\phi(n)$은 $n$ 이하이며 $n$과 서로소인 자연수의 개수이다. 
• 오일러의 정리는, 자연수 $n, a$가 $\text{gcd}(a, n)=1$을 만족할 경우, $a^{\phi(n)} \equiv 1 \pmod{n}$임을 말한다. 페르마의 소정리는 특수 케이스.

잠깐 오일러 파이 함수에 대한 기본 사실들을 빠르게 짚고 넘어가자. 증명은 검색하면 충분히 나올듯. 필요하면 댓글 :)

• 앞서 언급했듯이, $n$의 서로 다른 소인수가 $p_1, p_2, \cdots , p_k$라면 $\phi(n) = n(1-1/p_1)(1-1/p_2) \cdots (1-1/p_k)$이다. 
• $\phi$는 multiplicative function이다. 이는 $n, m$이 서로소인 자연수일 때, $\phi(nm) = \phi(n)\phi(m)$임을 의미한다.
• $m|n$이면 $\phi(m)| \phi(n)$ 역시 성립한다. 이 사실은 이 단원에서 사용될 것이다.
• 이 외에도, $\sum_{d|n} \phi(d) = n$ 등 재밌는 성질이 많다. $\sum_{d|n}$이란, $n$의 약수 $d$에 대하여 더한다는 뜻.

그런데 생각보다 이 정리들을 CP/PS 환경에서 사용할 곳을 떠올리기는 쉽지 않다. 

•  보통 많이 쓰이는 방식은 $p$가 소수일 때, $\pmod{p}$에서 $a$의 ($a, p$는 서로소) modular inverse를 구하는 것이다.
•  즉, $a^{p-1} \equiv 1 \pmod{p}$에서 $a^{p-2} \cdot a \equiv 1 \pmod{p}$를 얻고, $a^{p-2}$가 modular inverse임을 얻는 것이다.
• 하지만 우리가 앞에서 살펴보았듯이, modular inverse를 구하는 것은 소수가 아닌 경우에도 쓸 수 있는 일반적이고 빠른 방법이 있다.
• 페르마의 소정리는 그렇다 쳐도, 오일러 정리는? modular inverse를 오일러 정리로 구하려면 $\phi(n)$ 값이 필요하다.
• $\phi(n)$을 구하려면 기본적으로 $n$의 소인수분해가 필요하다. $n$이 $10^9$-scale로 큰 경우에는 에라토스테네스의 체도 쓸 수 없으니, 진짜 소인수분해를 해야한다. 이때 시간복잡도는 현재 지식상으로는 $\mathcal{O}(\sqrt{n})$. 로그 시간을 보장하는 확장 유클리드와 비교된다. 그러면 어디서 쓸까?
• 물론, 오일러 파이 함수 자체는 CP/PS 환경에서 많이 쓰인다. 카운팅 문제에서 Burnside's Lemma 등을 활용할 때도 사용되고, 후에 다룰 내용에도 등장한다. 애초에 쓸모가 엄청 많은 함수다. 여기서 사용할 곳이 적다고 말하는/주장하는 것은 오일러 정리의 활용이다.
• (물론, 이렇게 말하지만 오일러 정리도 PS에서 아래에서 설명하는 예시 외의 문제에서 쓰이지 않는 것은 당연히 아니다)

보통 CP/PS에서 (그리고 사실 예전 KMO 1차에서) 이러한 정리들을 사용하는 환경은, "Power Tower"를 계산하기 위한 것이다. 대충 이런 문제다. 

모두의 편의를 위하여 $[a_1, a_2, \cdots , a_k] = a_1^{a_2^{ \cdots ^{a_k}}}$라고 정의하자. 우리의 목표는 $[a_1, a_2, \cdots , a_k] \pmod{n}$을 효율적으로 계산하는 것이다.

또한, 편의상 Power Tower $[a_1, a_2, \cdots, a_k]$의 길이를 등장하는 자연수의 개수 $k$라고 정의하겠다.

원리에 특별히 관심이 없고 알고리즘 및 시간복잡도만 필요한 분들은, 마지막 문단으로 바로 넘어가도 된다. 그래도 한 번 다 읽어보는 것을 추천. 

상대적으로 간단한 경우부터 보자. $\text{gcd}(a_1, n) = 1$을 가정한 상태에서 생각을 해보자. 오일러 정리에 의하여, 우리는 $a_1^{\phi(n)} \equiv 1 \pmod{n}$을 알고 있다. 

그러므로, $a_1$을 밑으로 할 때 지수에 $\phi(n)$에 대한 나머지를 취해도 결과값의 $n$에 대한 나머지가 변하지 않는다.

즉, $[a_1, \cdots , a_k] \equiv a_1^{[a_2, \cdots , a_k]} \equiv a_1^{[a_2, \cdots , a_k] \pmod{\phi(n)}} \pmod{n}$가 성립할 것이다. 이 식의 의미하는 바는 결국

• $a_1, \cdots , a_k, n$에 대한 문제를 $a_2, \cdots, a_k, \phi(n)$으로 간단하게 "축소", "환원"할 수 있다.

라는 것이다. 왜 "축소"일까? 이를 바라보는 것에는 두 가지 관점이 가능하다. 

• Power Tower의 "길이"가 $k$에서 $k-1$로 축소되었다고 볼 수 있다.
• $\phi(n) < n$은 ($n \neq 1$이면) 앞서 언급한 $\phi$의 성질/정의에서 자명하다. 그러니 modulus가 $n$에서 $\phi(n)$으로 축소되었다고 볼 수 있다.

어느 관점으로 보는 게 좋을까? 첫 번째 관점은 단순히 $\mathcal{O}(k)$의 횟수로 끝남을 의미할 뿐이다. 두 번째를 보자.

• 사실 1. $\phi(n)$은 $n \ge 3$에 대하여 모두 짝수이다. $\phi(n)$은 $1$ 이상 $n$ 이하 자연수 중 $n$과 서로소인 것의 개수라고 했었다. 그런데 $\text{gcd}(a, n)=1$이면 $\text{gcd}(n-a, n) = 1$도 성립한다. (갑자기 이해가 안된다면, 유클리드 알고리즘 부분을 다시 한 번 읽고 오는 것을 추천한다) 그러니 $a$와 $n-a$를 (합이 $n$인) 한 쌍으로 묶을 생각을 할 수 있다. 이렇게 묶이지 않는 경우는 $n$이 짝수일 때 $n/2$ 뿐이다. 그런데 $n \ge 3$이므로 $n$이 짝수이면 $\text{gcd}(n/2, n) = n/2 > 1$이 되고, 이 경우는 고려할 필요가 없음을 알 수 있다. 그러니 쌍을 전부 맺어줄 수 있고, 개수는 짝수.
• 사실 2. $n$이 짝수이면, $\phi(n) \le n/2$이다. $2$ 이상 $n$ 이하 모든 짝수들이 $n$과 공통 소인수 $2$를 가지므로, $n$과 서로소가 될 수 없다. 그러니 서로소인 것의 개수는 많아봐야 $n-n/2 = n/2$개이며, 증명 끝. 이 두 사실을 이용하여, 우리가 문제를 "축소"하는 방식이 매우 강력함을 보여보자.

우리의 두 번째 관점은 modulus $n$의 감소에 집중하고 있다. $n$이 작으면 문제가 확실히 간단해진다.

$n=2$라면, $a_1$의 홀짝성만 판단하여 답을 바로 결정할 수 있다. $n=1$이면 그냥 답이 $0$이다. 그러니, 목표는 결국

• $n \rightarrow \phi(n) \rightarrow \phi(\phi(n)) \rightarrow \cdots $를 거칠 때, 언제 $1$이 될 것인가?

가 된다. 이러한 과정이 많아봐야 $\mathcal{O}(\log n)$번 필요함을 보이자.

• $n \rightarrow \phi(n)$ 과정에서는 별 논의를 할 수 없지만, 적어도 $\phi(n) < n$임은 안다.
• 그 이후부터는 재밌어진다. 사실 1에 의하여, 현재 $\phi(n)$은 짝수거나 $\phi(1)=\phi(2)=1$이다.
• $\phi(n)=1$인 경우에는 그냥 끝이다. $\phi(n)$이 짝수라 가정하자. 사실 2에 의하여, $\phi(\phi(n)) \le \phi(n)/2$이다.
• 즉, 한 번 과정을 거치면 modulus가 무조건 반 이상 감소한다. 이제 많아봐야 로그 횟수의 과정이 필요함은 당연하다.

물론, 위 논의는 문제를 축소하는 과정에서 계속 밑과 modulus가 서로소라는 가정이 성립할 때 가능한 것이다. 

즉, 처음에는 $\text{gcd}(a_1, n)=1$이어야 하며, 그 뒤에는 $\text{gcd}(a_2, \phi(n))=1$, $\text{gcd}(a_3, \phi(\phi(n)))=1$ 등이 필요하다.

이 가정을 제거하고 일반적인 문제를 해결하려면, 많은 노력이 필요하다. 우선 빠르게 전처리를 하나 하자.

• 이제부터 $a_i \ge 2$가 각 $i$에 대하여 성립함을 가정한다. $1$은 몇 번 곱해도 $1$이므로, $[a_1, a_2, \cdots, a_k , 1, b_1, b_2, \cdots, b_t] = [a_1, a_2, \cdots, a_k]$가 항상 성립한다. 즉, $1$이 등장하면 그 $1$과 뒤에 있는 tower를 다 날려도 된다. 이렇게 쓸모없는 부분을 날리는 과정을 거치면, $a_i \ge 2$인 상태가 된다. 

이제 다시 문제를 축소할 준비를 하자. $[a_1, \cdots, a_k] \equiv a_1^{[a_2, \cdots,  a_k]} \pmod{n}$는 정의상 여전히 성립.

문제를 해결할 각을 천천히 재보자. 개인적인 생각으로, 핵심 아이디어는 다음과 같다.

• 아이디어 1. 중국인의 나머지 정리와 소인수분해 : 사실 앞 단원에서 해도 되는 이야기지만, 여기서 한다. 
• 소인수분해는 자연수 $n$을 적당한 서로 다른 소수 $p_1, \cdots , p_k$에 대하여 $p_1^{e_1} p_2^{e_2} \cdots  p_k^{e_k}$ 형태로 유일하게 쓸 수 있다는 결과이다.
• 중국인의 나머지 정리는 $x \pmod{p_1^{e_1}}, x \pmod{p_2^{e_2}}, \cdots , x \pmod{p_k^{e_k}}$를 알면 이를 합쳐서 $x \pmod{n}$을 얻을 수 있다는 결과이다.
• 물론 반대 방향도 마찬가지. 즉, $n$에 대한 나머지를 아는 것과 $p_1^{e_1}, p_2^{e_2}, \cdots , p_k^{e_k}$에 대한 나머지를 아는 것은 완벽하게 동치이다.
• 그러니 $n$을 소인수분해하고, $n$이 갖는 각 prime power $p^e$에 대하여 $a_1^{[a_2, \cdots, a_k]} \pmod{p^e}$를 구할 생각을 할 수 있다.
• 이 생각의 흐름은 순수하게 수학적으로 보나, 지금/나중에 다룰 알고리즘의 중간 과정으로 보나 매우 중요하다. 

• 아이디어 2. 소수에 대한 케이스 분류 : 이제 목표를 $a_1^{[a_2, \cdots , a_k]} \pmod{p^e}$를 계산하는 것으로 정했다.
• Case 1. $a_1$이 $p$의 배수가 아닌 경우. 이 경우에는 $\text{gcd}(a_1, p^e)=1$이므로 기존에 했던 것과 똑같이 할 수 있다. 
• 즉, $[a_1, a_2, \cdots, a_k] \equiv a_1^{[a_2, \cdots , a_k] \pmod{\phi(p^e)}} \pmod{p^e}$가 성립한다.
• Case 2. $a_1$이 $p$의 배수인 경우. 이 경우가 우리가 새롭게 다루어야 하는 경우라고 볼 수 있겠다.
• 이 경우, $[a_2, \cdots , a_k]$의 값이 중요하다. 당장 이 지수가 $e$ 이상이라면, $a_1^{[a_2, \cdots, a_k]}$는 $p^e$의 배수가 된다.
• 그러니, 우리가 고안해야 하는 것은 $[a_2, \cdots, a_k]$가 $e$ 이상인지 판별하고, 아니라면 실제 값이 얼마인지 구하는 알고리즘이다.
• 길이 $4$의 Power Tower만 해도 $[2, 2, 2, 2] = 2^{16}$이므로, 이는 (CP/PS 환경에서) 커봐야 $60$ 언저리일 $e$를 훌쩍 넘는다.
• 즉, 길이 $3$ 이하의 Power Tower에 대해서만 고려해도 된다. 이제부터는 정수론이 아닌 단순 알고리즘의 영역이니, 직접 고민해보는 것 추천.
• 어쨌든 이 과정에서 $a_1^{[a_2, \cdots , a_k]} \pmod{p^e}$를 구할 수 있다. 각 경우에서 해답을 얻었으니, 중국인의 나머지 정리로 합치면 된다.

위 알고리즘은 어쨌든 문제를 환원하는 알고리즘이고, 실제로도 잘 작동할 것이다. 하지만 좀 복잡하고 더러우니, 깔끔하게 바꿔보자.

• 보조정리. $m|n$이면, $a \equiv (a \pmod{n}) \pmod{m}$이 성립한다. 
• 증명. $a \pmod{n}$은 어쨌든 적당한 정수 $k$에 대하여 $a+kn$으로 쓸 수 있다. $(a+kn)-a=kn$은 $m$의 배수이므로 증명 끝.

다시 아이디어 2의 케이스 분류 중 첫 번째 케이스로 돌아가보자. 

• Case 1. $a_1$이 $p$의 배수가 아닌 경우.
• $p^e|n$이므로, $\phi(p^e)|\phi(n)$이다. 보조정리에서 $([a_2, \cdots , a_k] \pmod{ \phi(n)}) \equiv [a_2, \cdots , a_k] \pmod{\phi(p^e)}$다.
• 그러므로, 오일러 정리에서 $[a_1, \cdots, a_k] \equiv a_1^{[a_2, \cdots , a_k] \pmod{\phi(n)}} \pmod{p^e}$가 성립한다.
• 이는 문제를 $n \rightarrow \phi(p_1^{e_1}), \phi(p_2^{e_2}), \cdots , \phi(p_k^{e_k})$로 복잡하게 문제를 환원하지 않고, 기존처럼 $n \rightarrow \phi(n)$ 형태로 문제를 환원할 수 있음을 의미한다.
• 즉, $[a_2, \cdots , a_k] \pmod{\phi(n)}$만 구하면 별다른 추가적인 처리 없이 원하는 계산을 할 수 있다는 의미다. 

이제부터 $[a_2, \cdots , a_k]$의 크기에 대한 케이스를 나눈다. 

• $[a_2, \cdots , a_k]$가 $100$ 이하인 경우. 이 경우에는 애초에 Power Tower의 길이 $k-1$이 $3$ 이하임을 앞에서 설명하였다. 그러니 $[a_2, \cdots,  a_k]$를 직접 계산한 뒤, $a_1^{[a_2, \cdots , a_k]} \pmod{n}$을 계산하면 된다. 즉, 이 경우는 중국인의 나머지 정리, 소인수분해, 앞선 케이스 분류 등의 아이디어가 필요없다.
•  $[a_2, \cdots , a_k]$가 $100$ 초과인 경우. 이 경우에는 $p|a_1$인 소수 $p$들에 대하여, $p^e$가 $n$의 prime power인 경우 ($e \le 100$일테니) $[a_1, a_2, \cdots , a_k] \equiv a_1^{[a_2, \cdots , a_k]} \equiv 0 \pmod{p^e}$가 될 것이다. 물론, $a_1$이 $p$의 배수가 아닌 경우는 위에서 다루었다.

이제 다음을 보일 준비가 완료되었다.

• Claim. $[a_2, \cdots , a_k] > 100$인 경우, $[a_1, \cdots, a_k] \equiv a_1^{[a_2, \cdots , a_k] \pmod{\phi(n)} + 100 \cdot \phi(n)} \pmod{n}$이다.
• 중국인의 나머지 정리를 생각하면, 결국 $n$의 소인수분해에 등장하는 각 prime power $p^e$에 대해 양변이 같은 나머지를 가짐을 보이면 된다.
• Case 1. $a_1$이 $p$의 배수가 아닌 경우. $\phi(p^e)|\phi(n)$이 성립하므로, 오일러의 정리에서 (즉, $a_1^{\phi(p^e)} \equiv 1 \pmod{p^e}$)
• $[a_1, \cdots , a_k] \equiv a_1^{[a_2, \cdots , a_k] \pmod{\phi(n)}} \equiv a_1^{[a_2, \cdots , a_k] \pmod{\phi(n)} + 100 \cdot \phi(n)} \pmod{p^e}$다. 증명 끝.
• Case 2. $a_1$이 $p$의 배수인 경우. $e \le 100$이고, $[a_2, \cdots , a_k] \ge 100$이고, $100 \cdot \phi(n) \ge 100$이다. 
• 그러니, $[a_1, \cdots , a_k] \equiv a_1^{[a_2, \cdots, a_k]} \equiv  0 \equiv a_1^{[a_2, \cdots , a_k] \pmod{\phi(n)} + 100 \cdot \phi(n)} \pmod{p^e}$다. 증명 끝.

위의 $100$이라는 값은 CP/PS 환경을 가정한 것이다. 실제로는 modulus가 $n$일 때, $\log_2 n$ 초과인 값을 아무거나 잡으면 된다. (너무 크게 잡으면 고생한다)

CP/PS 환경에서 웬만하면 $2^{100}$을 넘는 modulus는 볼 수 없을 것이므로, 그냥 $100$이라고 잡았다. 이렇게 하는 것이 짜기도 편하다.

이제 알고리즘을 정리해보자. 

• 입력은 $a_1, \cdots , a_k$와 $n$. $[a_1, \cdots , a_k] \pmod{n}$을 푸는 것이 목표다. 단, $a_i \ge 2$를 가정한다.
• 만약 $k \le 4$라면, $[a_2, \cdots , a_k]$가 $100$ 이하인지 판별하는 과정을 거친다.
• 만약 $100$ 이하라면, $[a_2, \cdots , a_k]$를 직접 계산하고 $a_1^{[a_2, \cdots , a_k]} \pmod{n}$을 반환한다.
• 그렇지 않다면, $\phi(n)$을 계산해준 뒤, $[a_2, \cdots , a_k] \pmod{\phi(n)}$을 계산한다. (즉, $a_2, \cdots , a_k$와 $\phi(n)$에 대한 문제를 푼다.)
• 그 후 $a_1^{[a_2, \cdots , a_k] \pmod{\phi(n)} + 100 \cdot \phi(n)} \pmod{n}$을 반환한다. 끝.

$a_i$가 $1$이 되어도 빠르게 잘 작동하는 알고리즘을 구축하는 것은 여러분의 몫이다. (정수론적 내용/테크닉이 추가되지 않는다) 

이 알고리즘은 맨 처음 여러 가정을 추가한 경우의 알고리즘처럼, modulus를 $n$에서 $\phi(n)$으로 축소한다.

이 과정이 로그 번 반복된 후에 modulus가 $1$이 된다는 사실은 그 때와 달라지지 않는다. 이제 마지막으로 복잡도 분석을 하자. 

각 단계에서 가장 핵심적인 비용은 역시 $\phi(n)$의 계산이다. 에라토스테네스의 체 등을 사용하지 않았다고 가정하면, $\phi(n)$의 계산은 $n$의 소인수분해가 필요하며 이는 $\mathcal{O}(\sqrt{n})$에 할 수 있다. 최대 $\mathcal{O}(\log n)$ 번의 단계가 필요하므로, 전체 시간복잡도는 $\mathcal{O}(\sqrt{n} \log n)$이다. 끝.