중국인의 나머지 정리 계산기

중국인의 나머지 정리는 흔히 CRT로 줄여 쓰며, 여러 모듈러 조건을 하나의 해로 결합합니다. x ≡ 2 modulo 3이라는 합동식은 x를 3으로 나누면 나머지가 2라는 뜻입니다. 이 계산기는 이러한 식 세 개를 입력받아 모두를 동시에 만족하는 가장 작은 비음수 정수를 구합니다. 고전적인 정리는 법이 쌍마다 서로소일 때 적용되며, 이는 어느 두 법의 최대공약수도 일이라는 뜻입니다. 이 조건에서는 모든 법의 곱을 법으로 할 때 해가 정확히 하나입니다. 법이 3, 5, 7이면 곱은 105입니다. 최소 해가 23이면 23, 128, 233 및 105를 더하거나 빼서 얻는 모든 정수가 같은 연립합동식을 만족합니다. 구성적 알고리즘은 모든 법을 곱해 M을 구하는 것으로 시작합니다. 각 식마다 M을 해당 법으로 나누어 부분곱을 만듭니다. 법이 쌍마다 서로소이므로 부분곱은 제외한 법에 대한 모듈러 곱셈 역원을 가집니다. 각 나머지, 부분곱, 역원을 곱하면 한 합동식을 만족하면서 다른 법에 대해서는 영이 되는 항을 얻습니다. 이 항들을 더한 뒤 M으로 나눈 나머지가 답입니다. CRT는 교과서의 정수론을 넘어 다양하게 활용됩니다. 효율적인 큰 정수 연산, 암호 구현, 부호 이론, 달력 주기, 교대 일정, 컴퓨터 대수, 나머지로부터 값 복원 등에 쓰입니다. 어려운 계산을 여러 법에 대한 작고 독립적인 계산으로 나눈 다음 다시 결합할 수 있을 때 특히 유용합니다. 정수 나머지와 일보다 큰 법을 입력하세요. 나머지는 음수이거나 법보다 커도 되며, 모듈러 연산으로 자동 정규화됩니다. 이 버전은 표준 정리에 맞추고 유일한 잉여류를 보장하기 위해 법이 쌍마다 서로소여야 합니다. 서로소가 아닌 법의 연립합동식도 풀리는 경우가 있지만 추가적인 양립 조건 확인이 필요하므로 이 계산기의 범위에 포함되지 않습니다. 결과를 각 법으로 나눈 나머지를 확인하여 항상 검산하세요.