[이산수학] 유클리드 호제법(Euclidean algorithm)
유클리드 호제법(Euclidean algorithm) 1. 유클리드 호제법 유클리드 호제법은 수학자 유클리드가 제시한 두 정수의 최대공약수를 찾는 방법입니다. 최대공약수를 구하기 위해 선제적으로 알아야 할 성질은 다음과 같습니다. a, b, x, r이 정수일 때 a= bx + r이면, gcd(a, b) = gcd(b, r) (증명) gcd(a, b) = G라고 하면, 서로소인 a', b'에 대해 a = a'G, b = b'G로 표현할 수 있습니다. a = bx + r을 만족하면, a'G = b'Gx + r이 성립하고, G(a' - b'x) = r이 성립합니다. 즉, gcd(b, r) = gcd(b'G, G(a' - b'x)) = G * gcd(b', a' - b'x)가 됩니다, gcd(b', a' - b..
[이산수학] 베주의 항등식(Bezout's identity)
베주의 항등식(Bezout's identity) 1. 베주의 항등식 베주의 항등식은 0이 아닌 두 a, b의 최대공약수는 임의의 정수 x, y에 의해 아래와 같은 항등식을 의미합니다. $$ax + by = gcd(a, b)$$ 2. 예시 ① a = 12, b = 8 $$gcd(a, b) = 4 = a * 1 + b * (-1)$$ ② a = 3, b = 7 $$gcd(a, b) = 1 = a * (-2) + b * 1$$ 연관 게시글 [이산수학] 정수론 [이산수학] 정수론 정수론 1. 정수론 정수론은 암호학, 알고리즘 이론 등에서 사용되는 정수에 관한 수학적인 구조와 성질을 연구합니다. 2. 나눗셈(Division) 2.1. 기본 개념 나눗셈은 앞으로 다룰 소수, 최대공약수, brightchords.ti..
[이산수학] 정수론
정수론 1. 정수론 정수론은 암호학, 알고리즘 이론 등에서 사용되는 정수에 관한 수학적인 구조와 성질을 연구합니다. 2. 나눗셈(Division) 2.1. 기본 개념 나눗셈은 앞으로 다룰 소수, 최대공약수, 모듈러 등에서 가장 기본이 되는 개념입니다. 나눗셈의 정의는 다음과 같습니다. a는 정수, b는 양의 정수일 때, a = bq + r 를 만족하는 정수 q, r이 존재한다. (단, 0 ≤ r ＜ b) a: 나눠지는 수 b: 나누는 수 q: 몫 r: 나머지 이때 r = 0인 경우 a는 b의 "배수(multiple)"라고 하며, b는 a의 "약수(divisor)"라고 합니다. 그리고 이때 a와 b의 관계를 b | a로 표현합니다. 또한, 나눗셈은 아래와 같은 관계를 만족합니다. a, b, c가 임의의 정..
