고교 과정과 안겹치는 내용 위주로 이산수학을 정리해보도록 하겠습니다.
성균관대학교 2021 여름학기 GEDB007_42 수업을 바탕으로 작성되었습니다.
Divisor
정수 에 대해 이면 이라 한다.
•
•
•
Modulus Operator
a를 m으로 나눈 나머지가 r
•
Congrument (합동)
일때, 와 는 에 대해 합동이고, 이는
로 쓸 수 있다.
•
•
•
나누기는 안됨
Prime Number and Composite Number
•
이 합성수일때, 은 을 만족하는 Divisor 를 갖는다.
에 대해 귀류법으로 보일 수 있음
•
소인수 분해는 유일하다 (정수론의 기본정리)
•
소수의 개수는 무한하다.
어떤 소수보다 작거나 같은 모든 소수들의 곱에 +1 하면 그것도 소수라서 소수는 무한함
GCD
Greatest Common Divisor
•
•
•
LCM
Least Common Multiple
•
•
•
Euclidean Algorithm
유클리드 호제법
일때,
ex)
을 구해보자.
따라서
gcd(252,198)=18=4*252+(-5)*198
Special Result
(단, 는 자연수, 는 정수) 로 나타낼 수 있다.
Inverse Modulo
일때, 이 되는 를 찾는 계산 과정
이면 인 가 존재하고
에서 적당히 를 조져서 양의 정수 로 만들면 됨...