확장 유클리드 알고리즘(ExGCD)의 원리와 활용

베주 항등식 (Bézout's Identity) 두 정수 \(a\)와 \(b\)의 최대공약수를 \(d = \gcd(a, b)\)라고 할 때, 다음 방정식을 만족하는 정수 \(x\)와 \(y\)가 반드시 존재합니다. \[ax + by = d\] 더 일반적으로 방정식 \(ax + by = c\)를 풀고자 할 때, \(c\)가 \(d\)의 배수가 아니라면 이 방정식은 정수 해를 가질 수 없습니다. 확장 유클리드 알고리즘의 유도 유클리 ...

10월 19일 17:51에 게시됨

확장된 중국인의 나머지 정리 구현

기본 원리: 중국인의 나머지 정리 (CRT) 주어진 연립 동치식을 만족하는 해 x를 찾는 문제이다: \[ \begin{cases} x \equiv a_1 \pmod{r_1} \\ x \equiv a_2 \pmod{r_2} \\ \vdots \\ x \equiv a_n \pmod{r_n} \end{cases} \] 여기서 각 모듈러스 \( r_i \)들은 서로소일 경우, 이 시스템은 유일한 해를 가진다. 이를 통해 전체 해를 구성할 수 있다. 각 \( i \)에 ...

5월 27일 12:33에 게시됨