수열의 나머지

서로소인 자연수 $a,b$에 대해 수열 $F_{n}=aF_{n-1}+bF_{n-2}$에 대해 초항 $F_{0}=0, F_{1}=1$이면 

$\gcd(F_{n},F_{m})=F_{\gcd(n,m)}$이다. 이것을 증명해보자.

 

• $F_{m} | F_{qm}$

임의의 정수 $n$과 $p$에 대해 $F_{n-2} \equiv 0 \mod{p}$라고 하자.

$F_{n} \equiv aF_{n-1} \pmod{p}$

$F_{2}=a$이므로 다음과 같이 바꿔쓸 수 있다.

$F_{n} \equiv F_{2}F_{n-1} \pmod{p}$

일반적으로 다음과 같이 쓸 수 있다.(이 아래에 나올 성질을 참고하자.)

$F_{n+k} \equiv F_{2+k}F_{n-1} \pmod{p}$

$k=n-4$라고 하자.

$F_{2n-4} \equiv F_{n-2}F_{n-1} \equiv 0 \pmod{p}$

$F_{3n-6} \equiv F_{2n-4}F_{n-1} \equiv 0 \pmod{p}$

...

$F_{qn-2q} \equiv F_{(q-1)n-2(q-1)}F_{n-1} \equiv 0 \pmod{p}$

즉, 다음과 같은 결론을 얻는다.

$F_{m}$이 $p$로 나누어 떨어지면 임의의 자연수 $q$에 대해 $F_{qm}$로 $p$로 나누어 떨어진다.

그런데 $p$는 임의의 자연수이므로 $F_{m} | F_{qm}$이라고 할 수 있다.

 

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

$F_{n+m}$

$=aF_{n+m-1}+bF_{n+m-2}$

$=(a^{2}+b)F_{n+m-2}+abF_{n+m-3}=F_{3}F_{n+m-2}+bF_{2}F_{n+m-3}$

$=(aF_{3}+bF_{2})F_{n+m-3}+bF_{3}F_{n+m-2}=F_{4}F_{n+m-3}+bF_{3}F_{m+n-2}$

...

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

 

• $\gcd(F_{n+1},F_{n})=1$

$\gcd(F_{n+1},F_{n})=d$라고 하자.

그럼 $d | F_{n-1}$이다. 다시 $\gcd(F_{n},F_{n-1})=d$이 되므로 $d | F_{n-2}$이다.

이 과정을 반복하면 $d | F_{1}$이고 $F_{1}=1$ 이기 때문에 $d=1$이다.

 

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

$m=qn+r$

성질 2번에 의해$F_{m}=F_{r+1}F_{qn}+bF_{r}F_{qn-1}$

성질 1번에 의해 $\gcd(F_{m},F_{n})=\gcd(F_{n},bF_{r}F_{qn-1})$

성질 3번에 의해 $\gcd(F_{n},bF_{r}F_{qn-1})=\gcd(F_{n},bF_{r})$

$F_{n}=aF_{n-1}+bF_{n-2}$

$\gcd(F_{n},b)=\gcd(aF_{n-1},b)=\gcd(a^{2}F_{n-2},b)=...=\gcd(a^{n-1}F_{1},b)=\gcd(a^{n-1},b)$

$\gcd(a,b)=1$이므로

$\gcd(a^{n-1},b)=1$

$\gcd(F_{n},b)=1$

이 성질을 이용하면 

$\gcd(F_{n},bF_{r})=\gcd(F_{n},F_{r})$

즉, $\gcd(F_{m},F_{n})=\gcd(F_{n},F_{r})$

이는 $\gcd(F_{m},F_{n})=F_{\gcd(m,n)}$임을 의미한다.