나머지가 같은 경우조건 단순화 하기x ≡ b (mod m1), x ≡ b (mod m2), x ≡ b (mod m3)... 처럼 나머지 b가 같을 때는조건을 병합할 수 있다.x ≡ b (mod LCM(m1m2m3...))로 병합하고 풀자증명m1|x-b, m2|x-b, m3|x-b .... 이므로m1, m2, m3의 최소공배수로도 x-b는 나눠진다.이후 남은 식들이 단순하다면 그냥 한 식에 대해 x = m1k + b 꼴의 식을 구하고이걸 다른 식에 대입하며 푼다. 나머지가 다른 경우한 합동식에 대해 풀고 대입하기먼저 나머지가 가장 간단한 합동식에 대해 풀어 x=a1k1+b1를 구하고다음 식에 x대신 대입해서 k1 을 구한다.구한 k1으로 새로운 식 k1 = a2k2+k1을 만든다.이후 반복해서 모든 k를 ..

합동정의a ≡ b (mod m) 에서 ≡정수 a를 m으로 나눈 나머지가 b일때 a는 법 m에 대해 b와 합동이다a ≡ b (mod m) ⇔ (a - b) = mk (k는 정수)합동의 성질a1 ≡ b1 (mod m), a2 ≡ b2 (mod m)일때  ⇒ a1±a2 ≡ b1±b2 (mod m)     ⇒ a1a2 ≡ b1b2 (mod m)     ⇒ (gcd(a2, m) = 1, gcd(b2, m) = 1일떄만) a1/a2 ≡ b1/b2 (mod m)     ⇒ 물론 c ≡ c (mod m)에 대해서도 충분히 성립함 (상수 덧, 뺄, 곱셈에 대해 성립)  a ≡ b (mod m1), a ≡ b (mod m2) 이고 gcd(m1, m2) = 1이면    ⇒ a ≡ b (mod m1m2) (m1, m2 두 조..