2. 합동식

(1)

- Contents -

1. 정제성

1.1. 약수와 소수 1.2. 소인수분해의 유일성

2. 합동식

2.1. 합동

2.2. 합동에 관한 기본성질 2.3. 페르마, 오일러, 윌슨의 정리

3. 다항합동식

3.1. 중국인의 나머지 정리 3.2. 법에 관한 합동식의 해법 3.3. 다항합동식의 해

4. 원시근

4.1. 법에 대한 정수의 위수 4.2. 지수

5. 이차 상반법칙

5.1. 이차잉여류와 르쟝드르 심볼 5.2. 쟈코비 심볼

Ⅰ. 기출문제

2001년시행기출(원시근)

G = ℤ₁₁- {0 }는 곱셈에 대하여 순환군(cyclic group)이 된다. 이 사실을 이용하여 단위원시 10-제곱근(법 11에 관한 원시근, primitive 10^th- root of unity)을 모두 구하여라.(5점)

2002년시행기출(중국인의 나머지정리) 다음 연립일차합동식의 해를 구하시오. (5점)

{

8x ≡ 4 ( mod 22) 3x ≡ 5 ( mod 25)

2003년시행기출(이차잉여, 페르마의 소정리)

다음 두 이차합동식의 해가 존재하는지 판별하시오. (총 5점) (1) x²≡ 97 ( mod 101) (2점)

(2) x²+ 2x ≡ 28 ( mod 89) (3점)

2004년시행기출(오일러의 φ함수)

1부터 1008까지의 자연수 중 1008과 서로소(relatively prime)인 자연수의 개수를 구하시오. (2점)

2004년시행기출(중국인의 나머지 정리)

f ( x) = ( 2 + 3ℤ, 3 + 5ℤ, 4 + 7ℤ) 를 만족시키는 정수 x 를 모두 구하시오. [3점]

Ⅱ.내용정리

※괄호안에 적당한 말을 연필로 쓰고 아래의 해답을 확인하세요.

1. 정제성(Divisibility)

1.1. 약수와 소수

NOTE (정수론의 기본원리)

다음의 사실을 바탕으로 정수론의 명제들은 입증된다.

(1)자연수의 정렬성의 원리

φ /= E ⊂ ℕ ⇒ E는 최소원소를 가진다.

(2)수학적 귀납법의 원리

A( n) : n에 관한 명제( ∀n ∈ℕ), A( 1) : 참, A( n) : 참이면 A( n + 1) : 참이다.

⇒ ∀n ∈ℕ, A( n) : 참 (3)아르키메데스의 원리

a ∈ ℝ ⇒ ∃n ∈ℕ s.t. a < n (즉 ℕ : 위로 비유계이다.)

정 의 1

(1) a, b ∈ ℤ에 대하여 ∃c ∈ ℤ s.t. (¹⁾ )

⇔ a | b ( a는 b를 나눈다.(divides)), 그렇지 않으면 a∤b

⇔ b : a의 배수(multipler)

⇔ a : b의 약수(divisor) 혹은 인수(factor) (2) p( ∈ ℤ) : 소수(prime)

⇔ (ⅰ)(²⁾ )

(ⅱ)(³⁾ ) (즉 p의 양의 약수는 1과 자기자신뿐이다.)

(3) n > 1이 ± 1 , ± n 이외의 약수를 가질 때 합성수(composite number) 라 한다.

정 리 1 (정수의 호제법(Division algorithm)혹은 나눗셈정리) a ∈ ℤ⁺, b ∈ ℤ일 때

∃₁q∈ℤ, ∃₁r∈ {0, 1, 2, …, a - 1 } s.t. b =qa + r

이 때 q : b를 a로 나눈 몫(quotient), r : 나머지(remainder)

정 의 2

(1) a, b( /= 0) ∈ ℤ, d ∈ ℤ s.t.

(ⅰ)(⁴⁾ ) (ⅱ)(⁵⁾ )

( ⇔ d : a와 b의 공약수(common divisor)) (ⅲ)(⁶⁾ )(최대(greatest))

⇔ d = gcd ( a , b) 혹은 d = ( a , b)

⇔ d : a와 b의 최대공약수(Greatest common divisor)

1) b = ac 2) 1 < p

3) 0 < n, n | p ⇒ n = 1 혹은 n = p 4) d ≥ 1

5) d | a, d | b

6) k | a, k | b ⇒ k | d

김 현 웅 전공수학

http://cafe.daum.net/hwmath

2006학년도 중등교원임용시험대비 문제풀이반

핵심내용정리(정수론) 구평회 임용고시학원 예비교사닷컴

구평회임용고시학원․서울(노량진) 02-812-5700․대구(동성로) 053-426-0078․부산(서면) 051-808-0565

(2)

(2) a, b ∈ ℤ에 대하여 ( a, b) =(⁷⁾ )

⇔ a, b:서로소(Relative prime)

정 리 2 (최대공약수의 well-definedness)

(1) a, b∈ℤ, a /= 0, b /= 0일 때 a와 b의 최대공약수는 유일하게 존재한 다.

(2) aℤ + bℤ =(⁸⁾ )(단 d = ( a, b)) 특히 ( a, b) = 1이면 aℤ+bℤ = ℤ이다.

정 리 3

(1) ( a, b) =d 이면

(

^a^d ^, ^d^b

)

⁼⁽⁹⁾⁾

(2) a | b c, (a, b) = 1이면 (¹⁰⁾ ) (3) a | bc이면 a

( a,b)

|

^c

(4) ( ma, mb) = |m |( a, b)

정 리 4 (유클리드 호제법(₌최대공약수의 계산법)) a ∈ℤ⁺, b ∈ℤ에 대하여

b = q₁a + r₁, 0 < r₁< a a = q₂r₁+ r₂, 0 < r2< r₁ r₁ = q₃r₂+ r₃, 0 < r3< r₂ ⋯

r_{n - 2}= q_nr_{n - 1}+ r_n, 0 < r_n< r_{n - 1} r_{n - 1}= q_{n + 1}r_n+ r_{n + 1}, rn + 1 = 0 일 때 rn=(¹¹⁾ )

NOTE

k-단계의 제수 → k + 1-단계의 (¹²⁾ ), k-단계의 나머지 → k + 1-단계의 (¹³⁾ )

정 리 5 (Diophantine방정식 ax + by = c의 일반해) a, b, c∈ℤ , a /= 0, b /= 0, d = ( a, b)일 때

(1) ax + by = c의 정수해가 존재 ⇔ d | c

(2) x0, y0가 ax+by = c의 하나의 해(즉 ax0+ by₀ = c)일 때 ax + by = c의 일반해는 x = (¹⁴⁾ ),

y =(¹⁵⁾ ) ( k ∈ ℤ) (즉 ax + by = c ⇔ x = x₀+ b

d k, y = y₀- a

d k ( k ∈ ℤ))

NOTE

Diophantine 방정식이란 해가 정수로서 결정되는 정수계수 방정식이다.

7) 1 8) dℤ 9) 1 10) a | c 11) gcd ( a, b) 12) 피제수 13) 제수 14) x₀+ b

d k 15) y₀- a

d k

1.2. 소인수분해의 유일성

정 리 6

(1)소인수분해의 유일성

1 < n ( n ∈ ℤ)일 때 n은 소수의 곱으로 유일하게 표시된다.

(즉 n = p1p₂… p_r, n = q1q₂… q_s ( pi,q_j : 소수 ∀i,j)

⇒ r = s이고 p_i와 q_j는 일대일대응관계에 있다.) (2)정수에는 무한히 많은 소수가 있다.

(3)유클리드의 정리

p : 소수, p | ab ⇒ p | a 혹은 p | b

일반화하면 p : 소수, p | a₁a₂…a_r ⇒ ∃i = 1, 2, …, r s.t. p | a_i

NOTE

n < - 1인 경우에는 - n이 소수의 곱으로 유일하게 표시된다.

(즉 적당한 소수 p₁, …, p_r에 대하여 n =- p₁p₂…p_r이고 이 표현은 유 일하다.)

정 리 7

1 < n, n은 소수가 아니다. ⇒ ∃p : 소수 s.t. (¹⁶⁾ )

2. 합동식(congruent equation)

2.1. 합동

정 의 3

(1) n ∈ ℤ⁺일 때 a, b∈ℤ, a ≡ b ( mod n) ⇔ n | a - b 그렇지 않으면 a /≡ b ( mod n)

(2) R : 법 n에 관한 완전잉여계(complete residue system modulo n)

⇔ R = {a₁,a₂,…,a_n} ⊂ ℤ s.t.

∀m∈ℤ, ∃1a_i∈R s.t. a_i≡ m ( mod n)

NOTE

≡ ( mod n) 은 ℤ위의 하나의 동치관계(equivalance equation)이다.

정 리 9

a, b ∈ℤ 에 대하여 (1) a ≡ b ( mod n)

⇔ ( a를 n으로 나눈 나머지 = b를 n으로 나눈 나머지) (2)디오판틴(Diophantine) 방정식

f( x, y) = 0

이 (정수)해를 가지면 임의의 n ∈ ℤ⁺에 관하여 합동방정식 f( x, y) ≡ 0 ( mod n)

도 해를 가진다.

(즉 f( x, y) = 0 ⇒ ( f( x, y) ≡ 0 ( mod n)( ∀n ∈ ℤ⁺))

NOTE

따라서 적당한 n에 관하여 f( x,y) ≡ 0 ( mod n)이 해를 갖지 않으면 f( x, y) = 0는 정수해를 갖지 않음을 알 수 있다.

16) p | n, p ≤ n

(3)

2.2. 합동에 관한 기본성질

정 리 8

(1) a₁≡ b₁( mod n), a₂≡ b₂( mod n), …, a_m≡ b_m( mod n)이면 (ⅰ) a₁+ a₂+ … + a_m≡ b₁+ b₂+ … + b_m( mod n)

(ⅱ) a₁a₂…a_m≡ b₁b₂…b_m( mod n)

(2) a ≡ b ( mod n), f(x) : 정수계수다항식(즉 f∈ℤ[x])이면 (ⅰ) ∀k∈ℤ⁺, a^k≡ b^k( mod n)

(ⅱ) f(a) ≡ f(b) ( mod n)

정 의 4

a∈ℤ에 대하여 a^*∈ℤ s.t. a a^*≡1 ( mod n)

⇔ a^* : 법 n에 대한 a의 역수(arithmetic inverse)

정 리 9

( a, n) =(¹⁷⁾ ) ⇔ ∃a^*∈ℤ s.t. a^* : 법 n에 대한 a의 역수

NOTE

ℤ_p( p : 소수)에서 0아닌 모든 원소는 역수를 갖는다.

NOTE (유클리드 호제법을 이용한 법n에 관한 역수의 계산) (1) ( a, n) = 1일 때 유클리드 호제법을 역순으로 적용하여

1 = ax + ny( x, y ∈ℤ) 를 만족하는 x, y ∈ℤ를 구한다.

(2) 1 ≡ ax + ny ≡ ax( mod n)가 되어

x = a^*( a의 법 n에 관한 역수) 예를 들어 5의 법 43에 대한 역수를 구하자.

유클리드 호제법을 적용하면 43 = 5⋅8 + 3

5 = 3⋅1 + 2 3 = 2⋅1 + 1 2 = 1⋅2 + 0

다시 역순으로 적용하면 1 = 43⋅2 + 5 ( - 17), 1 ≡ 5 ( - 17) ( mod 43) 그러므로 5^*=(¹⁸⁾ )이다.

정 리 10

(1) ( a, n) = 1일 때

(ⅰ) ax ≡ ay ( mod n) ⇔ x ≡ y ( mod n):약분법칙(cancelation law) (ⅱ) a^*: 법 n에 관한 a의 역수일 때

ax ≡ b ( mod n) ⇔ x ≡ (¹⁹⁾ ) ( mod n) (2) ( a, n) = d일 때

(ⅰ) ax ≡ ay ( mod n) ⇔ x ≡ y ( mod n/d)

(ⅱ) d | b일 때 법 nd 에 대한 a1의 역수 a^*₁에 대하여

ax ≡ b ( mod n) ⇔ x ≡ (²⁰⁾ ) ( mod n/d) (단 a1= a/d) 17) 1

18) - 17 19) a^*b 20) a^*₁b/d

정 의 5

n ≥ 1에 대하여

φ( n) =1부터 n까지의 n과 서로소인 정수의 개수 ( φ를 오일러의 φ함수라 한다.)

NOTE

n ≥ 1에 대하여

φ( n) = ℤ_n의 (²¹⁾ )의 개수

정 리 11(오일러의 φ함수값의 계산) (1) ( m, n) = 1이면 φ( m n) = φ( m ) φ( n) (2) p : 소수, k ≥ 1이면

φ( p) =(²²⁾ )

φ( p^k) =(²³⁾ )

(3) n = p^r₁¹p^r₂²… p^r_k^k( p_i : 서로 다른 소수, r_j≥ 1)일 때 φ( n) =(²⁴⁾ )

=(²⁵⁾ )

정 리 12 (가우스(Gauss)의 정리) 1 ≤ n ≤ ℤ⁺일 때 ∑

d | nφ(d) = n

2.3. 페르마, 오일러, 윌슨의 정리

정 리 14 p : 소수일 때

(1) ( p, a) = 1 ⇒(²⁶⁾ ) ≡ 1 ( mod p) (페르마의 소정리(Fermat's little theorem))

(2) ( a, n) = 1 ⇒ (²⁷⁾ ) ≡ 1 ( mod n)(오일러(Euler)의 정리) (3) (p -1)! ≡ -1 ( mod p)(윌슨(Wilson)의 정리)

NOTE

(1)페르마의 소정리의 가정에서 p는 소수이므로 ( p, a) = 1 ⇔ p ∤a (2)페르마의 소정리에 의해

a^p ≡

{

a a /≡ 0 ( mod p) 0 ≡ a a ≡ 0 ( mod p) (즉 ∀a ∈ℤ, (²⁸⁾ ) ≡ a ( mod p))

(3)오일러의 정리에 의해 ( a, n) = 1일 때 a의 법 n에 대한 역수 는 a^*= aφ ( n ) - 1

(4)오일러의 정리를 이용하면 페르마의 소정리는 자명하게 증명되므로 오 일러의 정리는 페르마의 소정리의 일반화이다.

21) 가역원(단원) 22) p - 1

23) p^k- p^{k - 1} = p^{k - 1}(p - 1) 24) φ( p^r1¹) φ( p^r₂²) … φ( p^r_k^k)

25) ( p1^r¹- p₁^r¹^{- 1}) ( p₂^r²- p₂^r²^{- 1}) … ( p_k^r^k- p_k^r^k^{- 1}) 26) a^{p - 1}

27) a^{φ ( n )} 28) a^p

(4)

3. 다항합동식

3.1. 중국인의 나머지 정리

도 입

(1) x ≡ 1 ( mod 2), x ≡ 2( mod 3)

⇔ ( x ≡ 1( mod 6) or x ≡ 3( mod 6) or x ≡ 5( mod 6)) and ( x ≡ 2( mod 6) or x ≡ 5( mod 6))

⇔ x ≡ 5( mod 6)

이와 같은 사실을 일반화하면 아래 정리의 (1)을 얻는다.

(2) f( x) ≡ 0( mod 2⋅3)

⇔ 2⋅3 | f( x)

⇔ 2 | f( x) and 3 | f( x) ( ∵ ( 2, 3) = 1)

⇔ f( x) ≡ 0( mod 2) and f( x) ≡ 0( mod 3)

이와 같은 사실을 일반화하면 아래 정리의 (2)를 얻는다

정 리 15

(1)중국인의 나머지 정리(Chinese remainder theorem) m₁, m₂, …, m_t( ∈ℤ⁺) : 서로소, b1, b₂, …, b_t∈ℤ일 때

∃x∈ℤ s.t.

ꀊ

ꀖ ꀈ

︳︳

x ≡ b₁( mod m₁) x ≡ b₂( mod m₂) …

x ≡ b_t( mod m_t)

이고 x는 mod (²⁹⁾ )에 대하여 유일하다.

(즉 x, y가 위의 연립합동식을 만족하면 x ≡ y ( mod m₁m₂…m_t)) (2)양의 정수 n이 n = p^a1¹…p^a_t^t ( p_i: 서로 다른 소수, a_j ≥ 1)와 같이 소 인수분해될 때

f( x) ≡ 0 ( mod n) ⇔ f(x) ≡ 0 ( mod p^a₁¹), …, f(x) ≡ 0 ( mod p^a_t^t)

3.2. 법 p

^a

에 관한 합동식의 해법

정 리 16

(1) x :f(x) ≡ 0 ( modp^{a + 1})의 해(즉 p^{a + 1}|f( x))이면 x :f( x) ≡ 0 ( mod p^a)의 해(즉 p^a |f( x))

(2) b + kp^a : f(x) ≡ 0 ( mod p^{a + 1})의 해( k∈ℤ)

⇔ f '( b)k ≡ (³⁰⁾ ) ( mod p) (단 f '( x )는 f( x)의 도함수(derivative))

NOTE

위의 정리에 의해 f(x) ≡ 0 ( modp^{a + 1})의 해를 구할 때

f( x) ≡ 0 ( mod p^a)의 해 중에서 f( x) ≡ 0 ( mod p^{a + 1})의 해를 골라낸다.

3.3. 다항합동식의 해

정 의 6

(1)정수계수다항식

f( x) = a₀+ a₁x + a₂x²+ …, g( x) = b₀+ b₁x + b₂x²+ …에 대하여

∀i, a_i≡ b_i( mod n) ⇔ f( x) ≡_xg( x) ( mod n)

(2)정수계수 다항식 f(x) = a₀+ a₁x + … + a_mx^m에 대하여

29) ( m1m₂…m_t) 30) - f( b)

p^a

∃i s.t. a_i≡ 0 ( mod n)일 때 deg/ _nf(x) = max {i | a_i≡ 0 }/

정 리 17

소수 p에 대하여 (³¹⁾ ) ≡_xx ( mod p)

NOTE

위의 정리는 임의의 다항합동식 f(x) ≡ 0 ( mod p)을 p-1이하의 차수로 바꿀수 있음을 의미하고 이는 페르마의 소정리에 의해 증명된다.

4. 원시근(primitive roots)

4.1. 법 n에 대한 정수 a의 위수

도 입

(1)군 G와 a ∈G에 대하여

ord( a)≡(³²⁾ ) = | < a > | = | {a^k| k ∈ ℤ }|

(2)(ⅰ) < ℤn, +> : 덧셈군, a ∈ℤ_n일 때

ord( a) = min {k∈ℤ⁺| ka = 0 }

(ⅱ) U( ℤn) = {k∈ℤ_n| ( k, n) = 1 }( ℤ_n의 단원군(unit group)), a ∈U( ℤ_n)에 대하여

ord( a) = min {k ∈ ℤ⁺| a^k= 1 } = | < a > | = | {a^k| k ∈ ℤ }|

(ⅲ) U( ℤ5) = {1, 2, 3, 4 }: ⋅에 대한 군, ord( 1) = 1

ord( 2 ) = 4 = | <2 > | = |U( ℤ₅) | = φ( 5 )( ⇒ U( ℤ₅) =< 2 >) ord( 3) = 4 = | <3 > | = |U( ℤ₅) | = φ( 5 )( ⇒ U( ℤ₅) =< 3 >) ord( 4) = 2

따라서 2, 3은 단원군 U( ℤ₅)의 생성원이 된다.

(ⅳ) U( ℤ6) = {1, 5 } : ⋅에 대한 군, ord( 1) = 1

ord( 5) = 2 = | <5 > | = |U( ℤ₆) | = φ( 6 )( ⇒ U( ℤ₆) =< 5 >) 따라서 5는 단원군 U( ℤ6)의 생성원이 된다.

정 의 7

n > 1, ( a, n) = 1일 때

(1) ordna : = (³³⁾ )

: 법 n에 대한 a의 위수(the order of a modulus n) (2) a : 법 n의 원시근(a primitive root of n)

⇔ ord_na = (³⁴⁾ )( = |U( ℤn) |)

⇔ < a > = (³⁵⁾ ) (즉 a는 ℤn의 단원군의 생성원)

NOTE

( a, n) /= 1이면 ∃k∈ℤ/ ⁺ s.t. a^k≡ 1 ( mod n)

31) x^p

32) min {k ∈ℤ⁺| a^k= e }

33) min {k∈ℤ⁺| a^k≡ 1 ( mod n) } 34) φ( n )

35) U( ℤn)

(5)

4.2. 지수(index)

도 입

개념상으로 다음과 같은 비례식이 성립한다고 볼 수 있다.

실함수식 : 합동식 ≈ log : (³⁶⁾ )

≈ log 의 밑조건 : (³⁷⁾ ) (1)실함수에서

log _r : ( 0, ∞) → ℝ, logrx = y ( ⇔ r^y = x) 0 < r, r /= 1( log 함수의 밑조건)

⇔ {r^x| x∈ℝ } = ( 0, ∞) : log_r의 정의역 (2)합동식에서

ind_r : U( ℤ_n) → ℤ, ind_rx = y ( ⇔ r^y≡ x ( mod n) r : 법 n의 원시근

⇔ {r^x| x∈ℤ } =< r >= (³⁸⁾ ) : ind_r의 정의역

정 의 8

r : n의 하나의 원시근이고 ( a, n) = 1일 때 ind_ra : =(³⁹⁾ )

: r에 대한 a의 지수(the index of a relative to r)

정 리 18

r이 n의 원시근일 때

(1) indr( ab) ≡ (⁴⁰⁾ )( mod (⁴¹⁾ )) (2) ind_ra^k≡ (⁴²⁾ )(⁴³⁾ )( ∀k > 0) (3) ind_r1 ≡ 0 ( mod φ( n) ), ind_rr ≡ 1 ( mod φ( n ))

5. 이차 상반법칙

5.1. 이차잉여류와 르쟝드르 심볼

정 의 9

p를 홀수인 소수, p /| a인 정수라 할 때

(1) a( ∈ℤ) : 법 p에 관한 이차 잉여류(quadratic residue)

⇔(⁴⁴⁾ )

그렇지 않으면 a : 법 p에 관한 이차 비잉여류(quadratic nonresidue) (2)

(

^ap

)

⁼⁽⁴⁵⁾ ), a가 법 p에 관한 이차 잉여류일 때

=(⁴⁶⁾ ), a가 법 p에 관한 이차 비잉여류일 때 : 르장드르 심볼(Legendre symbol)

36) ind

37) ind 의 원시근의 조건 38) U( ℤn)

39) min {k∈ℤ⁺| a≡r^k( mod n) } 40) ind_ra + ind_rb

41) φ( n ) 42) k indra 43) mod φ( n )

44) ∃x ∈ℤ s.t. x²≡ a ( mod p) 45) + 1

5.2. 쟈코비 심볼

정 의 10

n은 1보다 큰 홀수, n = p₁p₂…p_t(각 p_i는 서로 다른 소수), a ∈ℤ일 때

(

^aⁿ

)

^mⁿ

)

^{= ( - 1)} ^{m - 1}² ^⋅^{n - 1}²

47) 1 48) 1

49) a ( p - 1 )/2

50)

(

^a^p

)(

^b^p

)

51) ( - 1)

p - 1 2

52) (- 1)

p - 1 2 ⋅ q - 1

2