이산수학 - 정수론, 나눗셈, 베주의 항등식, 유클리드 호제법, 나머지 연산, 소수와 소인수 분해, RSA 암호
1. 나눗셈 a는 정수이고 b는 양의 정수라 할 때, 다음을 만족하는 유일한 정수 q, r이 존재한다. \[ a = bq + r \quad \text{단,} \quad 0 \leq r 이 정리는 어떤 정수 \( a \)를 양의 정수 \( b \)로 나누면, 몫 \( q \)와 나머지 \( r \)가 존재하며, 나머지 \( r \)는 0 이상 \( b \) 미만의 범위에 속한다는 것을 의미한다. 예를 들어, \( a = 17 \)이고 \( b = 5 \)인 경우를 생각해보자. \( a \)를 \( b \)로 나누면 다음과 같이 나타낼 수 있다.\[17 = 5 \cdot 3 + 2\]여기서 몫 \( q = 3 \)이고 나머지 \( r = 2 \)이다. 또한, 나머지 \( r \)는 0 이상 5 미만의 ..
2024. 5. 15.
이산수학 - 그래프, 트레일, 경로, 이분 그래프, 완전 이분 그래프, 정규 그래프, 오일러 투어, 해밀턴 경로
1. 기본사항 다음 그림처럼 점과 두 점을 서로 연결하는 선으로 이루어진 도형을 그래프라 한다. 2. 주요 용어 그래프 \( G \)는 꼭지점(vertex)들과 변(edge)들로 구성된다. 이를 수식으로 나타내면 \( G = (V, E) \)이다. 여기서 \( V = \{ v | v \text{는 꼭지점} \} \)이고, \( E = \{ e | e \text{는 변} \} \)이다.변은 두 꼭지점을 연결한다. 즉, 변에 의해 발생(incident)된다고 한다.연결된 두 꼭지점은 서로 인접(adjacent)한다고 한다.병렬 변(parallel edge)은 두 꼭지점을 연결하는 변이 복수개 있을 때를 의미한다.루프(loop)는 동일한 꼭지점을 연결하는 변을 뜻한다.고립된 꼭지점(isolated ..
2024. 5. 15.
이산수학 - 함수, 함수의 상등, 전사함수, 단사함수, 합성함수, 계승함수, 바닥함수, 천장함수, 나머지 함수
1. 기본사항 집합 \(X\)와 \(Y\)가 주어졌을 때, \(X\)에서 \(Y\)로의 함수 \(f\)는 다음 조건을 만족하는 관계이다.모든 \(x \in X\)에 대해, 오직 하나의 \(y \in Y\)가 존재하여 \((x, y) \in f\)를 만족한다. 이를 수식으로 표현하면 다음과 같다.\[ \forall x \in X, \exists ! y \in Y \quad \text{such that} \quad (x, y) \in f \]즉, \(X\)의 임의의 원소 \(x\)에 대해, \((x, y) \in f\)를 만족하는 \(y\)가 \(Y\)에 오직 하나만 존재한다.이를 함수 \(f\)로 표현하면 다음과 같이 쓸 수 있다.\[ f : X \to Y \]그리고, \(f(x) = y\)라는 관계를 만..
2024. 5. 15.
