위키득계정 ↗
과학

합동식

합동식과학
영문명
Congruence
표기
a≡b (mod m)
정의 조건
m이 a−b를 나눔
이 문서의 범위
양의 정수 m을 법으로 하는 정수 관계
정수의 합동식은 두 정수를 같은 양의 정수로 나누었을 때 나머지가 같다는 관계를 나타낸다. a≡b (mod m)은 a−b가 m의 배수라는 뜻이다.

같은 나머지

17과 5를 6으로 나누면 나머지가 모두 5다. 따라서 17≡5 (mod 6)이라고 쓴다. 두 수 자체가 같다는 뜻은 아니며 차이 12가 6의 배수라는 뜻이다.

음수도 포함하는 관계

−1과 5의 차이는 −6이므로 −1≡5 (mod 6)이다. 정수 합동 관계는 양의 수에만 적용되는 것이 아니다. 나머지를 0 이상 m 미만으로 택하는 방식과 언어별 나머지 연산자의 규칙은 구별해야 한다.

덧셈과 곱셈

같은 법에서 합동인 값은 덧셈과 곱셈 계산에서 바꾸어 사용할 수 있다. 17≡5, 8≡2 (mod 6)이므로 합은 25≡7≡1, 곱은 136≡10≡4 (mod 6)이다. 계산 중간에 작은 나머지로 줄여도 된다.

약분할 때의 조건

합동식에서는 0이 아닌 수라도 마음대로 약분할 수 없다. 2와 8은 법 6에서 합동이지만 양쪽을 2로 나눈 1과 4는 합동이 아니다. 법과 서로소인 인수는 역원을 이용해 소거할 수 있다.

관련 문서

정수 / 나머지 / 배수 / 약수 / 서로소 / 최대공약수 / 동치류 / 동치변형