피보나치 수열 심화과정4 -피보나치 수의 최대공약수 놀라운 성질-

1. 피보나치 수의 최대공약수

 

다음과 같이 정의되는 피보나치 수열

 

$F_{0} = 0, F_{1} = 1$이고 $F_{n+2} = F_{n+1} + F_{n}, n \geq 0$

 

에 대하여, n번째 피보나치 수 $F_{n}$와 m번째 피보나치 수 $F_{m}$의 최대공약수 $gcd(F_{n}, F_{m})$은

 

n,m의 최대공약수 gcd(n,m)번째 피보나치 수와 같다.

 

$$gcd(F_{n}, F_{m}) = F_{gcd(n,m)}$$

 

 

2. 보조정리1

 

임의의 정수 k에 대하여, $gcd(a,b) = gcd(a+kb, b)$

 

 

증명)

 

x가 a,b의 공약수라면, a는 x로 나누어 떨어지고 ($x | a$로 표시) b도 x로 나누어 떨어진다.

 

그러므로, 임의의 정수 k에 대하여 kb도 x로 나누어 떨어진다.

 

a도 x로 나누어 떨어지고, kb도 x로 나누어 떨어지므로 a+kb도 x로 나누어 떨어진다. 

 

역으로 x가 a+kb와 b의 공약수라고 하자. 

 

그러면 a+kb는 x로 나누어 떨어지고, b도 x로 나누어 떨어진다.

 

그러므로 임의의 정수 k에 대해 kb도 x로 나누어 떨어지며, (a+kb) - kb = a도 x로 나누어 떨어진다.

 

따라서 a,b가 x로 나누어 떨어지므로 x는 a,b의 공약수이다.

 

따라서 (a,b)와 (a+kb,b)가 같은 공약수 집합을 가지므로 둘의 최대공약수도 같아야한다.

 

 

3. 보조정리2

 

서로 인접한 두 피보나치 수 $F_{n}, F_{n+1}$은 서로소이다.

 

즉 자연수 n에 대하여 $gcd(F_{n}, F_{n+1}) = 1$

 

 

증명)

 

n = 1이면, $F_{1} = 1, F_{2} = 1$은 최대공약수가 1이므로, 서로소

 

n = k에서 $gcd(F_{k}, F_{k+1}) = 1$이라고 가정하자.

 

n = k+1이면, $gcd(F_{k+1}, F_{k+2}) = gcd(F_{k+1}, F_{k+1}+F_{k})$

 

보조정리1에 의해 $gcd(a,b) = gcd(a,a+b)$이므로, $gcd(F_{k+1}, F_{k+1}+F_{k}) = gcd(F_{k+1}, F_{k}) = 1$

 

따라서, 모든 자연수 n에 대하여 $gcd(F_{n}, F_{n+1}) = 1$

 

 

4. 보조정리3

 

m과 n이 서로소라면, $gcd(m,nk) = gcd(m,k)$

 

 

증명)

 

m과 nk의 공약수를 x라고 하자. m은 x로 나누어 떨어지고 nk는 x로 나누어 떨어진다.

 

그런데 n은 x로 나누어 떨어지지 않는다.

 

왜냐하면 m과 n이 서로소이므로 둘이 동시에 나누어 떨어지게 하는 x는 존재하지 않는다.

 

그런데 nk가 x로 나누어 떨어지므로 k가 x로 나누어 떨어져야한다.

 

즉 (m,nk)의 공약수와 (m,k)의 공약수가 서로 같다.

 

따라서 둘의 최대공약수도 서로 같아야한다.

 

 

5. 보조정리4

 

$$F_{m+n} = F_{m}F_{n+1} + F_{m-1}F_{n}$$

 

 

증명)

 

https://deepdata.tistory.com/760

행렬을 이용한 피보나치 수열 문제의 해법

 

피보나치 수열을 행렬로 표현하면...

 

$$\begin{pmatrix}
1 & 1\\
1 & 0
\end{pmatrix}=\begin{pmatrix}
F_{2} & F_{1}\\
F_{1} & F_{0}
\end{pmatrix}$$이고,

 

$$\begin{pmatrix}
F_{n+1} & F_{n}\\
F_{n} & F_{n-1}
\end{pmatrix}$$의 앞에 

 

$$\begin{pmatrix}
1 & 1\\
1 & 0
\end{pmatrix}$$을 곱하면,

 

$$\begin{pmatrix}
1 & 1\\
1 & 0
\end{pmatrix}\begin{pmatrix}
F_{n+1} & F_{n}\\
F_{n} & F_{n-1}
\end{pmatrix}=\begin{pmatrix}
F_{n+1}+F_{n} & F_{n}+F_{n-1}\\
F_{n+1} & F_{n}
\end{pmatrix}=\begin{pmatrix}
F_{n+2} & F_{n+1}\\
F_{n+1} & F_{n}
\end{pmatrix}$$

 

그러므로, 일반적으로 피보나치 수열로 이루어진 행렬을 다음과 같이 표현할 수 있다

 

$$\begin{pmatrix}
F_{n+1} & F_{n}\\
F_{n} & F_{n-1}
\end{pmatrix}=\begin{pmatrix}
1 & 1\\
1 & 0
\end{pmatrix}^{n}$$

 

 

그런데, $A^{m+n} = A^{m}A^{n}$이므로,

 

$$\begin{pmatrix}
F_{m+n+1} & F_{m+n}\\
F_{m+n} & F_{m+n-1}
\end{pmatrix}=\begin{pmatrix}
F_{m+1} & F_{m}\\
F_{m} & F_{m-1}
\end{pmatrix}\begin{pmatrix}
F_{n+1} & F_{n}\\
F_{n} & F_{n-1}
\end{pmatrix}=\begin{pmatrix}
F_{m+1}F_{n+1}+F_{m}F_{n} & F_{m+1}F_{n}+F_{m}F_{n-1}\\
F_{m}F_{n+1}+F_{m-1}F_{n} & F_{m}F_{n}+F_{m-1}F_{n-1}
\end{pmatrix}$$

 

위 식은 항등식이므로,

 

$$F_{m+n} = F_{m}F_{n+1} + F_{m-1}F_{n} = F_{m+1}F_{n} + F_{m}F_{n-1}$$

 

 

6. 보조정리5

 

m,n이 자연수일때, $F_{mn}$은 $F_{m}$으로 나누어 떨어진다.

 

 

증명)

 

임의의 자연수 m에 대하여 n에 대한 수학적 귀납법을 이용한다.

 

n = 1일때, $F_{m}$이 $F_{m}$으로 나누어 떨어지는건 자명하다.

 

임의의 n = k에서 위 명제가 성립한다고 가정하자.

 

$$F_{m(k+1)} = F_{mk+m} = F_{mk}F_{m+1} + F_{mk-1}F_{m}$$

 

$F_{mk}$가 F_{m}$으로 나누어 떨어지므로,

 

$$F_{m(k+1)} = F_{m}(xF_{m+1}+F_{mk-1})$$이고, 그러므로 $F_{m(k+1)}$도 $F_{m}$을 인수로 가지므로 나누어 떨어진다.

 

따라서 모든 자연수 n에 대해 $F_{mn}$이 $F_{m}$으로 나누어 떨어진다.

 

 

7. 증명

 

n을 m으로 나눈 몫이 k이고 나머지가 r이라면, n = mk + r이라고 표현할 수 있고,

 

보조정리4를 이용해서

 

$$gcd(F_{m}, F_{n}) = gcd(F_{m}, F_{mk+r}) = gcd(F_{m}, F_{mk+1}F_{r}+F_{mk}F_{r-1})$$

 

 

보조정리5에서.. $F_{mk}$가 $F_{m}$으로 나누어 떨어지므로, $F_{mk} = F_{m}x$라고 하자.

 

 

보조정리1에 의해 $gcd(a,b) = gcd(a,b+ak)$이므로,

 

$$gcd(F_{m},F_{mk+1}F_{r}+F_{m}xF_{r-1}) = gcd(F_{m},F_{mk+1}F_{r})$$

 

$F_{mk}$는 $F_{m}$로 나누어 떨어진다.

 

그런데, $F_{mk}$와 $F_{mk+1}$은 보조정리2에 의해 서로소이다.

 

그러므로, $F_{mk+1}$은 $F_{m}$으로 나누어 떨어지지 않는다. 즉, 둘은 서로소이다.

 

 

그러므로, 보조정리3에 의해 

 

$$gcd(F_{m},F_{mk+1}F_{r}) = gcd(F_{m},F_{r})$$

 

그러므로, $$gcd(F_{m}, F_{n}) = gcd(F_{m}, F_{r})$$

 

https://deepdata.tistory.com/366

최대공약수를 빠르게 구하는 알고리즘 - 유클리드 호제법

 

F와 상관없이 첨자가 마치 유클리드 알고리즘처럼, 진행될 수 있다는 것을 알 수 있다.

 

즉, gcd(m,n) = gcd(s,0)이 될 때까지 반복하면, gcd(m,n) = s가 되듯이

 

$$gcd(F_{m},F_{n}) = gcd(F_{gcd(m,n)},F_{0}) = gcd(F_{gcd(m,n)},0) = F_{gcd(m,n)}$$

 

 

8. 따름정리

 

$F_{n}$이 $F_{m}$으로 나누어 떨어진다면, n은 m으로 나누어 떨어진다.

 

 

증명)

 

$F_{n}$과 $F_{m}$의 최대공약수는 $gcd(F_{m},F_{n}) = F_{gcd(m,n)}$

 

$F_{n} = F_{gcd(m,n)}*p$이고 $F_{m} = F_{gcd(m,n)}q$이며 p,q가 서로소이다.

 

그런데 $F_{n}$이 $F_{m}$으로 나누어 떨어질려면, $F_{gcd(m,n)} = F_{m}$이어야한다.

 

그러므로, gcd(m,n) = m이다. 따라서, n과 m의 최대공약수가 m이며 n은 m으로 나누어 떨어진다.

 

 

9. 연습문제

 

11778번: 피보나치 수와 최대공약수 (acmicpc.net)

11778번: 피보나치 수와 최대공약수

 

 

10. 풀이

 

위의 내용을 그대로 구현한다.

 

a,b를 입력받으면 a,b의 최대공약수를 유클리드 호제법으로 구하고

 

gcd(a,b)번째 피보나치 수를 행렬을 이용해서 구하면 된다

 

from sys import stdin

def matrix_multiplication(a,b,mod):
    
    result = [[0,0],[0,0]]

    for i in range(2):
        
        for j in range(2):
            
            for k in range(2):
                
                result[i][j] += a[i][k]*b[k][j]
                result[i][j] %= mod
    
    return result

def matrix_exponentiation(matrix,n,mod):
    
    result = [[1,0],[0,1]]

    while n > 0:
        
        if n % 2 == 1:
            
            result = matrix_multiplication(result,matrix,mod)
        
        matrix = matrix_multiplication(matrix,matrix,mod)

        n //= 2
    
    return result

def gcd(a,b):
    
    while b != 0:
        
        a,b = b,a%b
    
    return a

mod = 1000000007

n,m = map(int,stdin.readline().split())

matrix = [[1,1],[1,0]]

x = gcd(n,m)

print(matrix_exponentiation(matrix,x,mod)[1][0])

 

 

참조

 

https://www.cut-the-knot.org/arithmetic/algebra/FibonacciGCD.shtml

GCD of Fibonacci Numbers

 

 

https://namu.wiki/w/%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98

최대공약수 - 나무위키

 

 

https://namu.wiki/w/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98%20%EC%88%98%EC%97%B4

피보나치 수열 - 나무위키