합동

(1)

정수론, 제8장

합동

^{이상준 교수}⁽₂₀₁₅^{덕성여대 수학과)}_{년 2학기}

교재 : 친절한 수론 길라잡이 (4판)

조셉 실버만 지음, 김병찬,김지영,이종규,박부성 옮김

(2)

❖ 정의(합동):

❖ (1) 만일 m이 a - b 를 나눌 때, “a와 b가 법 m에 대해 합동이다” 라고 말한다. 

영어로는 “a is congruent to b modulo m” 이라고 말한다.

❖ (1)* a와 b가 m으로 나눈 나머지가 같으면 “a와 b가 법 m에 대해 합동이다” 라고 말한다.

❖ (2) a ≡ b (mod m) 이라 표기한다.

❖ (3) m을 합동의 법(modulus) 이라 부른다.

❖ 예시:

❖ 5|(7-2) 이므로 7 ≡ 2 (mod 5) 이다.

❖ 6|(47-35) 이므로 47 ≡ 35 (mod 6) 이다.

❖ 13 ≡ _____ (mod 4)

(3)

합동식에서의 합,차,곱

❖ 성질: a1 ≡ b1 (mod m)이고 a2 ≡ b2 (mod m)이면, 

a1 ± a2 ≡ b1 ± b2 (mod m) 이고 a1a2 ≡ b1b2 (mod m)이다.

❖ 증명: a1 = b1 + k1m, a2 = b2 + k2m 인 정수 k1, k2 가 존재한다.

❖ ① a1 ± a2 = (b1 + k1m) ± (b2 + k2m)  = b1 ± b2 + (k1 ± k2)m 

그러므로, a1 ± a2 ≡ b1 ± b2 (mod m).

❖ ②

(4)

합동식에서 나눗셈 (중요!)

❖ 주의: ac ≡ bc (mod m) ⇏ a ≡ b (mod m)

❖ 예: 15・2 ≡ 20・2 (mod 10) 이지만, 15 ≢ 20 (mod 10)

❖ 성질: ac ≡ bc (mod m), gcd(c,m) = 1 ⇒ a ≡ b (mod m)

❖ 증명: 숙제!

❖ 성질: ac ≡ bc (mod mc) ⇒ a ≡ b (mod m)

❖ 증명: ac = bc + kmc (k ∈ Z) ⇒ a = b+km ⇒ a ≡ b (mod m)

❖ 예: 15・2 ≡ 20・2 (mod 10) ⇒ 15 ≡ 20 (mod 5)

(5)

추가내용

❖ 주의: uv ≡ 0 (mod m)이지만, u ≢ 0 (mod m) 이고 v ≢ 0 (mod m) 일 수 있다.

❖ 예: 2・3 ≡ 0 (mod 6) 이지만, 2 ≢ 0 (mod 6), 3 ≢ 0 (mod 6)이다.

❖ 성질: p: 소수

❖ uv ≡ 0 (mod p)이면 u ≡ 0 (mod m) 이거나 v ≡ 0 (mod m) 이다.

(6)

합동식에서의 방정식

❖ 문제: x + 12 ≡ 5 (mod 8) 를 풀어라.

❖ 풀이: x ≡ 5 - 12 ≡ -7 ≡ 1 (mod 8) 

❖ 문제: 4x ≡ 3 (mod 19) 를 풀어라.

❖ 풀이: 5・4=20 ≡ 1 (mod 19)  5・4x ≡ 5・3 (mod 19)  x ≡ 15 (mod 19)

(7)

❖ 질문: 5・4 ≡ 1 (mod 19) 인 5를 어떻게 찾았을까?

❖ 답: 

4x ≡ 1 (mod 19)  4x+19y = 1 

1 = 4 - 3  3 = 19 - 4・4 

1 = 4 - (19 - 4・4)  = 5・4 - 19 

따라서 x=5로 잡으면 된다.

4 3 1

19 16 3 1

4

(8)

❖ 예제: 5x+4 ≡ 6 (mod 26) 를 풀어라.

(9)

선형 합동방정식 정리

❖ 질문: ax ≡ c (mod m) 의 모든 해를 찾아라.

❖ 해결책: ax ≡ c (mod m) ⇔ ax = c + my ⇔ ax - my = c: 선형방정식! 

(10)

❖ 선형방정식 정리(6장): a, c, m (m≥1) 은 정수이고, gcd(a,m)=g 라 하자.

❖ (a) 만일 g∤c 이면, ax - my = c 은 해를 가지지 않는다.

❖ (b) 만일 g | c 이면, ax - my = c 은 무한히 많은 해를 가진다. 

(x₀, y₀)를 특수해라 하면 모든 해 (x,y)는 

x=x0+k(-m/g), y=y0-k(a/g) (k는 정수). 

[ x=x0+k(m/g), y=y0+k(a/g) (k는 정수). ]

❖ 선형 합동방정식 정리: a, c, m (m≥1) 은 정수이고, gcd(a,m)=g 라 하자.

❖ (a) 만일 g∤c 이면, ax ≡ c (mod m) 은 해를 가지지 않는다.

❖ (b) 만일 g | c 이면, ax ≡ c (mod m) 은 g 개의 해를 가진다. 

x₀를 특수해라 하면 모든 해 x는 

x ≡ x₀+k(m/g) (mod m) (k=0,1,2,...,g-1).

(11)

❖ 문제: 18x ≡ 30 (mod 42) 를 풀어라.

❖ 풀이:

❖ gcd(18,42) = 6 이고 6|30 이므로 해가 있다.

❖ 18x ≡ 30 (mod 42)  3x ≡ 5 (mod 7)

❖ 5・3=15≡1(mod 7) 이므로 x ≡ 25 ≡ 4 (mod 7).

❖ mod 42에 대한 해로 바꾸면 

x ≡ 4, 11, 18, 25, 32, 39 (mod 42)

(12)

❖ 문제: 9x ≡ 21 (mod 30) 를 풀어라.

(13)

일차가 아닌 방정식

❖ 문제: x²+2x-1 ≡ 0 (mod 7) 의 모든 해를 찾아라.

❖ 해결책: 모든 후보를 시도해라.

0 x 2 1 3 4 5

x²+2x-1 -1 7=0 2 14=0 23=2 34=-1

두 개의 해: x ≡ 2 또는 3 (mod 7)

(14)

❖ 주목: 일반해를 얻기는 쉽지 않다!

❖ 질문: 방정식 f(x) ≡ 0 (mod m) 은 몇 개의 해를 가질까?

❖ 사실(고교수학): f(x) 를 계수가 실수이고 차수가 d인 다항식이라 하면,  f(x)=0는 많아야 d개의 해를 가진다.

❖ 주의: f(x) ≡ 0 (mod m) 의 경우는 다르다!

❖ 예: x²+x ≡ 0 (mod 6) 

x ≡ 0, 2, 3, 5 (mod 6) ← 4개의 서로 다른 해 (2차방정식이지만)

❖ 주목: 만일 법 m이 소수이면, 위의 사실(f(x)=0의 경우)과   비슷한 결과를 추측할 수 있다.

(15)

법 p에 대한 합동다항식의 근 정리

❖ 법 p에 대한 합동다항식의 근 정리: 

소수 p와 정수 계수의 다항식 f(x)=adx^d+ad-1x^d-1+…+a0 (d≥1, p

∤

ad)에 대하여,  f(x) ≡ 0 (mod p) 는 최대 d개의 서로 다른 해를 가진다. 

❖ 증명방법: (귀류법 & 최소성) 다음 페이지! (매우 중요!) 

(16)

❖ 증명: (귀류법을 쓰기위해) 정리의 결론을 만족하지 않는 다항식이 있다고 가정하자.

❖ 그런 다항식 중에서 차수가 가장 낮은 다항식 중 하나를 f(x) = a_dx^d + a_d-1x^d-1 + … + a₀이라 하자.

❖ 그러면 f(x) ≡ 0 (mod p) 는 (d+1)개의 서로 다른 해 r₁,r₂,…,r_d+1를 가진다.

❖ f(x) ≡ f(x) - f(r₁) ≡ a_d(x^d-r₁^d) + a_d-1(x^d-1-r₁^d-1) + … + (x-r₁)≡ (x-r₁) g(x)  ^{차수: d-1}  정리하면: f(x) ≡ (x-r1) g(x) (mod p)

❖ 2≤i≤d+1 에 대하여 f(ri) ≡ (ri-r1) g(ri) (mod p)  ≡0 ≢0

❖ p|(ri-r1) g(ri) 이고 p∤(ri-r1) 이브로 소수의 가약성에 의해 p|g(ri) 이다. 

즉, g(r_i) ≡ 0 (mod p) (2≤i≤d+1)

❖ g(x)는 차수가 d-1이면서 g(x) ≡ 0 (mod p)은 서로 다른 d개의 해를 갖는다.  

즉 정리의 결론을 만족하지 않는다!