정수의 표현 :
- 우리는 일상생활에서 10진법을 이용하여 정수를 표현한다.
- 하지만 컴퓨터는 연산할 때 2진법을 사용하고, 문자나 숫자 등을 표현할 때 8진법 또는 16진법을 사용한다.
- 정수 n을 위의 그림처럼 표현한 것을 n의 밑 b 전개(base b expansion of n)라 한다.
2진수 곱셈 :
- 10진수가 10의 자리마다 들여쓰기를 하는 것처럼, 2진수는 2의 자리마다 들여쓰기한다.
소수 :
- 1보다 큰 모든 정수는 최소한 두 정수(1과 자기 자신)로 나누어 떨어진다.
- 정확히 두 개의 서로 다른 양의 정수가 약수인 양의 정수를 소수(prime)라고 한다.
- 대수학의 기본 정리 : 1보다 큰 모든 정수는 소수이거나, 둘 이상의 소수의 곱으로 표현할 수 있다.
소수 판별법 :
- 만약 n이 합성수라면, n의 소인수 중 하나는 √n보다 작거나 같다.
- 위의 정리를 이용해 제곱근 이하의 모든 소수로 나누어 보는 방법을 직접 나누어 보기(trial division)라 한다.
- 에라토스테네스의 체를 사용할 수도 있다.
최대공약수 :
- a,b가 0이 아닌 정수라 하자. d | a와 d | b인 정수 중 가장 큰 d를 a와 b의 최대공약수라고 한다. 이를 gcd(a,b)로 표현한다.
- 두 정수 a,b의 최대공약수가 1이면, 정수 a와 b는 서로소(relatively prime)라 한다.
최소공배수 :
- 양의 정수 a와 b의 최소공배수는 a와 b 모두로 나눌 수 있는 가장 작은 양의 정수이다.
- a와 b의 최소공배수는 lcm(a,b)로 표현한다.
유클리드 알고리즘 :
- a,b,q,r이 정수일 때, a=bq+r이라 하자. 그러면 gcd(a,b) = gcd(b,r)
gcd와 선형 결합 :
- 베주의 정리 : a와 b가 양의 저수이면, gcd(a,b) = sa + tb인 s와 t가 존재한다.
- 𝑎와 𝑏가 양의 정수이면, gcd(𝑎, 𝑏) = 𝑠𝑎 + 𝑡𝑏인 정수 𝑠와 𝑡는 𝑎와 𝑏의 베주 계수(Bezout coefficients)라 부른다. 또한, 식 gcd(𝑎, 𝑏) = 𝑠𝑎 + 𝑡𝑏를 베주의 동일성(Bezout's identity)이라 부른다.
소인수 분해의 유일성 :
- 양의 정수 a,b,c가 gcd(a,b) = 1이고 a | bc이면, a | c이다.
- 𝑝가 소수이고, 𝑎𝑖가 정수일 때 𝑝 | 𝑎1𝑎2 … 𝑎𝑛이면 𝑝 | 𝑎𝑖인 어떤 𝑖가 존재한다.
- (중요!!) 𝑚이 양의 정수이고 𝑎, 𝑏, 𝑐를 정수라 하자. 𝑎𝑐 ≡ 𝑏𝑐 (mod 𝑚)이고 gcd 𝑐, 𝑚 = 1이면 𝑎 ≡ 𝑏 mod 𝑚 .
반응형
'대학수업 > 이산수학' 카테고리의 다른 글
[12] 이산수학(관계) (0) | 2022.10.31 |
---|---|
[11] 이산수학(합동 풀기) (0) | 2022.10.18 |
[09] 이산수학(행렬을 이용한 연산) (0) | 2022.10.11 |
[08] 이산수학(수열과 행렬) (2) | 2022.10.04 |
[07] 이산수학(함수) (0) | 2022.09.27 |