오일러의 정리를 배우고 거듭제곱의 나머지를 구하는 방법 익히기

1. 오일러의 정리(Euler's theorem) a와 n이 서로소인 양의 정수이면, 다음이 성립한다 $$a^{\varphi(n)} \equiv 1 (mod n)$$ 여기서 $\varphi(n)$은 n에 대한 오일러 phi 함수이다. 서로소가 아니라면 다음과 같이 쓸 수 있다. $$a^{\varphi(n) + 1} \equiv a (mod n)$$ n이 소수 p이면, $\varphi(p) = p-1$이므로, a,p가 서로소이면 $a^{p-1} \equiv 1 (mod p)$이다. 페르마의 소정리는 오일러의 정리의 특수한 케이스이다. 2. 거듭제곱을 어떤 정수로 나눈 나머지 $a^{n}$을 어떤 정수 p로 나눈 나머지는 어떻게 구할 수 있을까? $a^{n}$을 직접 계산한 다음에, p로 나눈 나머지를 구하..