어렸을 때 이런 문제를 푼 기억이 있다. "사탕 $N$개를 나눠주는데 $a$개씩 나눠주면 $m_1$개가 남고 $b$개씩 나눠주면 $m_2$개가 남을 때 사탕의 수를 구하시오." 그때는 직접 대입하거나 식을 세워서 풀었던거 같은데 중국인의 나머지정리로도 풀 수 있다. 중국인의 나머지 정리(Chinese Remainder Theorem) >> Theorem) $\gcd(m,n) = 1$이고 $x \equiv b \mod m$이고 $x \equiv c \mod n$이면 $x \equiv d \mod mn$인 $d$가 유일하게 존재한다. proof $x \equiv b \mod m$은 $x = my + b$로 쓸 수 있고 이를 두번째 식에 대입하면 $my + b = nz + c$가 된다. 이는 곧 $my - n..
