[3-1] Basic Notions

3.1.1 Divisibility

정수의 성질 중에서 가장 중요한 것은 나눗셈이다

 

정리

a와 b가 정수이고 a는 0이 아닐 때 a가 b를 나누면 b = ak를 만족하는 정수 k가 존재한다.

a|b로 나타내고 b가 a의 배수라고 표현할 수 있다

 

명제

a, b, c가 정수일 때 

1. a != 0, a|0 and a|a

2. 모든 b에 대해서 1|b 

3. a|b이고 b|c라면 a|c

4. a|b이고 a|c라면 모든 정수s, t에 대해 a|(sb+tc)임 -> b = ak1, c = ak2, then sb+tc = a(sk1+tk2) -> a|(sb+tc)

 

 

3.1.2 Prime Numbers

1보다 큰 p가 오직 1과 자기 자신으로 나눌 수 있을 때 '소수'라고 한다

소수가 아닌 수는 합성수라고 한다

 

π(x) : x보다 작은 소수의 개수

π(x) ≈ x/ln x

//이것을 증명하는 것은 범위에 벗어나기 때문에 하지 않겠음

ex) 100자리의 소수를 얻고 싶다면?

π(10^100) - π(10^99) ≈ 10^100/ln 10^100 - 10^99/ln 10^99 ≈ 3.9 x 10^97

 

소수는 정수의 구성 요소로 모든 정수는 다른 지수승의 소수의 곱인 unique representation을 갖는다

 

정리

모든 양의 정수는 소수의 곱이고, 소인수분해는 요소를 재정렬하기 전까지 고유한 값을 가진다

증명

소수의 곱이 아닌 양의 정수가 있다고 가정하자. n이 그런 가장 작은 정수임

n은 1도 아니고 소수도 아니기 때문에 합성수임. n = ab with 1< a, b <n 

n은 소수의 곱이 아닌 가장 작은 양의 정수이므로 a와 b는 모두 소수의 곱(a,b가 n보다 작기 때문에 a,b는 소수의 곱임)인데 소수의 곱 x 소수의 곱 = 소수의 곱이기 때문에 n = ab도 소수의 곱이 되어 모순이 발생함 -> 모든 양의 정수는 소수의 곱이다

 

부명제

p가 소수이고 p가 정수 ab...z의 곱을 나눌 수 있다면 p는 a,b,...,z중 하나를 나눌 수 있음

ex) p=2라면 두 정수의 곱이 짝수 -> 두개의 요소 중 하나가 짝수임

 

3.1.3 Greatest Common Divisor - 최대공약수

gcd(a,b) or (a,b)로 나타냄

a와 b가 서로소면 gcd(a,b) = 1

최대 공약수를 찾는 가장 standard ways

1. a와 b를 소수로 나누고 a와 b의 소인수분해에서 소수의 지수를 보고 그 중에서 작은 지수를 취함

ex) 576 = 2^6*3^2, 135 = 3^3*5, gcd(576, 135) = 3^2 = 9 

2. a와 b가 큰 소수일 때 소인수 분해하기가 어려움. -> 유클리드 호제법 사용

 

https://terms.naver.com/entry.naver?docId=1132859&cid=40942&categoryId=32204 

유클리드의 호제법

 

정리

a와 b를 두 정수로 두자(a와 b 중 적어도 한개는 0이 아닐 때) d = gcd(a,b) 라고 한다면 ax+by = d를 만족하는 정수 x, y가 존재한다