가장 작은 해
법
법들

    합동식

    중국인의 나머지 정리 더 알아보기

    중국인의 나머지 정리 풀이기

    물건 더미를 셋씩 세면 2개가 남고, 다섯씩 세면 3개, 일곱씩 세면 2개가 남습니다. 물건은 23개, 또는 128개, 또는 233개로, 105마다 답이 하나씩 있습니다. 이것이 중국인의 나머지 정리라는 이름을 낳은 『손자산경』의 문제입니다. 원하는 만큼의 식과 원하는 만큼 큰 수로 연립 합동식 x ≡ a (mod n)을 입력하면, 답과 여러분의 수로 쓴 풀이, 그리고 왜 성립하는지 보여 주는 그림을 볼 수 있습니다. 모든 식이 동시에 성립할 수 없으면, 풀이기는 서로 부딪치는 두 식을 짚어 주고 그 이유를 보여 줍니다. 합동식 x ≡ a (mod n)을 한 줄에 하나씩 입력하세요. a는 나머지, n은 법입니다. '식 추가'를 누르거나 마지막 법에서 Enter를 누르면 줄이 추가되고, ×로 지울 수 있습니다. 200자리까지의 정수를 쓸 수 있고 a는 음수여도 됩니다. 예제를 고를 수도 있습니다. 타일에는 가장 작은 해와 그 해가 몇마다 반복되는지가 나오고, 그 아래에 처음 몇 개의 양의 해와 각 식의 검산이 나옵니다. 그림은 각 식을 만족하는 수에 표시를 하며, 모든 행에 표시가 있는 열이 해입니다. 나머지 표는 두 식을 한꺼번에 보여 줍니다. 풀이는 교과서의 구성법이나 대입법으로 여러분의 수를 써서 적힙니다.

    작동 원리

    1. 합동식 x ≡ a (mod n)을 한 줄에 하나씩 입력하거나, 손자의 문제, 달걀 바구니, 율리우스 주기 같은 예제를 고르세요.
    2. 가장 작은 해, 그 해가 반복되는 법, 처음 몇 개의 양의 해를 읽으세요. 각 해는 모든 식으로 검산되어 있습니다.
    3. 구성법이나 대입법으로 풀이를 한 단계씩 따라가고, 그림을 수직선과 나머지 표 사이에서 바꿔 보세요.

    구성법은 어떻게 작동하나

    어떤 두 법도 공약수가 없으면 해를 바로 만들 수 있습니다. 법들을 곱하세요. 손자의 문제에서는 N = 3 × 5 × 7 = 105입니다. 각 식마다 다른 모든 법의 배수인 Nᵢ = N / nᵢ를 잡습니다. 35, 21, 15입니다. 그다음 확장 유클리드 호제법으로 Nᵢ의 mod nᵢ 역원 yᵢ를 구합니다. 35를 3으로 나누면 2가 남고 2 × 2 = 4 ≡ 1 (mod 3)이므로 y₁ = 2이고, 21과 15는 나머지가 1이므로 역원은 1입니다. 그러면 x = 2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1 = 233이고 233 mod 105 = 23입니다. 각 항은 자기 식에 맞고 다른 법들의 배수이므로, 합은 모든 식에 맞습니다.

    법들이 공약수를 가질 때

    법들이 공약수를 가진 연립 합동식에도 해가 있을 수 있습니다. 두 식 x ≡ a (mod m)과 x ≡ b (mod n)이 동시에 성립하는 것은 a − b가 gcd(m, n)의 배수일 때뿐이며, 이때 해는 m × n마다가 아니라 lcm(m, n)마다 반복됩니다. 5분과 11분에 출발해 12분마다, 18분마다 다니는 두 버스는 29분에 만나고 그 뒤로 36분마다 만납니다. 11 − 5 = 6이 gcd(12, 18) = 6의 배수이기 때문입니다. 하지만 x ≡ 1 (mod 4)와 x ≡ 4 (mod 6)는 결코 함께 성립할 수 없습니다. 앞의 식은 x를 홀수로, 뒤의 식은 짝수로 만들기 때문입니다. 연립 합동식 전체에 해가 있는 것은 모든 두 식의 쌍에 해가 있을 때뿐이며, 풀이기는 이렇게 서로 부딪치는 두 식을 찾습니다.

    자주 묻는 질문

    중국인의 나머지 정리는 무엇을 말하나요?

    법 n₁, n₂, … 중 어떤 두 개도 공약수가 없으면, 아무 나머지 a₁, a₂, …에 대해서도 모든 i에서 x ≡ aᵢ (mod nᵢ)인 x가 0부터 N − 1 사이에 정확히 하나 있습니다. 여기서 N은 법들의 곱입니다. 다른 모든 해는 그 해와 N의 배수만큼 차이가 납니다. 손자의 문제의 해는 23, 128, 233, …으로 105마다 하나씩입니다.

    왜 '중국인의' 정리라고 부르나요?

    이런 종류의 문제 중 가장 오래된 것은 3~5세기에 쓰인 중국 산학서 『손자산경』에 있습니다. 셋씩, 다섯씩, 일곱씩 세면 어떤 물건이 2, 3, 2개 남는다는 문제입니다. 진구소는 1247년에 이런 문제의 일반적인 풀이법을 내놓았고, 카를 프리드리히 가우스는 1801년에 정리를 현대적인 형태로 서술했습니다.

    법들이 서로소가 아니면 어떻게 되나요?

    그러면 해가 없을 수도 있고, 해가 있더라도 법들의 곱마다가 아니라 최소공배수마다 반복됩니다. 두 식은 나머지가 두 법의 gcd를 법으로 같을 때 서로 맞습니다. 달걀 문제는 공약수를 가진 2, 3, 4, 5, 6, 7을 쓰지만 그래도 해가 있습니다. 바로 301이고, 420마다 반복됩니다.

    RSA는 중국인의 나머지 정리를 어떻게 쓰나요?

    RSA 메시지를 복호화한다는 것은 n = p × q일 때 c^d mod n을 계산하는 것입니다. 지수를 mod p − 1과 q − 1로 줄여 c^d mod p와 c^d mod q를 따로 계산하고, 두 결과를 정리로 합치는 편이 더 빠릅니다. 수의 길이가 절반이 되면 두 번의 거듭제곱 각각에 드는 일이 약 8분의 1이 되므로 복호화가 약 네 배 빨라지며, 대부분의 RSA 소프트웨어가 이 방법을 씁니다.

    수는 얼마나 클 수 있나요?

    식은 20개까지, 수는 각각 200자리까지입니다. 풀이기는 브라우저에서 정확한 정수로 계산하므로 답이 아무리 길어도 정확하며, 아무것도 어디로도 보내지 않습니다.

    시도해 볼 준비가 되셨나요?

    브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

    편집기로 이동