최대공약수의 성질

 

 

여러 개의 정수에 대하여 정수들의 공통된 약수를 공약수라 하고, 공약수 중 가장 큰 자연수를 '최대공약수'라고 한다.

그리고 두 수 \( a \), \( b \)의 최대공약수를 기호로 \( gcd(a, b) \) 또는 \( g(a, b) \)로 나타낸다.

 

다음과 같은 성질이 있다.

① \( a= bq + r (0 \leq r < b) \)일 때 \( g(a, b) = g(b, r) \) 이다.

② \( g(a, b) = g(a, a-b) \)

③ \( g(a, c) = 1 \)이면 \( g(a, bc) = g(a, b) \)이다.

 

예제1) 자연수 \( n \)에 대하여 \( g(2n+1, 2n-1) \)을 구해보자.

 

풀이)

\( g(2n + 1, 2n-1) = g(2n+1, 2) \)이고, \( 2n+1 \)은 항상 홀수이므로,

\( g(2n+1, 2) = 1 \)

 

예제2) 소수 \( p \), \( q \)가 \( 2 < p < q \)를 만족할 때, \( g(p+q, 2p) \)를 구해보자.

 

풀이)

\( g(p+q, p) = g(q, p) = 1 \)이므로

\( g(p+q, 2p) = g(p+q, 2) \)이다.

소수 \( p \), \( q \)가 2보다 큰 소수이므로 모두 홀수이다.

따라서, \( p+q \)는 짝수이고,

\( g(p+q, 2)=2 \)

그러므로, \( g(p+q, 2p) =2 \)

 

예제3) 피보나치 수열 \( F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2} (n \geq 2) \)에서,

        \( g( F_{2023} , F_{2024} ) \)를 구하시오.

 

풀이)

\( g( F_{2023} , F_{2024} ) = g( F_{2023} , F_{2022} + F_{2023} ) = g( F_{2023} , F_{2022} ) \)

마찬가지 방법으로,

\( g( F_{2023} , F_{2022} ) = g( F_{2021}, F_{2022} ) \)

\( g( F_{2021} , F_{2022} ) = g( F_{2021}, F_{2020} ) \)

\( g( F_{2021} , F_{2020} ) = g( F_{2019}, F_{2020} ) \)

\( \vdots \)

\( g( F_3, F_2 ) = g( F_1, F_2) \)

\( g( F_1, F_2 ) = g( 1, 1 ) = 1 \)