[정수론](6)[합동]

합동

• 정의
  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 두 조건을 모두 포함한다.)

 

합동방정식

• 합동방정식이 항상 해를 가지는가? -> 거짓
  ax ≡ b (mod m)에서 gcd(a, m)이 b를 나누지 않는다면 안가짐
  ⇔ ax ≡ (gcd(a, m)) (mod m)은 항상 해를 가진다
• 합동방정식의 모든 해 구하기
  ax ≡ b (mod m) ⇔ (a - b) = mk (k는 정수)이므로 선형방정식 정리에 의해
  gcd(a, m) = g에 대해
  au+mv=g에서 항상 해 u, v를 구할 수 있다.
  여기서 우리가 원하는 꼴을 만들어주기 위해 b/g를 곱하면
  a(bu/g)+m(bv/g)=b
  따라서 x0 = bu/g
  다른 해는 ax0 ≡ ax1 (mod m)이므로 x1 = x0 + mk/g (k = 0~g-1)

 

선형합동방정식 정리

a, b가 정수고 m이 1보다 클 때, a ≡ b (mod m)에서

• gcd(a, m)∤b이라면 해를 가지지 않는다
• gcd(a, m)|b라면 합동방정식은
  정확히 (0~m-1 범위에서) gcd(a, m)개의 서로 다른 해를 가진다
  이때 해는 au+mv = b 의 해 u, v를 찾고
  x0 = bu/g, 다른 해는 x = x0 + mk/g (k = 0~g-1) (g = gcd(a, m))

 

고차합동방정식

-> 풀기 매우 어려움
차수가 d인 고차합동방정식의 서로 다른 해의 개수는 최대 d다

• 증명
  귀류법으로 증명해보자~
  최고차항이 p로 나누어떨어지지 않는 다항식 f(x)가 있을때,
  f(x) ≡ 0 (mod m)이 d보다 많은 수의 해를 가진다 가정하자.
  이때 f(x)는 해당 가정을 만족하는 다항식 중 차수가 가장 낮은 다항식이라 하자.
  f(x) = a(0)x^d + a(1)x^d-1 + ... + a(d)
  f(x)-f(r1) = (x-r1)(d-1차 다항식 g(x))로 인수분해된다.
  f(rk)-f(r1) = (rk - r1) g(rk)에서 k!=1이면 r1 ≡ rk (mod m)이 아니다. 즉 r2, ... rd+1이 g(x)의 해다.
  이때 f(x)가 가정을 만족하는 가장 작은 차수의 다항식이라고 하였는데 더 작은 차수의 조건을 만족하는 g(x)가 나왔기 떄문에 모순이다.
  따라서 차수가 d인 고차합동방정식의 서로 다른 해의 개수는 최대 d다
  ⇒ 선형방정식의 해는 유일하다.