이산수학 - 정수론, 나눗셈, 베주의 항등식, 유클리드 호제법, 나머지 연산, 소수와 소인수 분해, 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.
