Congruence   합동

1. 합동 (合同, Congruence)

  ㅇ 동등,같음 등을 의미하는 광의의 수학 용어
     - 합동은 `같다` 이상의 광의의 개념으로써, 동일한 크기 및 모양/형태를 갖음을 나타냄
        . 기호로는 `≡` 또는 ``
        . 등식 기호 `=`의 일반화로 봄

  ㅇ [기하학]
     - 합동(Congruence) : 크기와 모양이 같으나 위치 만 다름 ( ≡ 또는  )
        . 적당히 이동(등거리 변환)시켜 포개면 정확하게 겹쳐짐
     - 닮음(Similarity) : 같은 모양을 갖지만, 크기가 다름   ( ~  )
        . 서로 대응하는 두 변의 비율이 일정하고, 대응하는 각은 모두 같음
 
  ㅇ [대수학/정수론]
     - 두 정수 a,b 에 대해, 그들의 차가 0 이면, a,b 는 같다 이라고 함 
     - 두 정수 a,b 에 대해, 그들의 차가 m 의 배수이면, a,b 는 합동 이라고 함
     * 이는 사실상, 정수가,
        . 일정한 수로 나눈 `나머지`에 만 의존하며, 
        . 이들을 통해 동등함을 일반화시켜 말하려는 것임


2. [정수론]  합동식

  ※ 19세기초 가우스(Karl Friedrich Gauss,1777~1855)가 최초로 도입한 기호(≡) 및 개념

  ㅇ 합동식 표기 :  a ≡ b (mod m)

     - 각 항들은 다음과 같이 주어짐
        .  a,b ∈ Z, m ∈ N
        .  a - b 가 m 의 배수, 즉 n | (a - b)

     - 위 합동식의 다양한 표현들
        .  `a는 법 m으로 b와 합동 (a is congruent to b modulo m)`
        .  `a,b는 법(法,Modulus) m에 대해 합동` 
        .  `임의의 정수 b는 {0,1,2,...,m-1} 중의 어느 한 정수와 법 m에 대해 합동`
        .  `합동 모듈러 m (법 m에 관한 합동) (Congruent Modulo m)`

     - 위 합동식의 의미상 동치/동등인 진술들
        . 정수 a,b의 차 (a-b)가 양의 정수 m 으로 나누어 떨어짐
           .. 즉,  m | (a-b)   (☞ 약수 참조)
        . 정수 쌍 a,p 또는 a,q는 양의 정수(자연수) m으로 나누었을 때, 같은 나머지 r를 갖음
           .. 즉,  a = p m + r, a = q m + r   (0≤r＜m)

  ㅇ 例
     - 例 1) 3  ≡ 24 (mod 7) : 정수 3,24의 차가 7로 나누어 떨어짐
     - 例 2) 42 ≠ 5 (mod 8)  : 정수 42,5의 차가 8로 나누어 떨어지지 않음
     - 例 3) 손목시계,표준시계가 나타내는 시간은 모듈로 12시간으로하여 합동
     - 例 4) 13 ≡ 25 (mod 12) : 13과 25는 12로 나누면 모두 나머지가 1이므로, 12에 대해 합동


3. [정수론]  합동의 성질

  ㅇ  a ≡ a (mod n)

  ㅇ  a ≡ b (mod n) 이면,  b ≡ a (mod n) 

  ㅇ  a ≡ b (mod n) 이고  b ≡ c (mod n) 이면,  a ≡ c (mod n)

  ㅇ  a + c ≡ b + c (mod n)

  ㅇ  a c ≡ b c (mod n)
     -  단, 위 식이 성립한다고 해서,  a ≡ b (mod n)도 성립하는 것은 아님
        . 例) 15·2 ≡ 20·2 (mod 10) (O), 15 ≢ 20 (mod 10) (X)

  ㅇ  a ≡ b (mod n), c ≡ d (mod n) 일 때,
     -  a + c ≡ b + d (mod n)
     -  a c ≡ b d (mod n)

  ㅇ  ak ≡ bk (mod n)  (k는 임의 자연수)


4. [정수론]  합동 관련 용어

  ㅇ 합동식 (Congruence Expression)          ☞ 모듈러 연산식 참조
     - 합동을 나타내는 기호 ≡가 들어있는 식

  ㅇ 합동 방정식 (Congruence Equation)
     - 합동식에 미지수 x가 들어있는 방정식
        . 例) x2 + 2x -1 ≡ 0 (mod n) 

     * 통상의 방정식과 유사하게 취급됨 

  ㅇ 합동류 (Congruence class)
     - a가 주어지고 그때의 b의 모든 집합    ☞ 잉여류

  ㅇ 합동의 유용성
     - 수의 나누어떨어짐(Divisibility)을 쉽게 나타냄
     - 합동에 의해, 마치 방정식 이론과 유사하게 합동 방정식 이론 전개가 가능해짐