4장

정수론의 기본 개념과 유한체

가분성과 호제법 (Divisibility & Division Algorithm)

==========================================================

**가분성

• a, b, m 이 정수이고, b 가 0 이 아닐때, 임의의 수 m 에 대해 a = mb가 성립한다면, b가 a를 나눈다 라고 한다.

• 즉 나눗셈 여산 후, 나머지가 0 이면 b가 a를 나눈다 라고함

• b | a == b가 a를 나눈다

• b | a 이면 b 는 a 의 약수

==========================================================

**나누어짐의 특성

• 만약 a | 1 이면 a = 1

• a | b && b | a 라면, a = ±b

• a | b && b | c 라면, a | c

• 만약 b | g 이고 b | h 이면, 임의의 정수 m 과 n 에 대해 b | (mg + nh) 이다.

  • 만약 b | g 이면 g = b x g1 이 되는 정수 g1 이 존재

  • 만약 b | h 이면 h = b x h1 이 되는 정수 h1 이 존재

  • 즉, mg + nh = mbg1 + nbh1 = b x (mg1 + nh1) 이다

==========================================================

**호제법( Division Algorithm )

• 임의의 양의 정수 n 과 음의 정수가 아닌 정수 a 에 대해 n이 a 를 나눈다면 정수인 몫 q와 나머지 r이 존재하며, 다음의 관계식이 성립된다

• 

**유클리드 호제법 ( Euclidean Algorithm )

• 두 양의 정수에 대한 최대 공약수를 결정하기 위한 수행 절차

• 서로소 : 공약수가 1 밖에 없는 두 정수

• 최대 공약수 ( Greatest Common Divisor )

    gcd( a, b ) : a와 b의 최대 공약수를 의미
    다음을 만족한다면 c는 a 와 b 의 gcd
    	c 는 a 와 b 의 약수
    	a 와 b 에 대한 모든 공약수는 c 의 약수
    양수인 최대 공약수를 구하는 것이기에, 다음은 모두 같은것을 의미
    	gcd(a,b) = gcd(a,-b) = gcd(-a,b) = gcd(-a,-b)
  

• 다음은 최대공약수를 유클리드 호제법을 이용해 찾는 방법이다.

  1. 어떠한 정수 a, b 와 d = gcd ( a, b ) 가 있다 가정
  2. gcd ( |a| , |b| ) 이기에 a >= b>= 0
  3. a 를 b로 나눈 후 호제법 적용 (4.1)
  4. 만약 r = 0 이라면 b | a, d 이므로 답은 b.
  5. r != 0 이라면, 가분성의 기본 성질에 의해 d | r 이라 할 수 있음
     1. b > r1이기 때문에 b를 r1 으로 나눌 수 있고 호제법을 적용하여 다음을 얻음
     2. 
     3. r2 = 0 이라면 d = r1 이 되고, 만약 r != 0 이라면 d = gcd( r1, r2 )
     4. 나누기 과정은 나머지가 0 이 나올 때 까지 계속된다
     5. 

• 위 방법을 쓰면 각 단계마다 d = gcd ( ri, ri+1) 을 얻을 수 있다

• 결과적으로 d = gcd ( rn, 0 ) = rn 을 얻게 된다

• 다음은 최대 공약수 구하기의 예제이다

• 

• q = a / b

• r = a mod b

• 유클리드 호제법에서 다음이 성립

  • gcd (a, b) = gcd( b, a mod b)
  • 
  • 즉, 다음과 같다고 할 수 있다
  • 

**확장 유클리드 호제법

• 정수 a 와 b 에 대한 최대 공약수 d뿐만 아니라 다음 수식을 만족하는 x 와 y도 구할 수 있다
• 
• 이때, x 와 y 가 상반된 부호를 가지게 되는 것은 명백하다
• 확장 유클리드 호제법은 a 와 b 가 주어졌을 때, (x, y, d) 를 결정하는 방법
• 각 i 단계마다 다음 수열이 도출된다
• 
• i - 1 과 i - 2 행에서 다음 값을 찾을 수 있다
• 
• 이미 r i = ax + byi 라고 추측했기에 다음이 도출된다
• 
• 기존의 유클리드 호제법은 나머지가 0 이 되면 d = gcd ( a, b) = rn 을 구하고 끝
• 확장 유클리드는 d = rn = axn + byn 까지 확장
  • 따라서 x = xn, y = yn임
• 예제)
• 

==========================================================

**Modulus

• 임의의 정수 a 와 양의 정수 n 에 대하여 a mod n 을 a 를 n 으로 나눈 **나머지

  • 이 때, n을 modulus 라고 함

• 

• 즉 다음과 같은 경우, modulus n 에 대해 합동이라고 한다

• 

• 합동에 관한 기본 특성

  • 만약 n | (a - b) 이면 a= b mod n
  • a = b mod n 은 b = a mod n 의 의미를 포함
  • a = b mod n 이고 b = c mod n 이면 a = c mod n

• 모듈러 연산의 특성

  • [(a mod n) + (b mod n)] mod n = (a + b) mod n
  • 빼기와 곱셈도 적용
  • modulo n 에서 set of residues는 다음을 만족할 대 표기할 수 있다
    [r] = {a: a 는 정수 a ≡ r (mod n)}
    

• modulo n 에서 k 와 합동인 음이 아닌 가장 작은 정수를 찾는 작업을 k를 modulo n 으로 환산한다 라고 한다

• modulo 연산은 다음 법칙들을 만족한다

• 교환 법칙

  • (w + x) mod n =(x + w) mod n

• 결합 법칙

  • ((w + x ) + y) mod n = (w + (x + y)) mod n # 곱셈도 똑같이 적용

• 분배 법칙

  • (w x (x + y)) mod n = ((w x x) + (w x y)) mod n

• 항등

  • (0 + w) mod n = w mod n
  • (1 x w) mod n = w mod n

• 일반적인 연산과 구별되는 특성

  • 만약 (a + b) ≡ (a + c) mod n 이라면 b ≡ c mod n

  • 

  • 위 식은 덧셈에 대한 역원이 존재함을 의미

  • 또한 다음 과 같은 특성도 존재한다

    • 만약 ( a x b ) ≡ (a x c ) (mod n) 이라면 b ≡ c mod n 이다
    • 단 a 는 n 과 서로소 이다