May 17, 2025
중국인 나머지 정리 (Chinese Remainder Theorem, CRT) 중국인 나머지 정리는 여러 개의 나머지 조건을 만족하는 수를 찾을 수 있는 도구다. 각 나머지 조건(mod)이 서로소라면, 유일한 해를 구할 수 있다. 문제 형태 다음과 같은 연립합동식이 주어졌을 때: 단, m₁, m₂, ..., mₖ는 서로소여야 한다. 공식 여기서: M = …
May 17, 2025
페르마의 소정리 (Fermat's Little Theorem) 이게 뭐냐면… 어떤 소수 p랑, p랑 서로 다르고 0도 아닌 수 a가 있을 때, 그 a를 (p-1)번 곱하면, 결과를 p로 나눈 나머지는 1이 된다. 예를 들어 소수 p = 7 수 a = 3 (7보다 작고, 7이랑 서로소) 그럼 정리에 따르면: 을 로 나누면 나머지가 이다. 직접 계산해보…