정리/수학 (2) 썸네일형 리스트형 [수학] 페르마의 소정리 (Fermat's little Theorem) 정수론 [개념 소개] 소수 p와 서로소인 a에 대해 $a^{(p-1)}$를 p로 나눈 나머지가 1 [공식] $a^{(p - 1)} \equiv 1 \, (mod \; p)$ [응용] $a^{(p - 2)} \equiv \dfrac{1}{a} \, (mod \; p)$으로 나머지 연산의 곱셈 역원을 구할 수 있음 [수학] 조합 (Combination) 조합론 [개념 소개] n개의 원소 중 k개를 뽑는 경우의 수 [성질] $\dbinom{n}{k} = \dfrac{n!}{(n - k)!k!}$ $\dbinom{n}{k} = \dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1}$ $\Sigma_{k = 0}^{n} \dbinom{n}{k} = 2^n$ [관련 알고리즘] 파스칼의 삼각형: kangwlgns.tistory.com/46 페르마의 소정리를 이용한 이항 계수: kangwlgns.tistory.com/48 뤼카의 정리: kangwlgns.tistory.com/49 이전 1 다음