[정수론] 합동 (Congruence) 1부

Congruence 는 정수의 나머지 연산을 다루기위한 도구로서, 가우스에 의해 disquistiones Arithmeticae 에서 정립되었다.

def. congruence modulo m
a ≡ b (mod m)      denotes        m | (a-b)             ( that is,    a-b = km for some k   )

즉, a 와 b가 나머지연산에 있어 m으로 나누었을때, 같은 나머지(least nonnegative residue)를 갖는 것을 의미한다.

a ≡ b (mod m)  을 간단히 a  ≡_m  b 으로 나타내기도 한다.

---

위의 정의가 같은 나머지를 갖는 두 수를 의미하는지는 다음과 같이 확인해 볼 수 있다.

a = m s + r₁  ,   b  =  m t  +  r ₂   라고 하면...   a-b  =  m ( s- t) + r₁ -  r₂   이므로 , m | (a-b) 라는 말은  곧,  m | ( r₁ - r₂ ) 이 된다.

그런데,   - m  <   r₁ - r₂   <  m   이므로,    r₁ - r₂  =  0   밖에 없다.

---

합동관계 ( congruence relation ) 은 동치관계 ( equivalence relation ) 이다.  ( 참고 :  동치관계  )

pf.
a≡a (mod m)                                                          :    m | 0
a≡b (mod m)  ⇒  b≡a (mod m)                                :    m | (a-b)   ⇒    m | (b-a)
a≡b (mod m)  ∧  b≡c (mod m)  ⇒  a≡c (mod m)     :    a-b = km , b-c = lm  ∴ a-c = (k+l)m    즉, m | (a-c)

---

기본성질 ( 여기서 modulus 는 m 으로 고정하고 편의상 생략하기로 함. )

1)    a≡b ∧  c≡d      ⇒       a+c ≡ b+d
2)    a≡b ∧  c≡d      ⇒       ac ≡ bd
3)    a≡b                  ⇒       a^k ≡ b^k   (k∈N)

pf.
1)   a-b = km , c-d = lm    ∴ (a+c)-(b+d) = (k+l)m
2)   a-b = km , c-d = lm    ∴ ac - bc = kcm , bc - bd = blm      ∴ ac - bd = (kc + bl) m
3)   2) 에서 c≡d 대신 a≡b 를 넣고, k 번 적용하면 된다. 인덕션으로 증명.

---

simple technique
큰수의 나머지 계산에서, 계산과정중에 작은 나머지를 갖는 수를 발견하면, 위의 베이식 프라퍼티들을 이용하여, 언제든지 대체하여 사용할 수 있다.

---

예제.   2 ²⁰⁰⁸ 을 9로 나눈 나머지는?

풀이.   2 ³ ≡ -1  이므로,  양변을 제곱하면  2 ⁶ ≡ 1 이다.
          2008 ≡ 208 ≡ 28 ≡ 4 (mod 6) 이므로,    2 ²⁰⁰⁸   =   2 ^{6k + 4}   =    ( 2 ⁶ ) ^k  2 ⁴     ≡   16   ≡   7 (mod 9)
          따라서 나머지는 7 이 된다.