모듈러

페르마의 소정리? 페르마의 소정리는 피에르 드 페르마가 알아낸 정리로서, 정수론의 가장 기본이 되는 정리이다. 이 내용을 간단히 말하면, 임의의 소수 p와 서로소인 수 a에 대해, a^(p-1)을 p로 나눈 나머지는 무조건 1이라는 말이다. 예를 들어, 3^6 = 729를 7로 나누면 나머지는 1이라는 사실을 알 수 있다. 증명 이항정리를 사용한 증명 먼저 페르마의 소정리는 다음과 동치이며, n = 0일 경우는 자명하다. 이항정리에 의하면 여기서, 0 < n < p이면 은 p의 배수이다. 따라서, 는 항상 성립하는 명제이다. 같은 방법으로 도 항상 성립한다. 따라서 n일 때 성립한다 가정하면, n+1, n-1일 때도 성립한다. 즉, 모든 정수 n에 대해 이 공식이 성립한다는 것을 알 수 있다. 기약잉여계..

모듈로(Modulo) 연산 컴퓨팅에서 어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산으로, 나머지 연산(mod)이라고 한다. 즉 일반적으로 정수 범위의 내에서 대부분 a를 n으로 나눈 나머지 r과 몫 q는 다음을 충족한다. 일반적으로 a와 n이 모두 정수인 상태에서 수행되지만 요즘은 많은 곳에서 정수 범위 이상의 피연산자를 사용할 수 있다. 하지만, mod 0은 Divide by Zero 에서 예외가 발생할 수 있기 때문에 주의해야한다. 이 모듈로 연산에 관련된 규칙이 모듈러 산술이다. 모듈러 산술(Modular Arithmetic) 모듈로 합동(Congruence Modulo) 두 정수 a, b와 정수 n (n > 1)이 주어질 때 n이 a, b의 차의 약수인 경우 (즉, a - b = kn을 ..