수학적 배경

정수론

- R : 실수 집합

- Z : 정수 집학

- N : 자연수 집합

   

약수와 배수

- b = a * c

- a | b

   

공약수

- 두 개(또는 그 이상)의 자연수의 공통인 약수를 그들 수의 공약수 라고 한다.

최대 공약수

- 공약수 중에서 가장 큰 수

- gcd(a, b) : a와 b의 최대 공약수

- 양수인 최대 공약수를 구하기 때문에 gcd(a, b) = gcd(a, -b) = gcd(-a, b) = gcd(-a, -b)가 성립 즉, gcd(a, b) = gcd(|a|, |b|)

   

서로소

- 공약수가 1 뿐인 두 자연수를 서로소라고 한다.

- gcd(a, b) = 1 일 때, a와 b는 서로소이다.

   

공배수

- 두 개(또는 그 이상)의 자연수의 공통인 배수를 그들 수의 공배수라고 한다.

최소 공배수

- 공배수 중에서 가장 작은 수

   

유클리드 호제법

- 두 정수의 최대 공약수를 계산할 때 사용, gcd(a, b) = au + bv 인 정수 u, v를 구할 수 있다.

ex) 510과 62의 최대 공약수를 구하고 u,v를 구해라

510 = 62 * 8 +14

62 = 14 * 4 + 6

14 = 6 * 2 + 2

6 = 2 * 3 => 최대 공약수 : 2

2 = 14 + 6*(-2)

= 14 + (62 + 14*(-4))*(-2)

= 14 + 62(-2) + 14*8

= 14 * 9 + 62(-2)

= 510 * 9 + 62 * (-74)

 

합동식 (모듈라 연산)

- 법(modulus) 값에 다다르면 다시 초기 값을 갖는 연산

- 40%12=4, 40≡4(mod12) 40과 4는 법(modulus 12) 에 관하여 합동이다.

- a≡b(mod m) a와 b의 차가 m의 배수일 때 합동(a-b = mk), a와 b는 m으로 나뉬을 때 같은 나머지 값을 가진다.

- 임의의 정수 c에 대하여 a+b≡b+c(mod m)이면 ac≡bc mod m 성립

- ab≡ac mod m 이고, gcd(a, m)=1이면 b≡c mod m 이 성립

   

법 m에 관한 잉여계

- 정수 m에 대하여 Zm = {0,1,2,,,,m-1} : 법 m에 관한 완정 잉여계

- Zm* : Zm 의 원소 중에서 m과 서로소인 원소 전체의 집합을 말하며, 이를 법 m에 대한 기약 잉여계라 함

- Zm* 의 원소개수는 ∅(m) 으로 나태낸다.

   

Euler (오일러) 의 정리

ex) 7의 경우, 1,2,3,4,5,6개, 0은 서로소 관계에서 빠진다.

- m 이 소수일 때 ∅(m) = (p-1)

 

Fermat의 정리

   

- 일차 합동식 ax ≡ b(mod m)에서 정수 a와 m이 서로소이면, x는 단 하나의 해를 갖는다.

- a 와 m이 서로소 -> gcd(a, m)=1 -> au+mv=1 인 정수 u,v가 존재

- 일차 합동식 해 구하기2 : ax ≡ b(mod m)의 해는 a의 승산역원을 구해 양변에 곱해주면 된다.

   

승산역원

- 승산역원을 가지기위해서는 a와 m이 서로소이어야 한다.

- 승산역원은 유클리드 호제법을 사용한다.

- 만약에 음수가 나오면 m을 더해서 양수를 만든다.

ex) 27 ∈ Z65 의 승산역원을 구하라

- gcd(27, 65) = 1

- 유클리드 호제법

- 65*8 + 27*(-12) = 1

- 27의 승산 역원은 53이다.

- 27*53 ≡ 1 mod 65