합동(수론)

누리위키, 온 누리의 백과사전
ProtArie (토론 | 기여)님의 2013년 10월 9일 (수) 14:18 판 (새 문서: 수론에서 두 정수 \(a\)와 \(b\)가 법(modulo) \(m\)에 대해서 '''합동'''(congruence)이라는 것은 다음을 만족한다는 것이다: \[m|(a−b).\] 이것을...)
(차이) ← 이전 판 | 최신판 (차이) | 다음 판 → (차이)

수론에서 두 정수 \(a\)와 \(b\)가 법(modulo) \(m\)에 대해서 합동(congruence)이라는 것은 다음을 만족한다는 것이다: \[m|(a−b).\] 이것을 다르게 표현하자면, \(a\)를 \(m\)으로 나눈 나머지와 \(b\)를 \(m\)으로 나눈 나머지가 같다는 뜻이다. 즉, 합동은 나머지가 같은 두 정수를 같은 수로 취급하는 동치 관계이다. 이것을 다음과 같이 표현한다: \[ a\equiv b\;(\operatorname{mod}m).\]

합동이 동치 관계임을 증명[편집]

  1. 반사 관계: \(m|0 \iff m|(a−a) \iff a≡a\;(\operatorname{mod}m).\)
  2. 대칭 관계: \(a\equiv b\;(\operatorname{mod}m) \Longrightarrow m|(a−b) \Longrightarrow m|(b−a) \Longrightarrow b\equiv a\;(\operatorname{mod}m).\)
  3. 추이 관계: \(a\equiv b,b\equiv c\;(\operatorname{mod}m)\Longrightarrow m|(a−b), m|(b−c)\Longrightarrow m|{(a−b)+(b−c)}\Longrightarrow m|(a−c)\Longrightarrow a\equiv c\;(\operatorname{mod}m).\)

성질 및 정리[편집]

이 문단에서는 무엇을 법으로 하는지는 생략하여 표현하겠다. \(a,b,c,d\)는 모두 정수이다.

  • \(a\equiv b\)이면, \(a\pm c\equiv b\pm c\)이다.
  • \(a\equiv b\)이면, \(ac\equiv bc\)이다.
  • \(a\equiv c\)이고 \(b\equiv d\)이면, \(a\pm b\equiv c\pm d\)이다.
  • \(a\equiv c\)이고 \(b\equiv d\)이면, \(ab\equiv cd\)이다.
  • \(a\equiv b\)이면, \(a^c\equiv b^c\)이다.
  • 법 \(m_1,m_2,\cdots,m_k\)에 대해서 각각 \(a\equiv b\)이라고 하자. 그러면 \(m_1,m_2,\cdots,m_k\)의 최소공배수 \(M\)을 법으로 해도 \(a\equiv b\)이다. 즉, \(a\equiv b\;(\operatorname{mod}M)\)이 성립한다.

같이 보기[편집]