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

중국인의 나머지 정리(CRT)를 사용하여 연립 합동식을 풀어주는 강력한 정수론 도구인 중국인의 나머지 정리 계산기에 오신 것을 환영합니다. 모듈러 산술을 공부하든, 수학 경시 대회를 준비하든, 암호학 문제를 풀든, 정수론을 탐구하든 이 계산기는 유일한 해에서 합동 클래스가 어떻게 정렬되는지 보여주는 대화형 시각화와 함께 완전한 단계별 솔루션을 제공합니다.

중국인의 나머지 정리란 무엇인가요?

중국인의 나머지 정리(CRT)는 법(moduli)들이 쌍마다 서로소인 경우 연립 합동식에 대한 해의 존재성과 유일성을 보장하는 정수론의 기본 결과입니다. 이 정리는 3세기경 중국의 수학자 손자(孫子)가 그의 저서 손자산경(孫子算經)에서 처음으로 기술했습니다.

공식적으로 다음과 같은 연립 방정식이 주어졌을 때:

모든 법 \(m_1, m_2, \ldots, m_k\)가 쌍마다 서로소(즉, 모든 \(i \neq j\)에 대해 \(\gcd(m_i, m_j) = 1\))이면, 법 \(M = m_1 \times m_2 \times \cdots \times m_k\)에 대해 유일한 해 \(x\)가 존재합니다.

CRT 알고리즘의 작동 원리

구성적 증명은 이 계산기에서 사용하는 알고리즘을 제공합니다:

1단계: M 계산

모든 법의 곱을 계산합니다:

2단계: 각 Mᵢ 계산

각 합동식 \(i\)에 대해, \(M_i = M / m_i\)를 계산합니다. 이는 \(m_i\)를 제외한 모든 법의 곱입니다.

3단계: 모듈러 역원 구하기

각 \(i\)에 대해, 확장 유클리드 알고리즘을 사용하여 \(M_i \cdot y_i \equiv 1 \pmod{m_i}\)를 만족하는 \(y_i\)를 찾습니다. \(M_i\)와 \(m_i\)는 서로소이므로(모든 법이 쌍마다 서로소이기 때문), 이 역원은 항상 존재합니다.

4단계: 해 구성

일반해는 임의의 정수 \(k\)에 대해 \(x + k \cdot M\)이며, 이는 해가 매 \(M\) 정수마다 반복됨을 의미합니다.

이 계산기 사용 방법

1. 합동식 입력: 각 방정식 \(x \equiv a \pmod{m}\)에 대해 나머지 \(a\)와 법 \(m\)을 입력합니다. 2개의 합동식으로 시작하여 더 많은 경우 "합동식 추가"를 클릭합니다(최대 10개).
2. 법 확인: 모든 법은 2 이상의 양의 정수여야 하며 쌍마다 서로소여야 합니다. 계산기가 자동으로 이를 확인합니다.
3. "연립방정식 풀기" 클릭: 계산기가 CRT 알고리즘을 적용하고 단계별 풀이 과정과 함께 유일한 해를 보여줍니다.
4. 시각화 검토: 수직선은 각 방정식의 합동 클래스가 해에서 어떻게 교차하는지 보여줍니다.
5. 검증: 검증 섹션은 해가 모든 원래 합동식을 만족하는지 확인합니다.

결과 이해하기

• 최소 비음수 해 (x₀): [0, M−1] 범위 내의 유일한 해
• 일반해: k가 임의의 정수인 x₀ + kM 형태의 모든 정수
• 검증 테이블: 각 합동식에 대해 x₀ mod mᵢ = aᵢ임을 확인
• 단계별 분석: 각 방정식에 대한 Mᵢ, 모듈러 역원 yᵢ, 부분합 aᵢ·Mᵢ·yᵢ를 표시
• 수직선: 해에서 나머지 클래스가 어떻게 정렬되는지 시각적으로 표현

중국인의 나머지 정리의 응용

고전적인 손자 문제

손자산경의 원본 문제는 다음과 같습니다: "개수를 알 수 없는 물건들이 있다. 셋씩 세면 둘이 남고, 다섯씩 세면 셋이 남고, 일곱씩 세면 둘이 남는다. 물건은 모두 몇 개인가?"

이를 식으로 나타내면: \(x \equiv 2 \pmod{3}\), \(x \equiv 3 \pmod{5}\), \(x \equiv 2 \pmod{7}\)입니다. CRT를 사용하면 답은 x = 23 (일반적으로는 비음수 정수 k에 대해 23 + 105k)입니다.

CRT를 적용할 수 없는 경우

• 서로소가 아닌 법: 법의 쌍이 1보다 큰 공약수를 공유하는 경우, 표준 CRT는 해를 보장하지 않습니다. 나머지가 호환되는 경우 해가 존재할 수도 있지만, 이 계산기는 표준 알고리즘을 위해 쌍마다 서로소인 법을 요구합니다.
• 단일 합동식: CRT는 최소 2개의 합동식이 필요합니다. 단일 합동식 \(x \equiv a \pmod{m}\)은 이미 자명한 해 x = a를 갖습니다.

확장 유클리드 알고리즘

확장 유클리드 알고리즘은 모듈러 역원을 찾는 데 필요하므로 CRT에 필수적입니다. 정수 \(a\)와 \(b\)가 주어졌을 때, 다음을 만족하는 정수 \(x\)와 \(y\)를 찾습니다:

\(\gcd(a, b) = 1\)일 때, \(x\)는 법 \(b\)에 대한 \(a\)의 모듈러 역원입니다. 즉, \(a \cdot x \equiv 1 \pmod{b}\)입니다.

자주 묻는 질문

중국인의 나머지 정리란 무엇인가요?

중국인의 나머지 정리(CRT)는 법들이 쌍마다 서로소인 연립 합동식 x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₖ (mod mₖ)가 있을 때, 법 M = m₁ × m₂ × ... × mₖ에 대해 유일한 해가 존재한다는 정리입니다. 이 정리는 3세기 중국의 수학자 손자에 의해 처음 기술되었습니다.

쌍마다 서로소란 무엇을 의미하나요?

쌍마다 서로소란 모든 법의 쌍이 1 이외의 공약수를 갖지 않는다는 것을 의미합니다. 예를 들어 {3, 5, 7}은 gcd(3,5)=1, gcd(3,7)=1, gcd(5,7)=1이므로 쌍마다 서로소입니다. 그러나 {4, 6, 5}는 gcd(4,6)=2이므로 쌍마다 서로소가 아닙니다.

연립 합동식을 단계별로 어떻게 푸나요?

CRT를 사용하여 푸는 방법: (1) 모든 법이 쌍마다 서로소인지 확인합니다. (2) M = 모든 법의 곱을 계산합니다. (3) 각 합동식에 대해 Mᵢ = M/mᵢ를 계산합니다. (4) 확장 유클리드 알고리즘을 사용하여 법 mᵢ에 대한 Mᵢ의 모듈러 역원 yᵢ를 찾습니다. (5) 해 x = Σ(aᵢ × Mᵢ × yᵢ) mod M을 계산합니다. 일반해는 임의의 정수 k에 대해 x + k×M입니다.

중국인의 나머지 정리의 응용 분야는 무엇인가요?

CRT는 실질적인 응용 분야가 많습니다: RSA 암호화에서 효율적인 복호화를 위해 사용됩니다. 컴퓨터 과학에서 계산을 작은 모듈러 조각으로 나누어 큰 수 산술에 사용합니다. 신호 처리에서 오류 정정 코드에 적용되며, 서로 다른 간격으로 반복되는 이벤트의 스케줄링 및 달력 문제에도 사용됩니다.

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

법이 쌍마다 서로소가 아닌 경우 표준 CRT를 직접 적용할 수 없습니다. 어떤 경우에는 특정 호환성 조건이 충족되면 해가 존재할 수 있지만, 그렇지 않으면 연립 합동식은 일치하지 않으며 해가 없습니다.

추가 자료

• 합동 산술 - 위키백과