알고리즘/Euler Theorm 썸네일형 리스트형 [Fermat's little theorem] 페르마의 소정리 페르마의 소정리는 아래와 같이 정의 된다. (전제 조건) a와 m이 서로소여야 하며, m이 소수일 경우 $$ a^{m-1} \equiv 1 \ (mod \ m)$$ 페르마의 소정리가 왜 필요할까? 보통은 modulus 연산의 나눗셈을 구하기 위한 응용으로 많이 사용된다. 다시 말하자면, 위의 수식을 아래와 같이 정리해 볼 수 있다는 말이다. $$ a^{m-2} \equiv a^{-1} \ (mod \ m)$$ modular 연산은 덧셈, 뺄셈, 곱셈에 대해서는 분배 법칙이 성립한다. $$ (a+b) \ mod \ m = a \ mod \ m + b \ mod \ m $$ $$ (a-b) \ mod \ m = a \ mod \ m - b \ mod \ m $$ $$ (a \times b) \ mod \ m.. 더보기 [오일러 Phi 함수] Euler totient function 오일러 Phi 함수 $\phi(n)$ 는 1부터 n까지 사이의 수 중에서 n과의 최대공약수가 1인 수의 갯수를 나타내는 함수이다. Phi 함수는 아래와 같은 성질을 만족한다. 1) 만약 p가 소수라면 $\phi(p)$ = p-1 를 만족한다. 2) 만약 p가 소수이고, k$\geq1$라면 1부터 $p^k$까지 정확히 $p^k/p$가 p로 나누어지기 때문에 다음을 만족한다. $\phi(p^k) = p^k - p^{k-1}$ 3) a와 b가 서로소라면 다음을 만족한다. $\phi(ab) = \phi(a) * \phi(b)$ 이를 바탕으로 수식을 정리하면, 아래와 같다. $\phi(n)$ = n * $(1- \frac{1}{p_1})$* $(1- \frac{1}{p_2})$* $(1- \frac{1}{p_3}.. 더보기 이전 1 다음
