중국인의 나머지 정리 계산기: 나머지 시스템을 단계별로 풀기
중국인의 나머지 정리 계산기는 연립 합동식(x ≡ 2 (mod 3) 및 x ≡ 3 (mod 5)와 같은 진술)을 개별 법수의 곱(또는 최소공배수)를 법으로 하는 단일 합동식으로 결합하여 해결합니다. 이 방법은 중국의 고대 수학 저작인 《손자산경》에서 약 1,500년 전으로 거슬러 올라가며, 오늘날 RSA 암호화 최적화, 달력 계산 및 오류 정정 코드에 기초할 뿐만 아니라 이산 수학 및 수론 과정의 주축입니다. 이 가이드는 계산기가 내부적으로 어떻게 작동하는지, 시스템이 해를 가지는지 확인하는 방법, 이 방법이 의존하는 모듈로 역원을 찾는 방법, 서로소인 법수를 사용한 예와 그렇지 않은 예 2가지, 그리고 일반적인 실수 및 연습 문제를 다룹니다.
목차
중국인의 나머지 정리란 무엇인가?
중국인의 나머지 정리(CRT)는 연립 합동식 x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₙ (mod mₙ)이 있고 법수 m₁, m₂, ..., mₙ이 서로소(모든 쌍이 1 이외의 공약수를 갖지 않음)일 때, x에 대해 M = m₁ × m₂ × ... × mₙ를 법으로 하는 정확히 하나의 해가 존재한다는 것입니다. 이 정리는 3~5세기 중국의 저작인 《손자산경》(손자의 산술 매뉴얼)에서 가장 먼저 나타나는 것에서 이름이 붙었으며, 그 유명한 퍼즐을 제시합니다: 3으로 나누면 나머지 2, 5로 나누면 나머지 3, 7로 나누면 나머지 2가 되는 수를 찾으세요. 이 퍼즐(그리고 이를 푸는 CRT 방법)은 교실 밖에서 끊임없이 나타납니다: RSA 암호화는 하나의 거대한 법수 대신 더 작은 법수를 사용하여 복호화 속도를 높이기 위해 CRT를 사용하고, 컴퓨터 과학자들은 더 빠른 산술 연산을 위해 큰 수를 더 작은 잉여의 튜플로 표현하며, 달력 시스템은 서로 다른 길이의 주기(요일, 월의 날짜, 윤년 주기)를 조화시키기 위해 사용합니다.
중국인의 나머지 정리: 서로소인 법수 m₁, ..., mₙ에 대해, 연립식 x ≡ aᵢ (mod mᵢ)는 M = m₁ × m₂ × ... × mₙ를 법으로 정확히 하나의 해를 갖습니다.
중국인의 나머지 정리 계산기는 어떻게 작동하는가?
중국인의 나머지 정리 계산기는 특히 시스템에 3개 이상의 합동식이 있을 때 손으로 추적하기에 지루한 4가지 단계를 자동화합니다. 특히 모듈로 역원 계산이 중요합니다. 내부적으로, 각 합동식을 쌍(aᵢ, mᵢ)으로 취급하고, 법수가 함께 사용 가능함을 확인한 다음, 시행착오가 아닌 가중 합을 사용하여 고유한 해를 구축합니다. 이 4가지 단계를 이해하면 계산기의 출력을 검증하거나 계산기가 허용되지 않는 시험에서 같은 문제를 손으로 풀 수 있습니다.
1. 단계 1: 법수 확인
모든 법수 쌍이 서로소임을 확인합니다(gcd = 1). 어떤 쌍이 공약수를 가지면, 계산기는 표준 공식 대신 다음 섹션에서 설명하는 호환성 확인으로 전환합니다.
2. 단계 2: 결합 법수 M 계산
모든 법수를 곱합니다: M = m₁ × m₂ × ... × mₙ. 이는 최종 결합 답의 법수입니다.
3. 단계 3: 각 부분 곱과 역원 찾기
각 합동식 i에 대해, Mᵢ = M / mᵢ(mᵢ를 제외한 모든 법수의 곱)을 계산한 다음, Mᵢ의 mᵢ에 대한 모듈로 역원을 찾습니다. 이를 yᵢ라 하며, Mᵢ × yᵢ ≡ 1 (mod mᵢ)를 만족합니다.
4. 단계 4: 결합 및 축소
모든 합동식에서 aᵢ × Mᵢ × yᵢ를 합산한 다음, 그 합을 M으로 축소하여 최소 음이 아닌 해 x를 얻습니다.
모든 중국인의 나머지 정리 계산기 뒤의 공식: x ≡ Σ (aᵢ × Mᵢ × yᵢ) mod M, 여기서 Mᵢ = M/mᵢ이고 yᵢ는 Mᵢ의 mᵢ에 대한 모듈로 역원입니다.
법수가 호환되는지 어떻게 확인하는가?
중국인의 나머지 정리의 교과서 버전은 서로소인 법수를 요구하지만, 실제 시스템(특히 일정 계획이나 암호화 문제에서 나타나는 것)은 종종 인수를 공유하는 법수를 가집니다. 일반화된 CRT 버전도 여전히 적용되지만, 시스템이 먼저 호환성 확인을 통과한 경우만입니다: 모든 합동식 쌍 x ≡ aᵢ (mod mᵢ)와 x ≡ aⱼ (mod mⱼ)에 대해, 두 식은 겹치는 부분에서 일치해야 합니다. 즉, aᵢ ≡ aⱼ (mod gcd(mᵢ, mⱼ))입니다. 이 확인이 한 쌍에서라도 실패하면, 시스템은 완전히 해가 없으며, 좋은 계산기는 잘못된 숫자를 반환하는 대신 이를 보고합니다.
1. 단계 1: 각 법수 쌍에 대해 gcd(mᵢ, mⱼ) 계산
2개의 합동식 시스템에서는 확인할 쌍이 하나뿐입니다. 3개의 합동식 시스템에서는 세 쌍 모두를 확인하세요.
2. 단계 2: 그 gcd를 법으로 두 잉여 축소
aᵢ mod gcd(mᵢ, mⱼ)와 aⱼ mod gcd(mᵢ, mⱼ)를 취합니다. 일치하면 쌍은 호환됩니다.
3. 단계 3: 호환되지 않는 시스템의 예
x ≡ 1 (mod 4)와 x ≡ 0 (mod 6)을 고려합니다. gcd(4, 6) = 2. 축소: 1 mod 2 = 1, 0 mod 2 = 0. 1 ≠ 0이므로, 두 합동식을 모두 만족하는 정수가 없으며, 시스템은 해가 없으며, 중국인의 나머지 정리 계산기는 이를 정확히 플래그해야 합니다.
서로소가 아닌 법수에 대한 호환성 규칙: x ≡ aᵢ (mod mᵢ)와 x ≡ aⱼ (mod mⱼ)이 모두 참일 수 있는 것은 aᵢ ≡ aⱼ (mod gcd(mᵢ, mⱼ))일 때만입니다.
모듈로 역원이란 무엇이고 어떻게 찾는가?
법 m에 대한 수 a의 모듈로 역원은 a × b ≡ 1 (mod m)을 만족하는 또 다른 수 b입니다. 이는 일반 나눗셈에서 1/a가 하는 역할을 하지만, 고정된 법 내의 정수에만 국한됩니다. 모듈로 역원은 gcd(a, m) = 1일 때만 존재하며, 이는 표준 중국인의 나머지 정리가 서로소인 법수를 요구하는 이유입니다: 모든 Mᵢ가 mᵢ에 대한 역원을 가짐을 보장합니다. 손으로 모듈로 역원을 찾는 가장 신뢰할 수 있는 방법은 확장 유클리드 호제법으로, 보통의 gcd 알고리즘을 앞으로 실행한 다음 역으로 작업하여 1을 a와 m의 조합으로 표현합니다.
1. 단계 1: 유클리드 호제법을 앞으로 실행
4 mod 7의 역원을 찾습니다. 반복적으로 나눕니다: 7 = 1×4 + 3, 그 다음 4 = 1×3 + 1, 그 다음 3 = 3×1 + 0. 나머지는 3, 그 다음 1, 그 다음 0입니다. gcd(4, 7) = 1임을 확인하므로 역원이 존재합니다.
2. 단계 2: 역으로 작업하여 1 분리
두 번째에서 마지막 줄부터, 1 = 4 − 1×3. 첫 번째 줄에서 3 = 7 − 1×4를 대입: 1 = 4 − 1×(7 − 1×4) = 2×4 − 1×7.
3. 단계 3: 역원 읽기
방정식 1 = 2×4 − 1×7은 2×4 ≡ 1 (mod 7)을 의미하므로, 4 mod 7의 역원은 2입니다. 빠른 확인: 4 × 2 = 8 = 7 + 1, 이는 정확히 ≡ 1 (mod 7)입니다.
작은 법수의 경우, 후보를 직접 테스트하는 것이 더 빠를 수 있습니다: a에 1, 2, 3, ...을 m을 법으로 곱해서 곱이 1이 될 때까지 계속합니다. 더 큰 법수의 경우, 확장 유클리드 호제법이 훨씬 더 신뢰할 수 있습니다.
연습 예제: 서로소인 합동식 풀기
이는 고전적인 손자산경 문제입니다: x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)을 만족하는 x를 찾으세요. 법수 3, 5, 7은 서로소이므로 표준 CRT 공식이 직접 적용됩니다.
1. 단계 1: M 계산
M = 3 × 5 × 7 = 105.
2. 단계 2: 각 Mᵢ과 그 역원 계산
M₁ = 105/3 = 35. 35 mod 3 = 2, 2 mod 3의 역원은 2입니다(2×2 = 4 ≡ 1 mod 3). M₂ = 105/5 = 21. 21 mod 5 = 1, 1 mod 5의 역원은 1입니다. M₃ = 105/7 = 15. 15 mod 7 = 1, 1 mod 7의 역원은 1입니다.
3. 단계 3: 결합
x ≡ (a₁×M₁×y₁) + (a₂×M₂×y₂) + (a₃×M₃×y₃) mod M = (2×35×2) + (3×21×1) + (2×15×1) mod 105 = 140 + 63 + 30 mod 105 = 233 mod 105 = 23.
4. 단계 4: 검증
23 ÷ 3 = 7 나머지 2 ✓. 23 ÷ 5 = 4 나머지 3 ✓. 23 ÷ 7 = 3 나머지 2 ✓. 최소 음이 아닌 해는 x = 23이며, 다른 모든 해는 임의의 정수 k에 대해 23 + 105k입니다.
x ≡ 23 (mod 105)—중국인의 나머지 정리 계산기가 즉시 반환하는 같은 답이며, 1,000년 이상 전에 이 수학 분야를 열었던 같은 퍼즐입니다.
연습 예제: 서로소가 아닌 법수 조화시키기
이제 x ≡ 3 (mod 4)와 x ≡ 1 (mod 6)을 풀어보세요. 4와 6은 서로소가 아닙니다(2의 인수를 공유합니다). 서로소인 예제의 표준 공식이 직접 적용되지 않지만, 시스템이 먼저 호환성 확인을 통과하면 여전히 법수의 최소공배수를 법으로 하는 고유한 해를 가질 수 있습니다.
1. 단계 1: 호환성 확인
gcd(4, 6) = 2. 두 잉여를 축소: 3 mod 2 = 1, 1 mod 2 = 1. 일치하므로 시스템은 호환되며 해가 존재합니다.
2. 단계 2: 결합 법수 찾기
4 × 6 = 24 대신, 최소공배수를 사용합니다: lcm(4, 6) = 12. 해는 24가 아닌 12를 법으로 하는 고유한 해가 됩니다.
3. 단계 3: 대입하고 풀기
첫 번째 합동식에서 x = 4k + 3을 쓰고, 두 번째에 대입: 4k + 3 ≡ 1 (mod 6), 따라서 4k ≡ −2 ≡ 4 (mod 6). 양변과 법수가 gcd(4, 6) = 2의 인수를 공유하므로, 전체 합동식을 2로 나눕니다: 2k ≡ 2 (mod 3). 2 mod 3의 역원은 2이므로, k ≡ 2×2 ≡ 1 (mod 3).
4. 단계 4: x 재구성
임의의 정수 j에 대해 k = 3j + 1이므로, x = 4(3j + 1) + 3 = 12j + 7. 최소 음이 아닌 해는 x = 7입니다.
5. 단계 5: 검증
7 mod 4 = 3 ✓. 7 mod 6 = 1 ✓. 따라서 x ≡ 7 (mod 12)가 정확하며, 법수가 공약수를 공유할 때—서로소가 아닌 CRT가 작동하는—합동식을 공약수로 나누는 단계입니다.
법수가 공약수를 공유할 때, 서로소인 공식을 그대로 사용할 수 없습니다. 역원을 찾기 전에 결과 합동식을 gcd(mᵢ, mⱼ)로 나누어야 합니다. 그렇지 않으면 역원이 존재하지 않습니다.
최소 음이 아닌 해 재구성
호환성 확인을 통과한 모든 중국인의 나머지 정리 시스템은 1이 아닌 무한히 많은 정수 해를 가집니다. 그러나 그들은 모두 M을 법으로 서로 합동입니다(또는 서로소가 아닌 경우 lcm(m₁, ..., mₙ)를 법으로 합동). 관례적으로, 계산기는 그 무한 집합의 최소 음이 아닌 대표인 값 x₀(0 ≤ x₀ < M을 만족)를 보고합니다. 왜냐하면 그것이 명시하기, 비교하기, 검증하기 가장 쉬운 단일 정규 답이기 때문입니다. 다른 모든 해는 x₀에 M의 배수를 더하거나 뺀 것입니다.
최소 음이 아닌 해 재구성
각 단계는 다음과 같습니다:
1. 음의 중간 합 축소
계산기 메서드의 단계 4의 가중 합은 임의의 잉여 aᵢ가 음수이거나 모듈로 역원이 음의 대표로 계산된 경우 음수가 될 수 있습니다. 합이 예를 들어 S = −37이고 M = 45인 경우, 결과가 음이 아닐 때까지 M을 반복적으로 더합니다: −37 + 45 = 8, 최소 음이 아닌 해는 x₀ = 8입니다. −37이 아닙니다.
2. 전체 해 집합
x₀을 얻은 후, 전체 해 집합은 k = ..., −2, −1, 0, 1, 2, ...에 대해 x₀ + kM 형태의 모든 정수입니다. 위의 손자 예제에서, 그것은 23, 128, 233, ...이며 또한 −82, −187 등이지만, 특정 범위가 요청되지 않는 한 보고하는 것은 23입니다.
음수이거나 과도하게 큰 중간 결과는 잘못된 것이 아닙니다. 값이 [0, M)에 들어갈 때까지 M의 배수를 더하거나 빼십시오.
중국인의 나머지 정리의 가장 일반적인 실수는 무엇인가?
CRT 문제의 대부분의 오류는 최종 계산의 결함이 아닌 확인을 건너뛰기에서 발생하므로, 문제의 끝이 아닌 시작 부분에서 속도를 늦추는 가치가 있습니다.
1. 서로소가 아닌 법수에 공식 적용
어떤 2개의 법수가 인수를 공유하면, M을 그들의 곱으로 계산하고 표준 방식으로 모듈로 역원을 찾으면 조용히 실패하거나 잘못된 답을 생성합니다. 항상 모든 쌍에 대해 먼저 gcd(mᵢ, mⱼ) = 1을 확인하세요.
2. 모듈로 역원을 일반 역수와 혼동
4 mod 7의 역원은 1/4가 아닌 2입니다. 모듈로 역원은 확장 유클리드 호제법(또는 작은 법수에서 시행 곱셈)으로 찾은 정수입니다. 절대 분수가 아닙니다.
3. 음수를 m을 법으로 올바르게 축소하지 않음
−2 mod 6은 4입니다. −2도 2도 아닙니다. 결과가 범위 [0, m)에 들어갈 때까지 법수를 계속 더하세요. 법수를 더하는 대신 절단하거나 절댓값을 취하는 것은 잘못된 답의 빈번한 원인입니다.
4. 서로소가 아닌 시스템에서 공약수로 나누기를 잊음
법수가 공약수를 공유할 때, 4k ≡ 4 (mod 6)과 같은 합동식은 역원을 찾기 전에 gcd(4, 6) = 2로 나누어야 합니다. 즉, 2k ≡ 2 (mod 3)가 됩니다. gcd(4, 6) ≠ 1이므로 4에는 mod 6의 역원이 전혀 없습니다.
5. 최종 합을 M으로 축소하는 것을 멈추지 않음
단계 4의 가중 합(예를 들어, 손자 문제에서 233)은 최종 답이 아닙니다. 최소 음이 아닌 해에 도달하려면 M으로 축소해야 합니다(233 mod 105 = 23).
당신의 답이 원래의 각 합동식에 다시 연결될 때 만족하지 않으면, 호환성 확인과 모듈로 역원을 먼저 다시 확인하세요. 거의 모든 CRT 실수가 실제로 일어나는 곳입니다.
연습 문제: 중국인의 나머지 정리 계산기 기술 테스트
아래의 3가지 시스템을 손으로 풀고, 먼저 서로소 또는 호환성을 확인한 후 아래의 솔루션과 비교하세요. 두 번째 문제는 의도적으로 풀 수 없습니다. 이를 인식하는 것은 해가 존재할 때 숫자 답을 찾는 것만큼 중요합니다.
1. 문제 1 (서로소)
풀기: x ≡ 1 (mod 3), x ≡ 4 (mod 5), x ≡ 6 (mod 7). 답: M = 105. M₁ = 35, 역원 2 mod 3; M₂ = 21, 역원 1 mod 5; M₃ = 15, 역원 1 mod 7. 합계 = (1×35×2) + (4×21×1) + (6×15×1) = 70 + 84 + 90 = 244. 244 mod 105 = 34. 확인: 34 mod 3 = 1 ✓, 34 mod 5 = 4 ✓, 34 mod 7 = 6 ✓. 해: x ≡ 34 (mod 105).
2. 문제 2 (서로소가 아닌 법수—해 없음)
풀기: x ≡ 2 (mod 8), x ≡ 5 (mod 12). gcd(8, 12) = 4. 축소: 2 mod 4 = 2, 5 mod 4 = 1. 2 ≠ 1이므로, 시스템은 호환되지 않으며 해가 없습니다. 중국인의 나머지 정리 계산기는 부정확한 숫자 대신 이 결론을 반환해야 합니다.
3. 문제 3 (호환되지만 서로소가 아닌 법수)
풀기: x ≡ 5 (mod 9), x ≡ 2 (mod 6). gcd(9, 6) = 3. 축소: 5 mod 3 = 2, 2 mod 3 = 2—호환. lcm(9, 6) = 18. x = 9k + 5로 쓰고 대입: 9k + 5 ≡ 2 (mod 6) → 9k ≡ −3 ≡ 3 (mod 6). gcd(9, 6) = 3으로 나누기: 3k ≡ 1 (mod 2) → k ≡ 1 (mod 2). 따라서 k = 2j + 1, x = 9(2j+1) + 5 = 18j + 14. 확인: 14 mod 9 = 5 ✓, 14 mod 6 = 2 ✓. 해: x ≡ 14 (mod 18). 이 같은 문제에서 모든 모듈로 역원과 축소 단계를 2배로 확인하려면, Solvify의 단계별 수학 풀이기가 이 가이드와 동일한 방식으로 각 단계를 설명합니다.
중국인의 나머지 정리에 대한 진정한 숙련도를 구축하는 가장 빠른 방법은 서로소, 서로소가 아니지만 호환, 및 호환되지 않는 시스템의 혼합을 푸는 것입니다. 어떤 경우에 있는지 인식하는 것은 기술의 절반입니다.
관련 게시물
나머지 정리 계산기: 나머지를 단계별로 찾는 방법
다르지만 관련된 나머지 개념—이 가이드는 다항식 나머지 정리를 다루며, 합동식 모듈로에 취급하기 전에 유용한 컨텍스트입니다.
가우스 소거법 계산기: 선형 시스템을 단계별로 풀기
또 다른 체계적인 알고리즘 기반 계산기 방법—가우스 소거법과 중국인의 나머지 정리가 각각 시스템을 단일 답으로 축소하는 방법의 비교.
단계별 수학 문제 해결: 모든 문제에 대한 반복 가능한 프레임워크
이 가이드의 5단계 프레임워크는 CRT 문제에 직접 적용됩니다: 주어진 것을 특정하고, 방법을 선택하고, 체계적으로 작업하고, 결과를 검증합니다.
관련 수학 풀이
스마트 스캔 솔버
합동식 또는 수론 문제의 사진을 찍고 즉시 단계별 중국인의 나머지 정리 솔루션을 받으세요.
단계별 솔루션
최종 나머지뿐만 아니라 모든 모듈로 역원, 호환성 확인, 축소 단계를 설명했습니다.
AI 수학 튜터
모듈로 역원, 서로소인 법수, 또는 시스템이 해를 가지지 않는 이유에 대해 후속 질문을 하고, 당신의 정확한 문제에 맞춘 답을 얻으세요.